콘텐츠로 이동

동적 계획법 소개

동적 계획법의 핵심은 반복 계산을 피하는 것입니다. 동적 계획법 문제는 재귀로 자연스럽게 풀리는 경우가 많습니다. 이런 경우에는 먼저 재귀 풀이를 작성한 다음, 반복되는 상태를 조회 테이블에 저장하는 것이 가장 쉽습니다. 이 과정을 메모이제이션(memoization)을 이용한 하향식(top-down) 동적 계획법이라고 합니다. 이는 memorization이 아니라 (메모장에 적어 두는 것처럼) "memoization"이라고 읽습니다.

이 과정의 가장 기본적이고 고전적인 예 중 하나가 피보나치 수열입니다. 피보나치 수열의 재귀식은 $f(n) = f(n-1) + f(n-2)$이며, 여기서 $n \ge 2$이고 $f(0)=0$, $f(1)=1$입니다. C++에서는 이를 다음과 같이 표현할 수 있습니다:

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

이 재귀 함수의 실행 시간은 지수적이며, 대략 $O(2^n)$입니다. 함수 호출 하나( $f(n)$ )가 비슷한 크기의 함수 호출 2개($f(n-1)$과 $f(n-2)$ )를 발생시키기 때문입니다.

동적 계획법(메모이제이션)으로 피보나치 계산 속도 높이기

현재 우리의 재귀 함수는 피보나치 수를 지수 시간에 계산합니다. 이는 문제가 감당하기 어려워지기 전까지는 작은 입력값만 처리할 수 있다는 뜻입니다. 예를 들어 $f(29)$는 100만 번이 넘는 함수 호출을 발생시킵니다!

속도를 높이기 위해, 부분 문제의 개수가 $O(n)$개뿐이라는 점에 주목합니다. 즉, $f(n)$을 계산하려면 $f(n-1),f(n-2), \dots ,f(0)$만 알면 됩니다. 따라서 이 부분 문제들을 다시 계산하는 대신, 한 번만 풀고 그 결과를 조회 테이블에 저장합니다. 이후의 호출은 이 조회 테이블을 사용하여 즉시 결과를 반환하므로, 지수적인 작업이 사라집니다!

각 재귀 호출은 조회 테이블을 확인하여 해당 값이 이미 계산되었는지 검사합니다. 이 작업은 $O(1)$ 시간에 수행됩니다. 이전에 계산한 적이 있다면 그 결과를 반환하고, 그렇지 않다면 평소대로 함수를 계산합니다. 전체 실행 시간은 $O(n)$입니다. 이는 이전의 지수 시간 알고리즘에 비해 엄청난 개선입니다!

const int MAXN = 100;
bool found[MAXN];
int memo[MAXN];

int f(int n) {
    if (found[n]) return memo[n];
    if (n == 0) return 0;
    if (n == 1) return 1;

    found[n] = true;
    return memo[n] = f(n - 1) + f(n - 2);
}

새로운 메모이제이션 재귀 함수를 사용하면, 예전에는 100만 번이 넘는 호출을 발생시키던 $f(29)$가 이제 단 57번의 호출만 발생시키며, 함수 호출이 거의 20,000배 줄어듭니다! 아이러니하게도 이제는 자료형이 제약이 됩니다. $f(46)$은 부호 있는 32비트 정수에 담을 수 있는 마지막 피보나치 수입니다.

일반적으로는 가능하다면 상태를 배열에 저장하려고 합니다. 오버헤드가 최소이면서 조회 시간이 $O(1)$이기 때문입니다. 하지만 더 일반적으로는 원하는 어떤 방식으로든 상태를 저장할 수 있습니다. 다른 예로는 이진 탐색 트리(C++의 map)나 해시 테이블(C++의 unordered_map)이 있습니다.

그 예시는 다음과 같습니다:

unordered_map<int, int> memo;
int f(int n) {
    if (memo.count(n)) return memo[n];
    if (n == 0) return 0;
    if (n == 1) return 1;

    return memo[n] = f(n - 1) + f(n - 2);
}

또는 비슷하게 다음과 같이 할 수 있습니다:

map<int, int> memo;
int f(int n) {
    if (memo.count(n)) return memo[n];
    if (n == 0) return 0;
    if (n == 1) return 1;

    return memo[n] = f(n - 1) + f(n - 2);
}

일반적인 메모이제이션 재귀 함수에서는 이 두 방법 모두 배열 기반 방법보다 거의 항상 느립니다. 이러한 대안적인 상태 저장 방법은 주로 벡터나 문자열을 상태 공간의 일부로 저장할 때 유용합니다.

메모이제이션을 적용한 재귀 함수의 실행 시간을 쉽게 분석하는 방법은 다음과 같습니다:

$$\text{work per subproblem} * \text{number of subproblems}$$

상태를 저장하는 데 이진 탐색 트리(C++의 map)를 사용하면 엄밀히 말해 $O(n \log n)$이 됩니다. 각 조회와 삽입에 $O(\log n)$의 작업이 필요하고, 서로 다른 부분 문제가 $O(n)$개이므로 전체 시간은 $O(n \log n)$입니다.

이 방식은 쿼리 값으로 함수를 호출하면 계산이 위(쿼리한 값)에서 시작하여 아래(재귀의 기저 사례)로 내려가고, 그 과정에서 메모이제이션을 통해 지름길을 만들기 때문에 하향식(top-down)이라고 부릅니다.

상향식 동적 계획법

지금까지는 메모이제이션을 사용하는 하향식 동적 계획법만 살펴보았습니다. 하지만 상향식 동적 계획법으로도 문제를 풀 수 있습니다. 상향식은 하향식과 정반대입니다. 아래쪽(재귀의 기저 사례)에서 시작하여 점점 더 많은 값으로 확장해 나갑니다.

피보나치 수에 대한 상향식 방법을 만들려면 먼저 배열에 기저 사례를 초기화합니다. 그런 다음 배열에 재귀적 정의를 그대로 적용하면 됩니다:

const int MAXN = 100;
int fib[MAXN];

int f(int n) {
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++) fib[i] = fib[i - 1] + fib[i - 2];

    return fib[n];
}

물론 위와 같이 작성하면 두 가지 이유로 다소 비효율적입니다. 첫째, 함수를 두 번 이상 호출하면 같은 작업을 반복하게 됩니다. 둘째, 현재 원소를 계산하는 데는 바로 앞의 두 값만 있으면 됩니다. 따라서 메모리를 $O(n)$에서 $O(1)$로 줄일 수 있습니다.

$O(1)$ 메모리를 사용하는 피보나치의 상향식 동적 계획법 풀이는 예를 들어 다음과 같습니다:

const int MAX_SAVE = 3;
int fib[MAX_SAVE];

int f(int n) {
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++)
        fib[i % MAX_SAVE] = fib[(i - 1) % MAX_SAVE] + fib[(i - 2) % MAX_SAVE];

    return fib[n % MAX_SAVE];
}

상수를 MAXN에서 MAX_SAVE로 바꾸었다는 점에 주목하십시오. 접근해야 하는 원소의 총개수가 3개뿐이기 때문입니다. 이제 입력 크기에 따라 늘어나지 않으므로 정의상 $O(1)$ 메모리입니다. 또한 필요한 값만 유지하기 위해 흔히 쓰이는 기법(나머지 연산자 사용)을 활용합니다.

이것이 전부입니다. 이것이 동적 계획법의 기본입니다: 이미 한 작업을 반복하지 마십시오.

동적 계획법 실력을 늘리는 요령 중 하나는 고전적인 예제를 공부하는 것입니다.

고전적인 동적 계획법 문제

이름 설명/예시
0-1 배낭 문제 무게가 $w_i$이고 가치가 $v_i$인 물건 $N$개와 최대 무게 $W$가 주어질 때, $\sum_{i=1}^{k} w_i \le W$를 만족하면서 크기가 $k$($1 \le k \le N$)인 물건의 각 부분집합에 대해 $\sum_{i=1}^{k} v_i$의 최댓값은 얼마입니까?
부분집합의 합 정수 $N$개와 $T$가 주어질 때, 주어진 집합의 부분집합 중 원소의 합이 $T$가 되는 것이 존재하는지 판별하십시오.
최장 증가 부분 수열(LIS) 정수 $N$개로 이루어진 배열이 주어집니다. 배열에서 LIS, 즉 모든 원소가 바로 앞 원소보다 큰 부분 수열을 구하십시오.
2차원 배열에서 경로의 수 세기 $N$과 $M$이 주어질 때, 각 단계에서 $(i,j)$에서 $(i+1,j)$ 또는 $(i,j+1)$로 이동하여 $(1,1)$에서 $(N, M)$까지 가는 서로 다른 모든 경로의 수를 세십시오.
최장 공통 부분 수열 문자열 $s$와 $t$가 주어집니다. $s$와 $t$ 모두의 부분 수열인 가장 긴 문자열의 길이를 구하십시오.
방향 비순환 그래프(DAG)에서의 최장 경로 방향 비순환 그래프(DAG)에서 최장 경로를 찾습니다.
최장 회문 부분 수열 주어진 문자열의 최장 회문 부분 수열(LPS)을 찾습니다.
막대 자르기 길이가 $n$ 단위인 막대와, cuts[i]가 잘라야 하는 위치를 나타내는 정수 배열 cuts가 주어집니다. 한 번 자르는 데 드는 비용은 잘리는 막대의 길이입니다. 자르는 데 드는 최소 총비용은 얼마입니까.
편집 거리 두 문자열 사이의 편집 거리는 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 연산 횟수입니다. 연산은 ["Add", "Remove", "Replace"]입니다

물론 가장 중요한 비결은 연습입니다.

연습 문제

DP 대회