한빛출판네트워크

저자: 김대곤


얼마 전에 완역된 Introduction to Algorithms(개정판)에도 Dynamic Programming은 고급 설계 및 분석 기법에 등장한다. 이번 기사에서는 Dynamic Programming의 핵심 아이디어와, 장점과 단점을 살펴보고, 또한 어떤 상황에 적용할 수 있는지 살펴보자. 그리고 나서 정말 고급(?)한 기술인지 스스로 판단해 보자.

먼저 다음 문제를 생각해 보자. 한 저택에는 30 개의 방이 있으며, 5 * 6 형태로 배열되어 있다(그림 1). 각 방에는 일정한 금액이 놓여져 있다.




[ 그림 1 ]


Start 지점에서 End 까지 가는 길들 중에서 가장 많은 금액을 모을 수 있는 길을 찾는 것이다. 단 위로 또는 왼쪽으로만 이동할 수 있다.

“그래, 간단한데. 가능한 모든 길을 전부 비교해 보면 되지.” 그런데, 문제는 계산이 그렇게 간단하지 않다는데 있다. 먼저, 가능한 길의 갯수는 126개이다. 각 길은 8 개의 방으로 구성되어 있다. 별로 계산하고 싶지 않은 숫자다. 사람 뿐 아니라 컴퓨터도 똑같은 생각을 가지고 있다.

이야기를 더 진행하기 전에 몇 가지 용어를 정의하도록 하자.

- MONEY(i,j) : (i,j)방에 있는 금액.
- UP(i,j) : (i,j)방 위에 있는 방, 즉 (i-1,j) 방.
- LEFT(i,j) : (i,j)방 위에 있는 왼쪽 방, 즉 (i,j-1) 방.
- COST(i,j,k,l) : (i,j)방에서 (m,n)방으로 갈 때 얻을 수 있는 최대 금액.
- PATH(i,j,k,l) : 최대 금액을 얻을 수 있는 (i,j)방에서 (m,n)방으로 가는 경로.

Start 지점에 있다고 가정해 보자. LEFT(5,6)로 가야하는지, UP(5,6)로 가야하는지를 제외하고는 무엇이든지 알아낼 수 있다면, 어떠한 정보가 필요한가? 만약, COST(LEFT(5,6))와 COST(UP(5,6))를 알고 있다면, 어느 길로 갈 것인가? 좀 더 직설적으로 말해서, UP(5,6) 입구에 COST(UP(5,6))=401, LEFT(5,6) 입구에 COST(LEFT(5,6))=391 이라고 써 놓았다면, 어디로 가겠는가? 당연히 UP(5,6)로 갈 것이다. 이제 문제는 각 COST(i,j)를 구하는 것으로 볼 수 있다. COST(i,j)는 다음과 같이 정의된다.

- COST(i,j) = MONEY(i,j), if i=1 && j=1
- COST(i,j) = MONEY(i,j)+COST(i,j-1), if i=1 && j>1
- COST(i,j) = MONEY(i,j)+COST(i-1,j), if i>1 && j=1
- COST(i,j) = MONEY(i,j)+MAX(COST(i-1,j),COST(i,j-1)), if i>1 && j>1

사실은 여기까지는 Induction를 이용한 알고리즘 설계이다. 이것을 그대로 옮기면 다음과 같은 프로그램을 작성할 수 있다.


public static int getRecursiveCost(int i, int j) {
        // Boundary case.
        if ( i == 0 && j == 0 ) {
            return rooms[i][j];
        }
        
        // Reach bottom
        if ( i == 0 ) {
            return rooms[i][j] + getRecursiveCost(i,j-1);
        }
        
        // Reach leftest.
        if ( j == 0 ) {
            return rooms[i][j] + getRecursiveCost(i-1,j);
        }
        
        int right = getRecursiveCost(i-1,j);
        int down  = getRecursiveCost(i,j-1);
        
        if ( right > down ) {
            return rooms[i][j] + right;
        }
        
        return rooms[i][j] + down;
        
    }


실행가능한 프로그램은 NaiveRecursion.java로 사이트에서 다운로드 가능하다. 이름에서도 알 수 있듯이 위의 프로그램은 효율적인 프로그램은 아니다. 그 이유는 이 재귀 프로그램의 재귀 트리(Recursion Tree)를 그려보면 쉽게 알 수 있다.




[ 그림 2 ]


같은 함수가 여러 번 호출된 것을 쉽게 알 수 있다. 예를 들면 COST(3,5)는 3번 호출되었다. 이것은 Dynamic Programming를 사용해야 하는 하나의 표지가 된다. 즉, Recursion Tree에서 반복이 있는 경우에 Dynamic Programming를 사용한다. 하지만 조금의 코드 수정으로도 Dynamic Programming과 같은 효과를 얻을 수 있다. 이러한 방법을 Memoization, Caching, 또는 Tabulation이라고 부른다. 이름에서도 알 수 있듯이, 한 번 계산한 값을 저장해 놓고, 필요하면 가져다 쓰는 것이다.


public static int getMemoizedCost(int i, int j) {
        if ( costs[i][j] != 0 ) {
            return costs[i][j];
        } 
        
        // Boundary case.
        if ( i == 0 && j == 0 ) {
            costs[i][j] = rooms[i][j];
            return costs[i][j];
        }
        
        // Reach bottom
        if ( i == 0 ) {
            costs[i][j] = rooms[i][j] + getMemoizedCost(i,j-1);
            return costs[i][j];
        }
        
        // Reach leftest.
        if ( j == 0 ) {
            costs[i][j] = rooms[i][j] + getMemoizedCost(i-1,j);
            return costs[i][j];
        }
        
        int right = getMemoizedCost(i-1,j);
        int down  = getMemoizedCost(i,j-1);
        
        if ( right > down ) {
            costs[i][j] = rooms[i][j] + right;
            return costs[i][j];
        }
        
        costs[i][j] = rooms[i][j] + down; 
        return costs[i][j];
        
    }


여러 번 호출 되지만 재계산하지 않고 계산값을 사용한다. 나머지 코드는 입력과 무관한 작은 상수이고, 호출되는 인자의 값 범위는 1~5, 1~6 이므로 5*6의 시간이 걸린다. 즉, n*m 의 방이 있는 경우, O(n*m) 걸린다. 단순한 재귀 프로그램에 비해 엄청난 발전이다. 지수(exponential) 함수에서 제곱승으로 시간이 단축된 것이다.

Dynamic Programming으로 넘어가기 전에 Dynamic Programming를 적용할 수 있는 또 다른 기준에 대해서 알아보자. 만약 PATH(5,6,1,1)이 (3,5)방을 지나간다고 가정하자. 그러면 PATH(5,6,1,1)은 단순히 PATH(5,6,3,5)와 PATH(3,5,1,1)를 연결한 것이다. 증명은 간단하다. 만약 방(5,6)에서 방(3,5)로 가는 더 좋은 경로가 있다면, 그 경로와 PATH(3,5,1,1)를 연결하면, 방(5,6)에서 방(1,1)로 가는 더 좋은 경로를 얻게 되며, 이것은 처음에 택한 경로가 PATH(5,6,1,1)이라는 가정과 모순된다. 이러한 성질을 Optimal Substructure라고 하며, Dynamic Programming를 적용할 수 있는지에 대한 또 다른 아이디어를 제공한다.

우리가 걸어온 단계 중에서 가장 힘든 부분은 재귀식을 도출하는 것이다. 그 이후에는 단순한 수정에 불과하다. Dynamic Programming이란 Memoization이 필요하지 않도록 단순히 계산 순서를 조정하는 것이다. Memoization의 단점은 추가적인 메모리 사용과 재귀 프로그램이 만들어 내는 추가적인 부담이다. 장점은 간단함에 있다. Dynamic Programming의 장점은 Memoization의 단점이 없다는 것이고, 단점은 Memoization의 장점이 없다는 것이다. 즉, 머리 좀 싸매야 한다는 것.

위의 예제에 Dynamic Programming를 적용하면, COST(i,j) 이전에 COST(i-1,j)와 COST(i,j-1)를 계산하는 것이다. 이 예제에서는 계산 순서가 쉽게 보이지만, 모든 문제가 이처럼 쉽지는 않다. 마지막으로 이러한 순서를 만족하는 프로그램을 제공하는 것으로 기사를 마치도록 하자.


public static void main(String[] args) {
        // Read input data
        read();
        
        // Compute
        for ( int i=0 ; i < 5 ; i++ ) {
            for ( int j=0 ; j < 6 ; j++ ) {
                //costs[i][j] = getMemoizedCost(i,j);
                if ( i == 0 && j == 0 ) {
                    rooms[i][j] = rooms[i][j];
                } else if ( i == 0 ) {
                    rooms[i][j] = rooms[i][j] + rooms[i][j-1];
                } else if ( j == 0 ) {
                    rooms[i][j] = rooms[i][j] + rooms[i-1][j];
                } else {
                    if ( rooms[i-1][j] > rooms[i][j-1] ) {
                        rooms[i][j] = rooms[i][j] + rooms[i-1][j];
                    } else {
                        rooms[i][j] = rooms[i][j] + rooms[i][j-1];
                    }
                }
            }
        }
        
        printMatrix(rooms);
    }


* 예제에 사용한 문제의 경우, 가능한 길의 갯수는 126개이다. 이것도 Dynamic Programming를 이용하여 쉽게 구할 수 있다. 만약 성공한다면, 여러분은 Dynamic Programming을 이해하고 사용한 것이라 할 수 있다.