[Discrete Mathematics] 알고리즘(algorithms) 및 알고리즘 분석

---

알고리즘 (Algorithms)

 

알고리즘은 어떤 문제를 해결하기 위한 단계별 방법이며, 다음의 특성을 가진다.

• 입력 (Input) : 알고리즘은 입력을 받는다.
• 출력 (Output) : 알고리즘은 출력을 생성한다.
• 정밀성 (Precision) : 각 단계가 명확하게 기술되어 있다.
• 결정성 (Determinism) : 실행 과정에서 각 단계의 결과는 유일하며, 입력과 이전 단계의 결과에 의해 결정된다.
• 유한성 (Finiteness) : 알고리즘은 유한한 수의 명령어가 실행된 후 종료된다.
• 정확성 (Correctness) : 알고리즘이 생성한 출력은 문제를 정확하게 해결한다.
• 일반성 (Generality) : 알고리즘은 일련의 입력에 대해 적용된다.

 

---

의사코드 (Pseudo-code)

 

영어를 그대로 읽어서 슈도코드라고도 한다. 알고리즘을 표현하는 방법으로 프로그래밍 코드와 비슷하지만, 특별히 작성 기준이나 문법 없이 작성한 코드로 당연히 프로그램으로 실행은 안 된다.

실제 프로그래밍에서 제약이 있는 부분을 생략하고 서술할 수 있고, 그러면서도 실제 프로그래밍 코드와 비슷해 정리하고 추후에 프로그래밍 언어로 전환하기 편리하다.

 

---

의사코드로 나타낸 알고리즘의 예

 

• 문자 탐색 알고리즘 (Text_Search Algorithm)

입력 : $ p $ (찾으려는 단어), $ m $ (찾으려는 단어의 길이), $ t $ (대상이 되는 글), $ n $ (대상이 되는 글의 길이)
출력 : $ i $ (찾으려는 단어가 있는 위치)

text_search(p, m, t, n) {
    for i = 1 to n - m + 1 {
    	j = 1
        while (t[i+j-1] == p[j]) {
            j = j + 1
            if (j > m) {
            	return i
            }
        }
    }
    return 0
}

1 부터 시작하는(프로그래밍 언어라면 0 부터 시작하는 경우가 대다수일 것) 인덱스를 통해 대상이 되는 글의 글자 하나 하나를 확인하다가 찾으려는 단어의 시작 글자와 같다면 루프가 시작된다. 루프가 시작되면 그 후로 몇 글자나 찾으려는 단어와 같은지 확인하고, 만약 찾으려는 글자의 길이만큼 같다는 것이 확인된다면, 해당 위치에 그 단어가 있는 것이 확인된 것이므로 해당 위치를 반환한다.

 

• 삽입 정렬 알고리즘 (Insertion Sort Algorithm)

입력 : $ s $ (정렬 대상이 되는 시퀀스), $ n $ (시퀀스의 크기)
출력 : $ s $ (정렬된 시퀀스)

insertion_sort(s, n) {
    for i = 2 to n {
    	val = s[i]
        j = i - 1
        while(j >= 1 and val < s[j]) {
            s[j+1] = s[j]
            j = j - 1
        }
        s[j+1] = val
    }
}

정렬 대상이 되는 시퀀스를 읽으면서 두 번째 원소부터 val 변수에 대입한다. val 에 담긴 값이 지금 정렬할 원소이다. 이때 j 의 시작은 val 의 담긴 원소의 인덱스 - 1 이다. 그 후 j 번째 원소가 val 보다 작다면 루프가 시작된다. 루프가 시작되면 j 번째 원소를 오른쪽으로 한 칸 이동시키고, j 를 1 줄인다. 즉 val 이 들어갈 자리를 만든다. 이 루프는 j 번째 원소가 val 보다 작지 않거나 j 가 1 보다 작아지면 멈춘다. 즉 j 가 조정되면서 val 보다 작은 값을 만나거나, 가장 앞에 도달하면 루프가 멈춘다. 루프가 멈추면(혹은 루프에 들어가지 않았다면) j + 1 에 val 을 대입하여 해당 수의 정렬을 완료한다.

 

---

알고리즘 분석

 

복잡도(complexity)란 알고리즘이 얼마나 많은 자원을 소비하는지를 말한다. 이는 시간 복잡도와 공간 복잡도로 나뉘며 이를 통해 동일한 문제를 해결하는 여러 알고리즘을 비교할 수 있다.

단 같은 $ n $ 의 크기를 갖는 알고리즘에 대해서도 알고리즘의 시간 복잡도는 입력에 따라 달라질 수 있다. 예를 들어 삽입 정렬 알고리즘의 입력으로 정렬된 시퀀스를 주는 것과 정렬되지 않은 시퀀스를 주는 것은 차이가 분명하다.

시간은 알고리즘이 실행되는 시간, 명확히는 연산 횟수를 말하며, 공간은 변수의 수, 시퀀스의 길이 등 차지하는 공간 영역, 컴퓨터에서는 필요한 메모리 크기를 말한다.

알고리즘 분석은 알고리즘의 시간 복잡도와 공간 복잡도를 추정하는 과정을 말하며, 특히 시간 복잡도를 위주로 추정한다. 시간 복잡도는 입력에 대한 함수로 입력 크기 $ n $ 을 매개변수로 사용한다.

최선의 경우의 시간(best-case time)은 크기가 $ n $ 인 모든 입력 중 알고리즘을 실행하는 데 필요한 최소 시간이고, 최악의 경우의 시간(worst-case time)은 크기가 $ n $ 인 모든 입력 중 알고리즘을 실행하는 데 필요한 최대 시간이며, 평균적인 경우의 시간 (average-case time)은 크기가 $ n $ 인 유한 집합의 입력에 대해 알고리즘을 실행하는 데 필요한 평균 시간이다.

입력의 크기가 작을 때 입력 크기에 따른 변화는 알고리즘의 실행 시간에 큰 영향이 없겠지만, 입력 크기가 커지면 입력 크기에 따른 변화가 중요해진다. 예를 들어 $ 2n $ 의 시간 복잡도를 가지는 알고리즘과 $ n^2 $ 의 시간 복잡도를 가지는 알고리즘은 입력이 작을 때는 큰 차이가 없고, 심지어 $ 2n $ 의 시간 복잡도가 더 작겠지만, 입력의 크기가 커지면 $ n^2 $ 의 시간 복잡도가 기하급수적으로 커진다.

일반적으로 시간 복잡도는 아래와 같이 순서를 매긴다.

$$ 1 < \lg n < n < n \lg n < n^2 < 2^n < n! $$

 

---

표기법 (Notation)

 

• Big-O | 빅오

$ f(n) = \mathcal{O}(g(n)) $ 은 양의 상수 $ C_1 $ 이 존재하여 모든 유한한 양의 정수 $ n $ 에 대해 $ f(n) \leq C_1 | g(n) | $ 이 성립함을 의미한다. 즉 $ f(n) $ 은 최대 $ g(n) $ 의 차수에 해당하면 성립한다.

 

• Big-Ω | 빅오메가

$ f(n) = \varOmega(g(n)) $ 은 양의 상수 $ C_2 $ 가 존재하여 모든 유한한 양의 정수 $ n $ 에 대해 $ |f(n)| \geq C_2 | g(n) | $ 이 성립함을 의미한다.

 

• Big-Θ | 빅세타

$ f(n) = \varTheta(g(n)) $ 은 $ f(n) $ 이 $ \mathcal{O}(g(n)) $ 이면서 동시에 $ \varOmega (g(n)) $ 일 때를 의미한다. 즉 $ f(n) $ 은 $ g(n) $ 의 차수에 해당한다.

$ a_k n^k + a_{k-1} n^{k-1} + \cdots + a_1 n + a_0 = \varTheta (n^k) $ 이다.

$ \lg n! = \varTheta (n \lg n) $ 이다. $ (\lg = \log _2) $

$ f(n) = \varTheta (g(n)) $ 이고 $ g(n) = \varTheta (h(n)) $ 일 때, $ f(n) = \varTheta(h(n)) $ 이다.

만약 루프마다 연산량이 절반씩 줄어드는 알고리즘이 있고, 그 알고리즘의 시간 복잡도가 $ g(n) $ 이라면 $ \varTheta (g(n)) = \varTheta (\lg n) $ 이다.

예를 들어 다음 의사코드와 같은, 즉 루프마다 연산량이 절반씩 줄어드는 알고리즘을 가정하자.

i = n
while (i >= 1) {
    x = x + 1
    i = floor(i / 2)
}

 만약 $ n $ 이 $ 2^{k-1} \leq n < 2^k $ 를 만족하면 $ \mathtt{x = x + 1} $ 이 $ k $ 번 실행된다고 가정하자. 수학적 귀납법을 이용하면 $ k = 1 $ 인 경우 $ 2^{1-1} = 1 \leq n < 2^1 $ 가 성립한다. $ n = 1 $ 이고, 실제 $ \mathtt{x = x + 1} $ 의 시행 횟수도 $ 1 $ 이므로 기초 단계가 성립하였다.

$ i = \lfloor i / 2 \rfloor $ 를 생각하기 위해 귀납 가정 $ n $ 이 $ 2^{k-1} \leq n < 2^k $ 를 만족하면 $ \mathtt{x = x + 1} $ 이 $ k $ 번 실행된다를 가정하자. $ 2^k \leq n < 2^{k+1} $ 을 증명해야 하는데, $ i $ 가 반으로 줄었으므로 $ 2^{k-1} \leq n < 2^k $ 이다. 그런데 이는 귀납 가정으로 참이라 전제되었기 때문에 참이고, 귀납 단계가 증명되었다.

기초 단계와 귀납 가정이 모두 증명되었기 때문에 수학적 귀납법에 의해 $ n $ 이 $ 2^{k-1} \leq n < 2^k $ 를 만족하면 $ \mathtt{x = x + 1} $ 이 $ k $ 번 실행된다고 말할 수 있다.

이제 양변에 로그를 위차현 $ k - 1 \leq \lg n < k $ 이다. 즉 $ \mathtt{x = x + 1} $ 이 실행되는 횟수는 $ \lg n < k \leq 1 + \lg n $ 이다. $ k $ 는 정수이므로 $ k = 1 + \lg n $ 이 성립하고, $ 1 + \lg n = \Theta (\lg n) $ 이므로 $ \mathtt{x = x + 1} $ 이 실행되는 횟수는 $ \varTheta(\lg n) $ 이다.

즉 연산량이 절반씩 줄어드는 알고리즘의 시간 복잡도는 $ \varTheta (\lg n) $ 이다.

 

---

재귀적 알고리즘 (Recursive Algorithm)

 

재귀 함수는 자신을 호출하는 함수이고, 이 재귀 함수를 포함하는 알고리즘을 재귀적 알고리즘이라 한다.

재귀는 많은 문제를 해결하는데 있어 강력하고, 자연스러운 방법이다. 이 유형의 문제는 분할 정복(divide-and-conquer)을 사용하여 원래 문제와 동일한 유형의 작은 문제들로 분할하여 해결할 수 있다. 각 하위 문제는 차례로 더 작은 하위 문제로 분해되며, 이 과정은 간단하게 해결 가능한 하위 문제로 나뉠 때까지 반복된다. 마지막으로 해결 가능한 하위 문제로 원래 문제를 모두 나눴다면 이 하위 문제를 풀고, 이 해결책들을 결합하여 원래 문제에 대한 해결책을 얻는다.

주의해야 할 것은 재귀 함수를 구성할 때 베이스 케이스(base cases)이 반드시 있어야 한다는 것이다. 만약 베이스 케이스가 없다면 재귀 함수는 무한히 자기 자신을 호출할 것이다.

가장 대표적인 예시가 팩토리얼 계산과 피보나치 수열 계산이다. 이는 자료구조 관련하여 정리해놓은 재귀(링크)를 확인하면 좋을 듯 하다. 기본적으로 재귀로 구성하게 되면 팩토리얼 계산의 시간 복잡도는 $ \varTheta(n) $ 이고, 피보나치 수열 계산의 시간 복잡도는 $ \varTheta(2^n) $ 이다.