『Disclaimer: 본 글은 대학원의 데이터과학 알고리즘 수업 및 데이터과학 입문서적에 관한 공부 내용을 정리하는 시리즈입니다. 

본 내용은 필자가 전부 직접 요약하여 적은 개인 노트이며, 개인 공부 및 복습이 주목적일 뿐, 상업적 의도는 없습니다. 

Source: Introduction to Algorithms 3rd Ed., by Cormen, Leiserson, Rivest, Stein』

1-1. 알고리즘의 정의

알고리즘은 인풋값을 받아 아웃풋값을 내놓는 잘 정의된 프로시져이다.

그리고 이러한 알고리즘은 잘 정의된 computational problem을 푸는 도구이기도 하다.

정렬(Sorting) 문제를 예로 들면, 인풋은 어떤 넘버 시퀀스이고, 아웃풋은 정리된 시퀀스이다.

알고리즘은 각 인풋에 대해 올바른 아웃풋을 내놓을 경우 올바르다(correct)고 한다.

그리고 올바른 알고리즘은 주어진 computational problem을 푼다(solve)고 한다.

올바르지 않은(incorrect) 알고리즘의 경우에도, 그 error rate을 컨트롤할 수 있으면 유용하기도 하다.

Data structure는 데이터를 저장하고 정리하는 방식이다. 

모든 용도에 두루 맞는 data structure는 없으므로 각 장단점을 알아야 한다.

알고리즘을 프로세스하는 하드웨어 경우, clock speed와 superlinear하게 power density가 증가하므로,

요즘처럼 고성능에서는 칩이 타버릴 위험이 매우 높아서 멀티코어를 제작하고 있다.

멀티코어는 곧 여러 컴퓨터를 병렬화한 것과도 같은데, 이를 염두에 두고 알고리즘을 디자인해야 한다.

1-2. 삽입 정렬(Insertion Sort) 알고리즘

첫번째 알고리즘 예로, 정렬(sorting) 문제를 풀어보자. 

인풋은 n개의 숫자 시퀀스고, 아웃풋은 정렬된 시퀀스이며, 우리가 풀고자하는 숫자들은 key라 부른다.

먼저, insertion sort의 경우, 키를 한번에 하나씩 뽑아서, 정렬된 시퀀스에 삽입을 한다.

첫번째 키는 빈 시퀀스에 들어가고, 두번째 키는 첫번째 키와 비교 후 들어간다.

세번째부터는 우측부터 좌측으로 비교하여 키보다 작거나 같은 수를 만나면 그곳에 삽입된다.

이 알고리즘은 인풋값들을 in place에서 정렬한다. 

즉, Array A 내에서 정렬이 진행되며, 한번에 어떤 상수 이하의 개수 숫자들만 array 밖에 store되어 있다.

아래는 pseudocode다.

1 for j = 2 to n

2 key = A[j]

3 i = j - 1

4 while i > 0 and A[i] > key

5 A[i + 1] = A[i]

6 i = i - 1

7 A[i + 1] = key

이 알고리즘이 올바른지 확인하기 위해서는 귀납 추론을 활용한다.

Base Case: i = 1 에 대해 trivially 참이다.

Inductive Hypothesis: 어떤 1 <= i < n에 대해 참이라고 가정한다.

Inductive Step: i + 1에 대해 참임을 증명한다. 

i = 1에 대해 참이고 i + 1에 대해 참이므로 모든 i에 대해 참임이 증명된다.

1-3. Pseudocode 형식

Pseudocode의 형식은 다음을 따른다.

- Indentation은 block structure를 의미한다. 즉, for나 while loop, 그리고 if-else 다음은 indent한다.

- while, for, repeat-until, if-else는 일반 코딩언어와 동일하다. for의 경우 증가는 to, 감소는 downto를 사용하고, 증감량엔 by를 사용한다.

- //는 코멘트를 의미한다.

- i = j = e의 경우 i = e와 i = j를 둘다 쓴 것과 같다. 

- 명확한 설명없이 global variable을 사용하지는 않는다.

- Array element의 엑세스는 A[i]로 하며, 인덱스는 0이 아닌 1부터 시작한다.

- 어떤 object에 점 . 을 붙이면 그 attribute에 엑세스 가능하다.

- y = x로 두면 둘다 같은 오브젝트를 참조한다. 이후 x.f = 3으로 두면 y.f도 3이 된다.

- Attribute은 cascade가 가능하다. 즉, f 그 자체가 g의 attribute을 가진 오브젝트에 대한 pointer면, x.f.g는 (x.f).g와 같다.

- 아무 object도 참조하지 않는 포인터의 경우 NIL이라는 값을 준다.

- 우리는 parameter를 procedure에 그 값 자체를 패스한다. Called procedure는 own copy of parameters를 가진다.

- Object가 pass되었을 때, 그 object를 대표하는 pointer는 복사되어도 그 object의 attribute은 그러지 않는다.

- return 명령어로 다수 값을 리턴할 수 있다.

- and와 or는 short circuiting이다. 즉, x and y에서 x가 거짓이면, y를 evaluate하지 않는다.

1-4. 알고리즘의 분석

알고리즘을 분석(analyze)한다는 것은, 알고리즘이 필요로하는 자원(resource)를 예상하는 것을 의미하게 되었다.

메모리, 접속 bandwidth, 하드웨어 등이 중요할 때도 있지만, 일반적으로 computational time을 의미한다.

본 노트에서는 프로세서가 RAM(random-access machine) 모델을 가정하는데, 여기서 프로그램은 동시가 아닌 한 줄 씩 실행된다.

또한 2^k의 경우, 이진수를 shift-left 방식을 사용하여 계산 가능하므로 constant time operation으로 취급한다.

RAM 모델의 경우 memory hierarchy는 모델하지 않는다.

알고리즘의 분석에는 'size of input'과 'running time' 두 가지를 측정해야 한다.

Input size의 경우 해당 문제에 의존하는 경향이 큰데, 가장 자연스러운 해석은 인풋값에 들어있는 아이템 숫자이다.

Running time의 경우, primitive operation 혹은 step의 숫자로 판단한다.

그리고 각 operation을 실행하는데 드는 시간은 operation 종류에 따라 다르겠지만 어떠한 상수 c_i라 정한다.

1 for j = 2 to n

2 key = A[j]

3 i = j - 1

4 while i > 0 and A[i] > key

5 A[i + 1] = A[i]

6 i = i - 1

7 A[i + 1] = key

그러면 위의 pseudocode를 분석해 보면, 

line cost times

1 c1 n (1의 경우에도 loop에 포함되는지 안되는지 판단해야하므로)

2 c2 n - 1 (2부터 n까지)

3 c3 n - 1 (2부터 n까지)

4 c4 ∑ⁿ_j=2 t_j

5 c5 ∑ⁿ_{j=2 (}t_j - 1)

6 c6 ∑ⁿ_{j=2 (}t_j - 1)

7 c7 n - 1 (line 2, 3과 동일)

line 4~6의 경우, 기존의 시퀀스가 sort가 얼마나 잘되었느냐에 달려 있으므로 새로운 변수 t로 표기한다.

여기서 c1 ~ c7이 동일하게 1이라고 가정을 하면,

이 알고리즘의 running time T(n)은 위의 모든 'times' column을 더한 값이다.

그러면 t값에 따라 best case와 worst case로 나눌 수 있다.

Best case는 이미 시퀀스가 정렬되어 있을 경우, j = 2, ..., n에 대해 t_j = 1이며 5, 6번 라인은 실행되지 않는다.

즉, T(n) = c1n + c2(n - 1) + c3(n - 1) + c4(n - 1) + c7(n - 1) = 5n - 4 이다.

Worst case는 시퀀스가 역정렬되어 있을 경우, t_j = n(n+1)/2 -1 (2부터 시작하므로 1을 뺌)이고, t_j-1 = n(n-1)/2이다.

즉, T(n) = c1n + c2(n - 1) + c3(n - 1) + c4(n(n+1)/2 - 1) + c5(n(n-1)/2) + c6(n(n-1)/2) + c7(n - 1) = 1.5n^2 + 3.5n - 4 이다.

따라서 이 알고리즘의 running time은 quadratic function이다.

여기서는 best case도 고려했지만, 일반적으로는 worst case만 다룬다.

또한, 실제적으로는 an^2에서 constant coefficient a도 중요하지만 이론에서는 order of growth에 초점을 둔다.