Dynamic Programming

상위 문서: 알고리즘 설계와 분석

개요

동적 프로그래밍(Dynamic Programming)은 좌우 순서로 배열된 문제들에 대한 최적화 문제를 효율적으로 푸는 방법이다. 동적 프로그래밍의 핵심적인 아이디어는 복잡한 문제를 작은 하위 문제(subproblem) 로 나누고, 중복 계산을 피하기 위해 이전 결과를 저장(memoization)하는 것이다. 이때 동적 프로그래밍은 재귀적으로 구현한다는 것을 의미하지 않는다. 동적 프로그램의 본질은 어디까지나:

1. 중복되는 하위 문제(Overlapping Subproblems): 예를 들면, 피보나치에서 fib(3)을 여러 번 계산하지 않는 것이 있다.
2. 최적 부분 구조(Optimal Substructure): 큰 문제의 최적해가 작은 문제의 최적해들로 구성되는 것이다.

따라서 DP를 구현하는 방식은 아래와 같이 두 가지로 나뉜다:

1. Top-Down(Memoization): 큰 문제에서 출발해 재귀를 통해 하위 문제를 호출하며, 이미 계산된 값은 저장하여 활용한다.
2. Bottom-Up(Tabulation): 가장 작은 하위 문제부터 순서대로 반복문으로 해결하며, 결과를 테이블에 저장한다.

동적 프로그래밍은 완전탐색(Exhaustive Search) 방식에 같이 사용된다. 완전 탐색 기법은 모든 가능한 해를 탐색하므로 항상 정답은 구하지만 비효율적이지만 동적프로그램과 같이 응용하여, 중복 계산을 제거하여 효율을 높일 수 있다. 이를 이용한 대표적인 알고리즘으로는 Floyd’s Algorithm이 있다.

Recurrence Relations

점화식(Recurrence Relation)은 어떤 수열을 “이전 항들로 정의하는 식”이다. 즉, "자기 자신을 기반으로 정의된 함수"이다. 예를 들면, 아래와 같은 식이 있다:

$a_n=a_{n-1}+1,a_1=1\Rightarrow a_n=n$
$a_n=2a_{n-1},a_1=2\Rightarrow a_n=2^n$
$a_n=n{a}_{n-1},a_1=1\Rightarrow a_n=n!$

이와 같이 점화식을 통해 문제의 구조를 반복되는 관계로 표현함으로서 프로그램이 재귀적으로 계산할 수 있다. 즉, 동적 프로그래밍은 이러한 점화식을 효율적으로 계산하기 위해 부분 결과를 저장하는 기법이다.

Fibonacci Numbers

해당 문단에서는 동적 프로그래밍 활용의 대표적인 예시들 중의 하나인 피보나치 수열을 통해서 동적 프로그래밍의 구현 방법에 대해 알아보는 것을 목표로 한다.

Intuitive Version

피보나치 수열의 점화식 정의는 아래와 같다:

$F_n=F_{n-1}+F_{n-2},F_0=0,F_1=1$

이를 구현하기 위한 기본적인 방법은 아래와 같다:

long fib_r(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib_r(n-1) + fib_r(n-2);
}

이는 직관적으로 구현된 동적 프로그래밍이지만, 동일한 값을 반복해서 계산하는 비효율이 있다. Figure 1에서 보이는 바와 같이 fib(6)를 계산하려면 fib(5)와 fib(4)이 필요한데, fib(5) 안에서도 다시 fib(4)을 계산한다. 피보나치 수의 성장 비율은 황금비($\varphi$)로 수렴하며, 이에 따라 입력이 n일 때 재귀 호출은 $n^{1.6}$번 정도 발생한다. 즉, 단순 재귀는 계산이 폭발적으로 늘어나 너무 느리다는 결론을 얻을 수 있다.

Memoization(Top-Down)

Memoization은 계산한 결과를 저장(cache) 해서 다시 계산하지 않게 만드는 기법이다. 이는 아래와 같이 구현된다:

#define MAXN 92
#define UNKNOWN -1
long f[MAXN+1];

long fib_c(int n) {
    if (f[n] == UNKNOWN) {
        f[n] = fib_c(n-1) + fib_c(n-2);
    }
    return f[n];
}

위 코드에서 f[n] 배열은 캐시 기능을 하며, UNKNOWN 값(-1)은 아직 계산되지 않은 상태를 의미한다. 이를 통해서 한 번 계산한 피보나치 수는 저장하여 중복 계산을 방지한다. 재귀 구조에 저장소를 추가한 형태를 top-down 방식의 동적 프로그래밍이라고 한다. 아래는 위의 코드를 실행하기 위해서 f 배열을 초기화한 뒤 fib_c()를 호출하는 드라이버 함수이다:

long fib_c_driver(int n) {
    int i;
    f[0] = 0;
    f[1] = 1;
    for (i = 2; i <= n; i++) {
        f[i] = UNKNOWN;
    }
    return fib_c(n);
}

이는 O(n)의 시간 복잡도를 가지므로, 효율적으로 구현되었다고 할 수 있다.

Down-Top Dynamic Programming

Down-Top 동적 프로그래밍은 가장 작은 하위 문제부터 차근차근 해결하면서, 그 결과를 테이블(table)에 저장하고 큰 문제의 답을 점진적으로 만들어가는 방식이다. 이 방식은 메모리를 더 사용하는 대신, 반복문을 사용하여 속도를 더욱 획기적으로 개선할 수 있다는 장점이 있다. 이는 아래와 같이 구현된다:

long fib_dp(int n) {
    int i;
    long f[MAXN+1];
    f[0] = 0;
    f[1] = 1;
    for (i = 2; i <= n; i++) {
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

이는 시간 복잡도와 공간 복잡도가 모두 O(n)으로, 매우 효율적으로 구현되었다.

Binomial Coefficients

이항 계수(Binomial Coefficients)는 동적 프로그래밍의 고전적인 응용 중 하나이다. 이항 계수는 수학적으로 아래와 같이 정의된다:

$(\genfrac{}{}{0ex}{}{n}{k})=$ "n개 중에서 k개를 선택하는 방법의 수"

이항 계수는 흔히 조합(combination)이라고 불리며, 다양한 분야에 활용된다. 예를 들어 n명의 사람 중 k명을 뽑는 경우의 수이나, n$\times$m 격자의 왼쪽 위에서 오른쪽 아래까지, 오른쪽 또는 아래로만 이동할 수 있을 때 가능한 경로의 수를 구할 때 사용된다. 이 외에도 경로 문제, 선택 문제, 확률 계산 등 매우 다양한 문제에 등장한다.

이항 계수는 동적 프로그래밍의 전형적인 예시 중 하나이다. 왜냐하면 이항 계수는 반복되는 하위 문제 구조를 갖고 있기 때문이다. 이항 계수는 아래와 같이 계산된다:

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{(n-k)!k!}$

즉, 팩토리얼을 이용하여 직접 계산할 수 있다. 하지만 이는 중간 계산에서 오버플로(overflow)가 발생한 우려가 있다. 예를 들어, $20!=2,432,902,008,176,640,000$이므로 중간 계산이 너무 커져서 자료형이 감당하지 못한다. 따라서 직접 팩토리얼 계산보다는 점화식을 이용하는 방법이 더 안전하고 효율적이다.

Pascal’s Triangle

파스칼의 삼각형은 figure 2와 같은 형태를 가지고 있는 수의 배치인데, 이항 계수를 삼각형 모양으로 배열한 것이다. 파스칼의 삼각형의 배치 규칙은 그 바로 위의 두 수의 합이다. 이는 아래와 같은 관계를 시각적으로 표현한 것이다:

$>(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n-1}{k-1})+(\genfrac{}{}{0ex}{}{n-1}{k})$

바로 위 식의 파스칼의 점화식이다. 이를 직관적으로 표현하면, n번째 원소를 포함하는 경우의 수 $(\genfrac{}{}{0ex}{}{n}{k-1})$와 n번째 원소를 포함하지 않는 경우의 수 $(\genfrac{}{}{0ex}{}{n}{k-1})$를 합치면 n개의 원소 중에서 k개를 선택하는 경우의 수가 된다는 것이다. 이 방식의 장점은 팩토리얼 계산이 필요 없으며, 단순 덧셈 연산으로 해결 가능하므로 동적 프로그래밍 적용에 매우 적합하다는 것이다.

이를 활용하여, 이항 관계에 대한 기저 조건(base case)을 분석하면 아래와 같다:

1. $(\genfrac{}{}{0ex}{}{n}{0})=1$: 아무 것도 고르지 않는 경우는 항상 1가지 (공집합)
2. $(\genfrac{}{}{0ex}{}{n}{n})=1$: 모든 원소를 고르는 경우도 항상 1가지 (전체 집합)

즉, 이항 계수에 대한 점화식은 아래와 같이 구해진다:

$(\genfrac{}{}{0ex}{}{n}{k})=\{\begin{array}{ll}1,& ifk=0ork=n\\ (\genfrac{}{}{0ex}{}{n-1}{k-1})+(\genfrac{}{}{0ex}{}{n-1}{k}),& otherwise\end{array}$

Binomial Coefficients Implementation

아래는 위의 점화식을 C코드로 표현한 것이다:

long binomial_coefficient(int n, int k) {
    int i, j;
    long bc[MAXN+1][MAXN+1];

    // base cases
    for (i = 0; i <= n; i++)
        bc[i][0] = 1;
    for (j = 0; j <= n; j++)
        bc[j][j] = 1;

    // fill DP table using Pascal’s recurrence
    for (i = 2; i <= n; i++) {
        for (j = 1; j < i; j++) {
            bc[i][j] = bc[i-1][j-1] + bc[i-1][j];
        }
    }

    return bc[n][k];
}