Move Fast

  자료구조 (Data Structure)

• 컴퓨터에서 자료를 정리하고 “조직화”하는 다양한 구조.
• 일련의 동일한 타입의 데이터를 정돈하여 저장한 구성체
• 하나의 데이터 타입에 관한 연산과 표현
• ex) 배열(Array)

  알고리즘 (Algorithm)

• 컴퓨터로 문제를 풀기 위한 단계적인 절차
• 기본적으로 프로그램은 아래와 같은 구조를 가진다.

프로그램 = 자료구조 + 알고리즘

• ex) 최댓값 탐색 프로그램 = 배열 + 순차탐색
• 알고리즘의 조건

1. 입력 : 0개 이상의 입력이 존재
2. 출력 : 1개 이상의 출력이 존재
3. 명백성 : 각 명령어의 의미는 모호하지 않고 명확하다.
4. 유한성 : 한정된 수의 단계 후에는 반드시 종료
5. 효과성 : 각 단계는 충분히 단순하고 기본적이므로 연필과 종이만 사용해서도 수행해볼 수 있다.
6. 유효성 : 각 명령어들은 실행 가능한 연산

  추상 데이터 타입 (Abstract Data Type, ADT)

• 데이터 타입 (Data Type) : 데이터의 집합과 연산의 집합
• 추상 데이터 타입(이하 ADT) : 데이터 타입을 추상적 또는 수학적으로 정의한 것
• 데이터나 연산이 무엇인지는 정의되지만 데이터나 연산을 어떻게 컴퓨터 상에서 구현할 것인지는 정의되지 않는다.
• 데이터 추상화 (Data Abstraction) : 데이터와 연산의 개념 또는 기능을 간추려낸 것으로, 추상화된 각각의 데이터 구조는 데이터와 연산의 구현 방식과는 독립적으로 발달하게 된다. 즉, 연산 수행의 해결책(구현)과는 독립적으로 다루어진다.
• ADT의 구현 (Implementation) : 특정한 데이터 구조를 표현하는 것
• ADT와 자료구조는 별개이며, 데이터 추상화는 자료구조와 프로그램을 연결 짓는 (자료구조 내부의 데이터에 접근하는) ADT 연산을 야기한다.
• 객체 : 추상 데이터 타입에 속하는 객체가 정의된다. 객체는 여러 개가 정의될 수 있다.
• 연산 : 객체 사이에 정의된 연산은 ADT와 외부를 연결하는 인터페이스 역할을 한다.

  알고리즘의 성능 분석 기법

• 수행 시간 측정 : 두 개의 알고리즘의 실제 수행 시간을 측정하는 것으로, 동일한 하드웨어나 운영체제를 사용하여 실제로 구현해야 한다.
• 알고리즘의 복잡도 분석 : 직접 구현하지 않고 수행 시간을 분석하는 것으로, 알고리즘이 수행하는 연산의 횟수를 측정하여 비교한다. 일반적으로 연산의 횟수는 n(=입력 개수)의 함수이다.
• 시간 복잡도 분석 : 수행 시간 분석 (자주 쓰이는 방법)
• 공간 복잡도 분석 : 수행 시 필요로 하는 메모리 공간 분석

  시간 복잡도 분석

• 시간 복잡도는 알고리즘을 이루고 있는 연산들이 몇 번이나 수행되는 지를 숫자로 표시한다.
• 수행 시간이 입력의 크기에 따라 변하면 안 되며, 연산의 수행 횟수는 고정된 숫자가 아닌 입력의 개수 n에 대한 함수로 표현한다. 이를 시간복잡도 함수라고 하고 T(n)이라고 표기한다.

ex) 1+1, 8+2, 144+132 등 두 개를 더하는 시간은 항상 일정해야 한다. 입력의 크기가 1이든 144 든 영향을 받아선 안 된다. 즉, 수행할 작업의 양은 입력의 개수와 관련이 있다.

ex) 사전에서 단어 검색하기

알고리즘 1. 선형 탐색 : 처음부터 끝까지 한 단어씩 탐색하며, 찾는 단어와 일치할 경우 종료

알고리즘 2. 이진 탐색 : 어느 페이지에 단어가 위치하는지 추측하여, 그 페이지보다 앞에 있으면 그 앞부터 다시 추측하고 뒤에 있으면  그 뒤부터 추측한다. 탐색 범위를 절반으로 좁혀나가는 방식이다.

Q) 단어의 개수가 2배인 사전의 경우 어떤 알고리즘이 걸리는 시간이 적은가?

A)

 알고리즘 1의 경우 단어의 개수가 N개 일 때, 최악의 경우 N번 연산을 해야 한다. 즉, 단어의 수와 비례한다고 볼 수 있다. 따라서 N번 연산에 걸리는 시간이 t초일 때, 2N개의 단어라면 최악의 경우 2N번 연산을 하므로 2t초가 걸린다.

 알고리즘 2의 경우 1/2 씩 탐색할 단어의 개수가 줄어들기 때문에, 최악의 경우 번 연산을 해야 한다. 따라서 번 연산에 걸리는 시간이 t초일 때, (연산 횟수가 +1 증가된 것을 알 수 있다.) 단어 하나를 더 찾는 시간(=a초 < t)만큼 시간이 더 걸린다. 즉, 총 (t+a)초가 걸리므로 알고리즘 2가 더 효율적이다.

• 시간 복잡도 함수 계산 예 : 코드를 분석해보면 수행되는 연산들의 횟수를 입력 크기(n)의 함수로 만들 수 있다.

총 연산수 = 1 + n-1 + n-1 = 2n

  빅오 표기법

• 연산의 횟수를 대략적으로 표기한 것
• 두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n >= n0 에 대하여 |f(n)| <= c|g(n)| 만족하는 2개의 상수 c와 n0가 존재하면, f(n) = O(g(n))
• 빅오는 함수의 상한을 표시한다.
• 빅오 표기법을 사용하는 이유 : 시간 복잡도 함수 일 때, n = 1000 이라면 이다. T(n)의 값은 1,001,001 이고, 이중에서 첫 번째 항의 값이 전체의 약 99.9%인 1,000,000이고 두번째 항의 값은 1000으로 전체의 약 0.1%를 차지한다. 따라서 보통 시간복잡도 함수에서 가장 영향을 크게 미치는 항만을 고려하면 충분하기 때문에 빅오 표기법을 사용한다.

  알고리즘의 수행시간

• 최선의 경우 (best case) : 수행시간이 가장 빠른 경우
• 평균의 경우 (average case) : 수행시간이 평균적인 경우
• 최악의 경우 (worst case) : 수행시간이 가장 늦은 경우

최악의 경우는 가장 널리 사용되며, 계산이 쉽고 응용에 따라서 중요한 의미를 가질 수 있다. 여기서 의미란 어떤 입력이 주어지더라도 알고리즘의 수행 시간이 얼마 이상을 넘지 않는다는 상한(Upper Bound)의 의미를 가진다.

  자료 구조의 C언어 표현 방법

• 자료구조와 관련된 데이터들을 구조체로 정의한다.
• 연산을 호출할 경우, 이 구조체를 함수의 매개변수로 전달한다.