한빛출판네트워크

저자: 김대곤

* 알고리즘의 Complexity 또는 계산복잡도
* 탐욕 알고리즘(Greedy Algorithm)
* 동적 프로그래밍(Dynamic Programming) – 고급 설계 기법인가?
* Induction과 병합 정렬(Merge Sort) 알고리즘
* 거짓말 같은 Induction


다음과 같은 신탁이 주어졌다고 합시다. “1에서 n까지 출력하는 알고리즘을 개발하라”

너무 단순해 보여서 한가지 방법만 있는 듯 보입니다. 보기와는 다르게 아주 다양한 방법이 있습니다. 프로그래밍 책을 한 번이라도 본 사람들은 쉽게 다음과 같은 프로그램을 작성할 수 있을 것입니다.

public static void printUsingLoop(int N) {
    for ( int i=1 ; i <= N ; i++ ) {
        System.out.println(i);
    }
}

하지만 재귀 프로그램으로도 쉽게 구현할 수 있습니다.

public static void printUsingRecursion(int N) {
    if ( N == 1 ) {
        System.out.println(N);
    } else {
        printUsingRecursion(N-1);
        System.out.println(N);
    }
}

실행속도는 어떻게 될까요? 반복문을 사용한 경우에는 N에 비례하는 것이 분명하게 보입니다. 그러면 위의 재귀 프로그램의 속도는 어떻게 될까요? 이것도 N에 비례합니다. 재귀 프로그램의 실행속도는 재귀방정식으로 주어집니다. 즉 위의 프로그램의 수행속도는 다음과 같이 정의됩니다.



T(N)를 계속적으로 전개해 보면, N개의 1이 나옵니다. 이것들을 모두 더하면 N이므로 실행속도는 N이 됩니다. 조금 더 복잡해 보이는 프로그램을 만들어 봅시다. 다음과 재귀 프로그램도 1부터 N까지 출력합니다. 초기값은 1과 N이 되겠지요.

public static void printUsingRecursion(int i, int j) {
    if ( i == j ) {
        System.out.println(i);
    } else {
        int k = (int)((i+j)/2);
        printUsingRecursion(i,k);
        printUsingRecursion(k+1,j);
    }
}

수행속도는 어떻게 될까요? 먼저 실행속도는 재귀함수로 표현해 봅시다. 그러면 실행속도는 다음과 같이 표현됩니다.



간단히 말하기 힘들어 보입니다. T(1,5)를 전개해 봅시다.
T(1,4)=T(1,2)+T(3,4)+1={T(1,1)+T(2,2)+1}+{T(3,3)+T(4,4)+1}+1
다시 정리하면 T(1,4)=7이 됩니다. 동일하게 방법으로 T(1,8)=15가 됩니다. N에 비례한다고 말하기가 조금 주저되는 상황입니다. 결론부터 말하면 실행속도는 N에 비례합니다. 그리고 N(=j-i+1)이 2의 제곱승일 때 T(1,N)은 2N-1이 됩니다. 이것은 고등학교 수학으로 간단하게 계산이 가능합니다. 그 전에 재귀 트리(Recursion Tree)를 생각해 봅니다.



실제적인 출력은 leaf에서만 수행됩니다. 만약 leaf의 갯수가 N이고 leaf가 아닌 모든 노드들이 2개의 하위 노드를 가지고 있는 경우, 이러한 노드의 갯수는 N-1이 됩니다. 이것은 고등학교 수학으로 증명이 가능합니다. 최상위 노드는 하나이고 그 다음은 2개가 되고 그 다음은 4개 됩니다. 최상위 노드에서 Leaf 노드까지의 거리는 일정합니다. 그리고 이 거리를 h라고 합시다. Leaf가 아닌 노드의 갯수는 다음과 같이 계산됩니다. 등비수열의 합을 구하는 공식 생각나시죠.



N이 이므로 내부 노드의 갯수는 N-1이 됩니다. 전체 합은 2N-1입니다. 여기서 비례한다는 것은 알고리즘의 계산복잡도를 말하는 것입니다. 이것에 대한 간략한 설명은 “알고리즘 Complexity 또는 계산복잡도” 기사에서 찾을 수 있습니다.

알고리즘을 시작하는 사람들이 가지는 가장 일반적인 고정관념 중에 하나는 여기서 알고리즘이 끝났다고 생각하는데 있습니다. 하지만 알고리즘은 반드시 증명을 따라옵니다. 즉, 알고리즘이 목표한 결과를 가져온다는 것을 증명하지 않으면 무용지물입니다. 어떻게 그 알고리즘을 사용해서 프로그램을 할 수 있습니까 어떤 값을 나올지 모르는 상황에서. 일반적으로 알고리즘의 핵심을 알고리즘을 증명하는 과정에 있다고 할 수 있습니다. 이 과정을 연습해서 얻는 결과물은 자신의 문제에 대한 알고리즘 개발할 수 있는 것입니다. 알고리즘의 개발과 알고리즘의 증명은 동전의 양면과 같습니다.

여기서 사설은 중단하고 위에 있는 각 알고리즘을 증명해 봅시다. 먼저 첫번째 재귀 프로그램(R1이라고 합시다)을 증명해 봅시다. 만약 N=1이면, R1은 1(=N)를 출력합니다. 1에서 N(=1)까지 출력하였습니다. 만약 이 R1이 N=k일 때, 1에서 k까지 출력한다고 가정합시다. N=k+1일 때, R1(k)이 1부터 k까지 출력합니다. 그리고 나서 k+1를 출력합니다. 그러므로 1부터 k+1까지 출력합니다. 즉, 어떠한 자연수 N에 대하여 R1은 1부터 N까지 출력합니다. 이것으로 증명은 끝났습니다. 재귀 프로그램은 Induction를 이용하여 증명합니다.

그러면 처음에 있는 반복문은 어떻게 증명할까요? Loop Invariant로 이용하여 반복문을 증명합니다. Loop Invariant은 간단하게 말하면, 반복문이 시작되는 위치에서 항상 만족하는 성질입니다. 즉

각 루프의 시작점(for 과 출력문 사이), 이 때의 i의 값은 k라고 합시다. 1부터 k-1까지 출력되었다.

이것에 대하여 반복문 이전, 반복문이 수행되는 동안, 반복문이 끝난 시점에 위의 성질이 만족하는 것을 보이는 것이 반복문 증명의 방법입니다. 자 시작해 봅시다.

반복문이 시작되는 전에는 i=1입니다. 아직 아무것도 출력되지 않았습니다. 1에서 0까지는 아무것도 없으므로 Loop invariant를 만족합니다.

반복문이 i=k라고 합시다. 이 때에는 1부터 k-1까지 출력되었습니다. 그리고 k까 출력됩니다. 그리고 반복문은 i=k+1인 시작점을 통과하게 됩니다. 이 때에 1부터 k까지 출력되었습니다. 즉 1부터 (k+1)-1까지 출력되었습니다. 그러므로 모든 루프의 시작점에서 위의 성질은 만족합니다.

반복문이 끝나면, i는 N+1이 됩니다. i=N인 루프의 시작점에서 1에서 N-1까지 출력했고, 반복문을 빠져나오기 전에 N를 출력하였습니다. i=N+1일 때 1부터 N까지 출력하였습니다.

즉 반복문을 빠져 나온 시점에 우리가 예상할 수 있는 결과는 1부터 N까지 출력되었다는 것입니다. 이것으로 반복문을 사용한 알고리즘의 증명은 끝났습니다.

무슨 말 장난이냐고 생각하실 분이 계실지 모릅니다. 하지만 이 과정 없이는 스스로 알고리즘을 개발하기는 아주 힘듭니다. 이제 위의 과정을 잘 이해되었다면 쉽게 풀리는 몇가지 문제를 제시함으로써 기사를 마무리 하려고 합니다.

1. 주어진 N에 대하여 N부터 1까지 출력하는 프로그램.
2. 주어진 N(=2^k-1 )에 대하여 1에서 N까지의 짝수를 순서대로 출력하는 프로그램.
3. 주어진 N(=2^k-1)에 대하여 1에서 N까지의 수 중에서 4로 나누었을 때 2가 남는 수를 순서대로 출력하는 프로그램.
4. 정렬된 정수의 배열 A[1…N]에서 k가 있는지 없는지 확인하는 프로그램. 예를 들어 A[1…5]가 다음과 같이 주어졌다고 하자.



k=8이면 2, k=15이면 -1를 출력해야 한다. 즉 있으면 그 위치를 출력하고 없으면 -1를 출력하는 프로그램.