[Algorithm] 동적 계획법(DP)

1. 개요

동적 계획법은 영어로 DP(Dynamic Programming)라고 부른다. 큰 문제를 작은 문제로 나눠서 풀기 위한 알고리즘으로 연산의 결과를 캐시에 저장하여 재활용 함으로써 중복되는 연산을 단 한 번씩만 수행한다. 따라서 프로그램의 실행 속도를 향상시킬 수 있다.

2. 동적 계획법의 조건

동적 계획법은 Overlapping Subproblem과 Optimal Substructure라는 두 가지 조건을 모두 만족해야 한다.

2-1. Overlapping Subproblem

문제를 작은 문제로 쪼갤 수 있고, 원래의 문제와 쪼갠 문제를 같은 방법으로 풀 수 있어야 한다.

2-2. Optimal Substructure

문제의 정답을 작은 문제의 정답에서 구할 수 있어야 하고, 한 문제의 정답은 크기에 상관없이 일정해야 한다.

3. 메모이제이션(Memoization)

동적 계획법은 연산의 결과를 캐시에 저장해 놓고, 필요할 때 재활용하므로 중복되는 연산을 단 한번씩만 수행할 수 있다. 연산의 결과를 보통은 배열에 저장하는데, 이를 메모이제이션(Memoization)이라고 한다.

3-1. 일반적인 피보나치 수

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

3-2. 메모이제이션을 이용한 피보나치 수

int d[10];
 
int fibo(int n) {
    if (n <= 1) return n;
    if (d[n] > 0) return d[n];
    return d[n] = fibo(n - 1) + fibo(n - 2);
}

4. 구현 방법

동적 계획법의 구현은 Top-Down, Bottom-Up 두 가지 방법이 있다.

4-1. Top-Down

큰 문제를 작은 문제로 나눠서 푸는 방법으로, 재귀로 구현한다.

int d[10];
 
int fibo(int n) {
    if (n <= 1) return n;
    if (d[n] > 0) return d[n];
    return d[n] = fibo(n - 1) + fibo(n - 2);
}

4-2. Bottom-Up

작은 문제부터 차례대로 푸는 방법으로, 반복문으로 구현한다.

int d[10];
 
int fibo(int n) {
    d[0] = 0; d[1] = 1;
    for (int i = 2; i <= n; ++i) {
        d[i] = d[i - 1] + d[i - 2];
    }
    return d[n];
}