[알고리즘] 동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming)은 코딩 테스트를 준비하는 사람이라면 반드시 알고 있어야 할 알고리즘 기법이다.

1. 더 작은 size의 문제를 푼다.
2. 푼 문제의 해답을 저장해두고, 필요할 때마다 가져다 쓴다.
3. 이를 이용해 더 큰 문제의 해답을 도출한다.

DP 로 줄여서 부르며, 1차원 배열, 딕셔너리, 트리 등 다양한 형태를 이용하여 기록하지만 가장 많이 쓰는 형태는 2차원 배열이다. 과거의 계산 결과를 저장하여 중복 계산을 피하고 전체 문제의 계산량을 줄이는 것이 핵심이다.

DP는 Divide and Conquer(분할 정복)와 유사하게 문제를 더 작은 문제로 나누어 해결 한다. 하지만 분할 정복은 같은 부분 문제를 여러 번 계산할 수 있는 반면, DP는 이미 계산한 결과를 저장해두고 필요할 때마다 꺼내서 사용 한다.

DP의 2가지 구현 방식

1. Bottom-Up(반복문 + 테이블 채우기)

• 작은 문제부터 차근차근 표를 채워가며 최종 답을 도출한다.
• 2차원 배열에 기록하는 방식을 많이 사용한다.
• DP의 기본 논리이다.

2. Top-Down(재귀 + 메모이제이션)

• 문제를 재귀적으로 풀되, 이미 계산한 값은 저장해두고 재사용한다(메모이제이션).
• 구현이 직관적이지만, 재귀 호출 스택을 많이 사용한다.
• 예시: 피보나치 수열(f(n) = f(n - 1) + f(n - 2))

재귀보다는 점화식을 찾아서 반복문을 통해 테이블을 채우고, 문제의 최종 해답을 구하는 방식이 많이 사용된다. 다만 2가지 난관이 존재한다. 바로 문제를 DP로 풀 수 있는지 판단해야 한다는 것과 점화식을 세워야 한다는 것이다. 현재 size의 문제를 풀기 위해서 이전 size의 어떤 답들을 참조해서 계산하는 구조인지 파악해야 한다.

뭔가 붕 뜬다고 느껴질 수 있지만, DP로 풀지 말지 결정하는 기준(Principle of Optimality)은 의외로 간단 명료하다. 어떤 문제의 instance에 대한 최적해에 좀 더 작은 size에 대한 instance의 최적해가 모두 포함되어 있으면 된다.

예를 들어, i -> j를 최단 경로로 가야 할 때, 중간에 k라는 지점을 거친다고 해보자. 이 경우에 i -> k로 가는 최단 경로는 i -> j의 최단 경로에 반드시 포함되어 있을 것이다. 느낌이 직관적으로 꽂힌다면 이해가 잘된 것이다.

예시: 이항 계수(Binomial Coefficient)

점화식이 주어져 있는 쉬운 예제를 통해서 다이나믹 프로그래밍에 대한 이해도를 더 높여 보자.

이항 계수의 정의는 다음과 같다.

C(n, k) = n! / ((n - k)! * k!) (0 <= k <= n)

어떤 이항 계수를 구할 때 이 식을 그대로 계산하는 것이 아니다. 파스칼의 삼각형에 의한 점화식을 기반으로 다음과 같이 구한다.

C(n, k) = C(n - 1, k - 1) + C(n - 1, k) (0 < k < n), (C(n, 0) = C(n, n) = 1)

k를 고를 때와 고르지 않았을 때에 대한 경우라고 생각하면 이해가 쉽다. 이제 이 점화식을 코드로 구현하여 답을 도출해보자.

[C++]

메모이제이션 없이 순수 재귀로 구현할 때

int bin(int n, int k) {
    if (k == 0 || n == k) {
        return 1;
    }

    return bin(n - 1, k - 1) + bin(n - 1, k);
}

별 생각 안 해도 쉽게 구현할 수 있다. 하지만 이 방식은 중복 계산이 매우 많다.

Top-Down(재귀 + 메모이제이션)

static int memo[n + 1][k + 1];

int bin(int n, int k) {
    if (k == 0 || n == k) {
        return 1;
    }

    if (memo[n][k] != 0) {
        return memo[n][k];
    }

    return memo[n][k] = bin(n - 1, k - 1) + bin(n - 1, k);
}

계산된 결과를 저장해둠으로써, 중복 계산을 없앨 수 있다.

Bottom-Up(반복문 + 테이블 채우기)

static int B[n + 1][k + 1];

int bin(int n, int k) {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= min(i, k); j++) {
            if (j == 0 || i == j) {
                B[i][j] = 1;
            }
            else {
                B[i][j] = B[i - 1][j - 1] + B[i - 1][j];
            }
        }
    }

    return B[n][k];
}

2차원 배열 B에 C(i, j)의 모든 값을 저장하고, 이를 이용하여 원하는 결과를 구한다.

시간 복잡도

DP에서 Basic Operation은 반복이 제일 많이 되는 부분이다. n * k 크기의 2차원 배열을 채우면서 n번 반복, k번 반복이 이뤄지므로 시간 복잡도는 Θ(nk)이다.

마무리

DP는 재귀보다 반복문 사용이 일반적이며, 내부적으로 2차원 배열을 많이 이용한다. 필요한 초기값을 올바르게 설정하고, 참조하는 값이 먼저 계산되도록 계산 순서를 잘 지정해야 한다.