다이나믹 프로그래밍

다이나믹 프로그래밍은 “큰 문제를 작은 문제로 나누어 푸는 알고리즘”이다. 하지만 단순히 나누는 것이 다가 아니라, 두가지 조건을 만족해야만 다이나믹 프로그래밍으로 문제를 푼다고 할 수 있는데, 그 두가지는

 

• Overlapping subproblem (겹치는 부분 문제)
• Optimal substructure (최적 부분 구조)

이다.

Overlapping subproblem

겹치는 부분 문제란, “큰 문제를 작은 문제로 쪼갤 수” 있어야 하고, “큰 문제와 작은 문제를 같은 방법으로 풀 수” 있어야 한다는 것이다. 피보나치 수를 예로 들자면

 

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)

 

이런 식에서 f(n)을 구하는 문제는 다시 f(n-1)을 구하는 문제와 f(n-2)를 구하는 문제로 나누어진다. 상대적으로 작은 문제를 풀게 되는 것이다. 또한 같은 f( )를
구하는 것이므로 같은 방법으로 문제를 푼다고 할 수 있다.

Optimal substructure

최적 부분 구조란, 큰 문제의 정답을 작은 문제에서 구할 수 있어야 한다는 것이다.

위 피보나치 수의 식에서 f(n-1)은 다시 f(n-2) + f(n-3)이 되고, 이 때 f(n-2)가 중복이 된다. 작은 문제의 답을 “재활용”하여 큰 문제의 답을 구할 수 있는 것이다. 이 때, 후술할 메모이제이션이 사용된다. 그리고 최적 부분 구조를 만족한다면, 문제에 크기에 상관없이 어떤 한 문제의 답은 일정하다.

Memoization

다이나믹 프로그래밍에서 빠질 수 없는 것이 바로 메모이제이션이다. 메모이제이션은 말 그대로 “메모”하는 기법으로 부분 문제의 해를 메모하여 다음에 재사용하겠다는 것이다. 이 방식을 이용하면 겹치는 부분 문제를 여러번 계산할 필요 없이 자원을 아낄 수 있다.

 

* 추가 : Bottom-up 방식에서 사용하는 방법은 타뷸레이션(Tabulation)이라는 단어가 따로 존재한다고 한다. 메모이제이션은 Top-down 방식.

문제 접근 방법

다이나믹 프로그래밍의 접근 방법은 두가지로 나눌 수 있는데, Top-down 방식과 Bottom-up 방식이다.

Top-down

Top-down은 큰 문제를 쪼개가면서 해를 구하는 것이다. 주로 “재귀”를 이용해서 문제를 푼다. Top-down 방식을 사용하여 피보나치 수를 구하는 코드를 짜보자.

int dp[100];
int fibonacci(int n) {
    if(n <= 1) {
        return n;
    } else {
        if(dp[n] > 0) {
            return dp[n];
        }
        dp[n] = fibonacci(n-1) + fibonacci(n-2);
        return dp[n];
    }
}     

Bottom-up

Bottom-up은 가장 작은 문제부터 해를 구하여 원래 문제의 해에 도달하는 것이다. 주로 “반복문”을 이용해서 문제를 푼다. Bottom-up으로 문제를 풀면 다음과 같다.

int dp[100];
int fibonacci(int n) {
    dp[0] = 0;
    dp[1] = 1;
 
    for(int i = 2 ; i <= n ; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}    

 

다이나믹 프로그래밍은 결국 내가 구하고자 하는 부분을 어떻게 메모할 지, 또 점화식을 어떻게 세울지에 따라 실력이 판가름 난다고 할 수 있다. 결국 많이 해보는 것이 중요하겠다.