[알고리즘] 동적 계획법

분할정복

동적 계획법

동적 계획법(Dynamic Programming)은 복잡한 문제를 부분 문제들로 나누어 해결할 때, 메모이제이션을 통해 효율적으로 문제를 해결하는 기법이다. 동적 계획법은 대개 다음 두 가지 속성을 가진 문제에 대해 사용할 수 있다.

중복되는 부분 문제: 문제를 나누어 풀 때 같은 문제가 반복적으로 해결된다.
최적 부분 구조: 문제의 최적해가 그 부분 문제의 최적해로부터 구해진다.

글로만 설명하면 이해하기 어려우니 예제를 통해 살펴보자.

중복되는 부분 문제

피보나치 수열은 F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2) (n >= 2)로 정의되는 수열이다. 이를 재귀적으로 구현하면 다음과 같다.

이를 그대로 재귀함수로 구현하면 다음과 같다.

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

위 코드에서 fibonacci(5)를 호출하면 결과적으로 fibonacci(2)를 3번씩이나 호출하게 된다.

overlapping-subproblems

이렇게 같은 부분 문제를 반복적으로 호출하는 것을 중복되는 부분 문제라고 한다. n이 커지면 커질수록 중복되는 부분 문제의 수가 기하급수적으로 증가하고, 똑같은 부분 문제를 풀기 위해 똑같은 재귀 호출 과정을 반복하게 된다. 이런 현상을 방지하기 위해 한번 계산한 부분 문제를 저장해두었다가 다시 계산하지 않도록 하는 것이 메모이제이션이다.

다음 코드는 메모이제이션을 적용한 피보나치 수열의 구현이다.

int cache[100]; // -1로 초기화

int fibonacci2(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (cache[n] != -1) return cache[n];
    return cache[n] = fibonacci2(n - 1) + fibonacci2(n - 2);
}

이는 실제로 속도의 측면에서 엄청난 차이를 보인다. fibonacci 함수는 n이 약 50이 넘어가면 계산이 불가능한 수준이 되지만, fibonacci2 함수는 n이 10,000,000이 넘어가도 1초 이내에 계산이 가능하다.

최적 부분 구조

optimal-substructure

각 칸에 숫자가 써있는 행렬의 왼쪽 위(0, 0)에서부터 오른쪽 아래(n - 1, n - 1)까지 이동할 때, 경로에 있는 숫자의 합을 최대화하는 문제를 생각해보자. (단, 한번에 오른쪽 또는 아래로만 이동할 수 있다.)

이 문제를 풀기 위해 다음과 같은 부분 문제를 정의할 수 있다.

maxpath(i, j): (i, j)에서 (n - 1, n - 1)까지 이동할 때, 경로에 있는 숫자의 합의 최댓값

그러면 다음과 같은 점화식을 세울 수 있다.

maxpath(i, j) = A[i][j] + max(maxpath(i + 1, j), maxpath(i, j + 1))

위 점화식을 메모이제이션을 이용해 구현하면 다음과 같다.

int n;
int A[100][100];
int cache[100][100]; // -1로 초기화

int maxpath(int i, int j) {
    if (i == n - 1 && j == n - 1) return A[i][j];
    if (cache[i][j] != -1) return cache[i][j];
    return cache[i][j] = A[i][j] + max(maxpath(i + 1, j), maxpath(i, j + 1));
}

위 문제를 메모이제이션을 적용하여 효율적으로 풀 수 있었던 이유는 부분 문제를 풀 때 (i, j)까지 어떤 경로로 왔는지에 대한 정보가 (i, j)에서 (n - 1, n - 1)까지의 최적해를 구하는 데에 전혀 영향을 끼치지 않기 때문이다.

이처럼 지금까지 어떤 경로로 부분 문제에 도달했건 간에, 전체 문제의 최적해가 부분 문제의 최적해로부터 구해진다면 이를 최적 부분 구조라고 한다.

동적 계획법을 통해 문제를 풀고자 한다면 최적 부분 구조를 만족하도록 부분 문제를 정의하는 것이 중요하다.

생각해보기

만약 위 문제에서 "숫자 10은 두번 이상 지나갈 수 없다."라는 조건이 추가된다면 어떻게 부분 문제를 정의해야 할까?

배낭 문제

knapsack

배낭 문제는 동적 계획법을 이용해 풀 수 있는 대표적인 문제이다. 문제의 정의는 다음과 같다.

각 물건은 무게와 가치를 가지고 있으며, 배낭에는 넣을 수 있는 최대 무게가 정해져 있다. 이때 배낭에 넣을 수 있는 물건들의 가치의 합의 최댓값은 얼마인가?

이 문제를 풀기 위해 다음과 같은 부분 문제를 정의할 수 있다.

knapsack(i, w): 0번째 물건부터 i번째 물건까지만 고려했을 때, 무게의 합이 w를 넘지 않도록 물건을 골랐을 때의 가치의 합의 최댓값

그러면 다음과 같은 점화식을 세울 수 있다.

knapsack(i, w): 다음 두 값 중 최댓값
- knapsack(i - 1, w) i번째 물건을 넣지 않는 경우
- knapsack(i - 1, w - weight[i]) + value[i] i번째 물건을 넣는 경우 (단, w >= weight[i]일 때만)

이를 동적 계획법을 이용해 구현하면 다음과 같다.

int n;
int weight[100];
int value[100];
int cache[100][100]; // -1로 초기화

int knapsack(int i, int w) {
    if (i == -1) return 0;
    if (cache[i][w] != -1) return cache[i][w];
    int ret = knapsack(i - 1, w);
    if (w >= weight[i]) ret = max(ret, knapsack(i - 1, w - weight[i]) + value[i]);
    return cache[i][w] = ret;
}

LIS: 최대 증가 부분 수열

https://algospot.com/judge/problem/read/LIS

부분 문제

lis(start): S[start]에서 시작하는 증가 부분 수열 중 최대 길이

코드

int n;
int S[500];
int cache[500]; // -1로 초기화

int lis(int start) {
    if (cache[start] != -1) return cache[start];
    int ret = 1;
    for (int next = start + 1; next < n; ++next) {
        if (S[start] < S[next]) ret = max(ret, lis(next) + 1);
    }
    return cache[start] = ret;
}

PI: 원주율 외우기

https://algospot.com/judge/problem/read/PI

부분 문제

pi(start): start부터 시작하는 숫자열을 외우는 데 드는 최소 난이도

코드

int n;
int digits[10000];
int cache[10000]; // -1로 초기화

int difficulty(int start, int end) // start부터 end까지의 난이도, 구현은 생략

int pi(int start) {
    if (start == n) return 0;
    if (cache[start] != -1) return cache[start];
    int ret = INF;
    for (int len = 3; len <= 5; ++len) {
        if (start + len <= n) ret = min(ret, pi(start + len) + difficulty(start, start + len - 1));
    }
    return cache[start] = ret;
}

성균관대학교 | Google Developer Student Clubs