동적계획법(Dynamic Programming) 입문하기

DP(Dynamic Programming)?

DP는 문제를 최적화를 할 때, 사용을 주로 합니다. 불필요하게 다시 계산을 하는 일을 막아 주는 기능을 합니다.

예를 들어, 가장 기본 적인 Fibonacci(피보나치) 숫자를 구하는 경우를 생각해 봅시다. 여기서 가장 단순하게 생각할 수 있는 코드는 피보나치는

f(n) = f(n-1) + f(n-2) 즉 n번째 피보나치 숫자는 n-1번 째 피보나치 수와 n-2번 째 피보나치 수의 합과 같다 입니다.

이를 재귀 함수로 나타내면

int nth_fibonacci(int n) {
    if(n <= 1)
        return 1;
    else
        return nth_fibonacci(n-1) + nth_fibonacci(n-2);
}

입니다. 하지만 이와 같은 경우 치명적인 문제점이 있습니다. 10에 가까운 숫자를 가지고 직접 저 알고리즘을 나무 형태로 그리면서 따라가 보시기 바랍니다.

그럼 문제점을 찾으셨을 겁니다. 이미 무슨 값인지 계산했던 피보나치 수를 다시 계산을 하는 것을 보게 됩니다. 그래서 이 같은 경우 항상 O(2^n) 이라는 어마어마한 연산을 하여야 합니다.

이 경우를 최적화할 수 있는 기법이 DP입니다. 그리고 DP에는 두 가지 대표적인 구현 방법이 있습니다.

메모이제이션을 이용한 DP

메모이제이션을 이용한 DP는 간단하게 말하면 이미 계산한 값은 기록을 해놔서 다시는 다시 계산을 안하도록 하는 것 입니다. 위의 코드에서 살짝만 바꾸면 최적화가 됩니다.

int D[100] // 기록해 두는 배열

int nth_fibonacci(int n) {

    int &ret = D[n];
    if(ret != 0) return ret;

    if(n <= 1) // 첫 번째와 두 번째 피보나치는 1
        return 1;
    else
        return ret = (nth_fibonacci(n-1) + nth_fibonacci(n-2));
}

위 코드를 보면 다음 줄들이 변경이 되었습니다.

    int D[100] // 1

    int &ret = D[n]; // 2
    if(ret != 0) return ret; // 3

    return ret = (nth_fibonacci(n-1) + nth_fibonacci(n-2)); // 4
}

우선 1번은 기록을 해놓기 위해서 선언한 배열입니다. 2번은 C++에서 레퍼런스입니다. 단순히 변수의 값을 카피하는 것이 아니라, 변수의 주소 자체를 카피를 해서 ret이 변하면 D[n]의 값도 바뀌도록 해주는 것 입니다. 그리고 3번은 이미 계산을 한 상태면 D[n]의 값은 0이 아니므로 0이 아니면 이미 계산해 둔 값을 반환하도록 하는 것 입니다. 그리고 4번이 중요한데, 4번은 재귀로 밑에 값을 계산을 하고 그 값을 ret에 저장하는 것 입니다. 이렇게 코드를 짜면 겹치는 부분은 다시 연산하지 않게 됩니다.

이 경우에는 최악 경우에도 선언을 해둔 배열의 크기만큼만 연산을 합니다. 그래서 O(n) // n은 배열의 크기 와 같은 시간 복잡도를 같습니다.

반복문을 이용한 DP

하지만 메모이제이션을 활용한 DP를 활용하지 못할 때도 있습니다. 함수의 깊이가 너무 깊어져서 Stack Overflow가 나거나, 반복문을 이용하는 것이 훨씬 간편할 때 입니다.

메모이제이션을 이용한 DP에서는 위에서 아래(Top-Down)로 진행을 했다면 반복문을 이용한 DP는 아래서 위로(Bottom-Up) 방식을 사용합니다.

int D[100] // 기록해 두는 배열

int nth_fibonacci(int n) {
    int i;
    D[0] = D[1] = 1; // 첫 번째와 두 번째 피보나치는 1
    for(i = 2; i <= n; i++) {
        D[i] = D[i-1] + D[i-2];
    }
    return D[n];
}

이렇게 어떻게 보면 메모이제이션 예제보다 더욱 간단하게 구현이 되었습니다. 그리고 함수를 계속 호출하지 않아서 메모리를 절약할 수도 있습니다. 실제로 약간 빠르기도 합니다.

마치며

반복문을 이용한 DP에서 n번째 피보나치 수를 구할 때, 기록하는 배열을 모두 잡을 필요가 없습니다. 변수 3개를 한 스텝마다 갱신을 하면서 구해서 메모리를 더욱 절약할 수 있습니다.

그리고 본격적인 DP문제는 다음 글부터 다루도록 하겠습니다.