Table of contents

동적계획법은 이름부터 생소하다. 종만북에 따르면 동적계획법을 만든 벨만(벨만포드 알고리즘 창시자)은 단순히 dynamic이라는 단어가 멋있어서 선택했다고 한다(…) 따라서 컴퓨터공학부에서 흔히 쓰이는 dynamic의 의미로 생각하려고 하면 이 알고리즘이 어떤 내용일지 감을 잡을 수 없다. 이런 네이밍 센스에도 불구하고 정말 널리 쓰여서 이렇게 유명한걸 보면 그만큼 강력하고 효과적인 알고리즘이라는 것을 알 수 있다.

동적계획법이란

내게 동적계획법의 의미를 가장 와 닿게 설명할 수 있는 두 단어는 수학적 귀납법과 점화식이다. 동적계획법의 기본 개념을 이해하기 위해 피보나치 수열을 예시로 생각해보자. 피보나치 수열을 점화식으로 쓰면 아래와 같이 나타낼 수 있다.

$ f(n) = f(n-1) + f(n-2) $

이는 코드로 나타내면 다음과 같이 쓸 수 있다.

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

초기조건까지 해주면 다음과 같이 나타낼 수 있다.

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

이렇게 큰 문제( $ f(n) $ )를 작은 문제( $ f(n-1) $ , $ f(n-2) $ )를 이용해서 나타낼 수 있다면, 수학적 귀납법처럼 초기 조건이 옳다면 큰 n에 대해서도 옳은 값을 구할 수 있다. 이와 같은 방법을 동적계획법이라고 한다. 기본 개념은 이렇지만 진정한 동적계획법이라고 부르려면 여기서 발생하는 한 가지 문제를 해결해야 한다. 어떤 문제가 발생하는지 확인하기 위해 $ f(5) $ 를 호출하면 함수가 호출되는 과정이 어떻게 되는지 살펴보자.

함수가 무려 15번이나 불린다. 특히 아래로 갈수록 더 많이 불려서 $ f(1) $ 은 5번이나 불린다. 그리고 조금만 관찰하면 $ n $ 이 늘어날수록 이 불리는 횟수는 지수적으로 증가할 것이라는 걸 추측할 수 있다. 그렇게 되면 $ n $ 이 조금만 커져도 프로그램은 터져버리고 말 것이다.

이렇게 지수적으로 증가하는 이 횟수를 획기적으로 감소시켜보자. 먼저 각 함수가 불리는 순서를 표시해보면 다음과 같다.

여기서 잘 생각해보면 우리는 4번 과정에서 이미 $ f(2) $ 를 구했다. 따라서 이 값을 저장해뒀다면 8번에서 $ f(2) $ 를 구할 때 굳이 $ f(1) $ 과 $ f(0) $ 를 호출하지 않아도 $ f(2) $ 의 값을 알아낼 수 있다. 따라서 우리는 9번과 10번 과정을 생략할 수 있다. 마찬가지로 3번에서 우리는 이미 $ f(3) $ 을 구했다. 따라서 이를 이용하면 11번에서 사용하면 12~15번 과정을 생략할 수 있다.

이처럼 큰 문제를 작은 문제를 활용하여 구하되, 이렇게 구한 값을 저장해서 다음에 또 구해야 할 때 효율적으로 가져다 쓸 수 있게 하는 것이 진정한 동적계획법의 설계이다.

구현 방법

동적계획법의 구현 방식에는 크게 세 가지가 있다. 보통은 두 가지로 많이 분류하는데, 바로 Top-Down 방식이랑 Bottom-Up 방식이다. 나는 여기서 다른 사람들과는 다르게 Bottom-Up 방식도 Collect 방식과 Spread 방식으로 나눠서 총 세 가지라고 분류하는 편이다.

Top-Down 방식

Top-Down 방식은 그대로 직역하면 위에서부터 내려오는 방식으로, 내가 먼저 원하는 값을 부른 다음에 거기서부터 필요한 것들을 수집해나가는 방식이다. 이 방식은 주로 메모이제이션과 재귀함수를 써서 구현한다.

우리가 일반적으로 수학적으로 점화식을 세운 것을 이 방식에서 그대로 사용할 수 있다. 예를 들어 위에서 설명한 피보나치의 점화식인

$ f(n) = f(n-1) + f(n-2) $

을 살펴보면 마찬가지로 $ f(n) $ 을 구하기 위해 $ f(n-1) $ 과 $ f(n-2) $ 를 구하라고 하는 Top-Down 방식이라고 생각할 수 있다. 따라서 이를 이용해 $ f(100) $ 을 구하는 것을 구현하면 아래와 같다.

int d[110];

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

int main() {
    printf("%d",f(100));
}

이 방식은 수학적으로 세운 식 그대로 재귀함수로 구현하고, 이 값을 배열에 저장하는 메모이제이션만 추가하면 되기 때문에 구현이 쉽다는 장점이 있다. 다만 재귀함수라는 것 자체가 함수를 불러오고 하는 과정에서 시간이 걸리기 때문에 재귀함수를 사용하지 않고 반복문으로 처리하는 Bottom-Up 방식에 비해 속도가 조금 느리다. 하지만 시간복잡도는 그대로고 아니고 기껏해야 상수 배 차이니 만약에 Bottom-Up으로 구현하기 어렵거나 헷갈린다면 이 방식으로라도 구현하는 것이 좋다.

Bottom-Up 방식 (Collect)

Bottom-Up은 직역하자면 아래서부터 올라오는 것으로, 바닥부터 차근차근히 계산해내서 내가 목표하는 곳 까지 구해내는 방식이다. 그 중 일반적으로 많이 쓰이는 Collect(정식 용어는 아니고 내가 붙인 이름이다)방식에 대해 알아보자.

말로 설명하는 것 보다 코드를 먼저 보는 것이 이해하기 쉬울 것이다. Bottom-Up 방식은 주로 for문을 사용해서 구현한다. 따라서 일반적으로 재귀로 구현하는 것보다 빠르다.

int d[110];

int main() {
    d[0] = 1;
    d[1] = 1;
    for(int i = 2; i <= 100; i++) {
        d[i] = d[i-1] + d[i-2];
    }
    printf("%d",d[100]);
}

이렇게 바닥부터 차근차근 한 단계씩 올라가서 내가 원하는 값까지 구해내는 방식을 Bottom-Up이라고 한다. 위와 같은 구현은 내가 원하는 값( $ d[i] $ )를 얻기 위해 나보다 작은 값( $ d[i-1]$ , $ d[i-2] $ )로부터 수집하기 때문에 Collect 방식이라고 이름을 붙였다.

이 방식이 가능하려면 지금 위치(i)에 왔을 때 지금의 값( $ d[i] $ )이 수집해야 하는 재료( $ d[i-1] $ , $ d[i-2] $ )가 모두 구해져 있어야 한다는 조건을 만족해야 한다. 피보나치의 경우 변수가 $ i $ 하나뿐이라 $ i $ 가 증가하는 순으로 계산하면 되지만 나중에 변수가 2,3개 들어가거나 일반적인 차원의 배열을 채우는 것이 아닌 그래프나 집합 같은 자료구조에서 동적계획법을 설계하는 경우 이 점에 유념해서 for문을 순회하는 순서를 정해야 한다.

Bottom-Up 방식 (Spread)

Spread 방식은 다른 사람들은 거의 얘기하지 않는 방식이다. 그러나 가끔 이 방식으로 생각해야 더 쉽게 설계되는 경우가 있어서 소개하고자 한다. 위의 두 방식은 내가 원하는 값을 얻기 위해서 어떻게 해야 할까를 생각하면서 코딩했다. 그러나 Spread 방식은 이와 다르게 ‘지금 나의 값이 어디에 영향을 끼칠까`에 대해서 생각한다. 역시 말 보다 코드를 먼저 보는 것이 빠를 것이다.

int d[110];

int main() {
    d[0] = 1;
    for(int i = 0; i <= 99; i++) {
        d[i+1] += d[i];
        d[i+2] += d[i];
    }
    printf("%d",d[100]);
}

피보나치의 점화식을 우변에 있는 $ f(x-1) $ 과 $ f(x-2) $ 의 입장에서 생각해 보면, 어떤 $ f(t) $ 가 영향을 끼치는 값은 $ f(t+1) $ 와 $ f(t+2) $ 라고 할 수 있다. 따라서 내가 $ d[i] $ 값에 도달했을 때 이 값을 $ d[i+1] $ 과 $ d[i+2] $ 에 전파하기 때문에 Spread 방식이라고 이름을 붙였다.

이 방식을 설계할 땐 지금 위치( $ i $ )에 왔을 때 지금의 값( $ d[i] $ )에 전파를 해야 했던 값들( $ d[i-1] $ , $ d[i-2] $ )이 모두 전파를 완료한 상태여야 한다는 조건에 유념해서 for문을 순회하는 순서를 정해야 한다.

Collect 방식과 Spread 방식은 절대적인 상위호환 관계가 있는건 아니고 상황에 따라 어떤게 더 좋을지 달라지는 것 같다. Spread 방식으로 생각하는 것이 익숙하지 않으면 처음엔 어려울 수도 있지만, 나중에 익숙해지면 그래프처럼 특이한 자료구조에서 동적계획법을 해야 할 때 도움이 되는 경우가 많았다.

시간복잡도 분석

동적계획법의 장점 중 하나는 시간복잡도를 분석하기가 쉽다는 점이다. 동적계획법을 할 때 채우는 배열을 보통 동적 테이블(Dynamic table)이라고 부르는데, 시간복잡도를 분석할 때 고려해야하는 최악의 경우에서는 대부분 이 테이블을 꽉 채워야 내가 원하는 값을 얻을 수 있다. 또한 테이블은 점화식에 의해서 채워지니 일반적으로 테이블의 한 칸을 채울 때 걸리는 시간복잡도도 거의 일정하다. 따라서

$ 테이블의 ~ 크기 \times 한 ~ 칸을 ~ 채우는데 ~ 걸리는 ~ 시간 $

을 하면 원하는 시간복잡도를 얻을 수 있다.

비트마스킹 기법

비트마스킹 기법은 독립적으로 존재하긴 하지만, 일반적으로 동적계획법과 같이 쓰이니 같이 설명해보자. 비트마스킹 기법은 집합의 포함 상태를 비트를 사용해서 나타내는 집합이다.

예를 들어서 내가 a, b, c, d, e 다섯 개의 원소가 있는데 이 중에서 a, b, e만 포함된 {a, b, e}를 나타낸다고 해보자. 여기서 포함된 원소를 1, 포함되지 않는 원소를 0으로 표현하면 이는 11001₂라고 할 수 있다. 따라서 이 이진수를 다시 십진수로 바꾸면 25이므로 {a, b, e}와 25가 같다고 할 수 있다. 이렇게 비트를 가지고 놀 경우, 비트연산(&, |, <<, >>)들은 속도가 굉장히 빠른 연산이므로 시간 면에서도 좋다고 할 수 있다.

비트마스킹에서의 연산

x번째 원소 추가

x번째 비트를 1로 바꾸면 되므로 그 비트를 or연산 해주면 된다.

mask |= (1<<x)

x번째 원소 제거

x번째 비트만 0으로 바꿔주면 된다. 다시 생각하면 x번째 원소만 0이고 나머지는 모두 1인 값과 and를 하면 된다.

mask &= !(1<<x)

최소 원소 찾기

이번엔 조금 고급기술로 가보자. 최소원소란 가장 오른쪽의 비트로, 예를 들어 현재 mask가 0110100일 경우 0000100을 찾는 것이다. 우선 코드를 먼저 보자.

mask & (-mask);

음수 연산을 비트적으로 생각하면 2의 보수를 사용하므로 not을 한 다음 1을 더하는 연산이 된다. 오른쪽에서 i번째 비트가 최소 비트라고 하면, not을 하면 i번째 원소는 0이 되고 그 오른쪽에 있는 원소는 모두 1이 된다. 이 상황에서 1을 더하면 다시 i번째 원소는 1이 되고 그 오른쪽에 있는 원소는 0이 된다. 또한 왼쪽에 있는 원소들은 not한 상태에서 변하지 않는다. 따라서 이를 원래 mask와 and를 하면 i번째 원소의 왼쪽은 다 자기 자신과 not을 한 것과 and를 하므로 0이고 오른쪽은 0과 and가 되니 0이 된다. 따라서 i번째 원소만 1로 남아있게 된다.

최소 원소 지우기

위와 비슷한 원리로 작동한다.

mask & (mask - 1)

마찬가지로 오른쪽에서 i번째 비트가 최소 비트라고 하고 생각해보자. 여기서 1을 빼면 i번째 비트는 0이 되고 그 오른쪽 비트들은 모두 1이 된다. 따라서 이 수와 원래 수를 and를 하면 i번째 왼쪽에 있는 비트들은 변하지 않았으므로 그대로 남는다. 또한 i번째 비트와 그 오른쪽 비트는 모두 0이 된다. 따라서 결론적으로는 i번째 비트만 0으로 변한 효과이므로 최소 원소를 지우는 효과가 된다.

모든 부분집합 순회하기

비트연산으로 할 수 있는 연산중 가장 재밌는 게 아닐까 싶다. 우선 코드부터 보자.

for(i = mask; i; i = ((i - 1) & mask)) {
    do something
}

워낙 유명한 코드라 그냥 믿고 써도 되지만 공부도 할 겸 증명을 해보자. 우선 (i - 1) & mask)라는 식에 대해 생각해보자. 위에서 봤듯이 자기 자신에서 1을 빼면 최소 비트가 0이 되고 그 오른쪽에 있는 비트는 모두 0이 된다. 이 상태에서 원래의 mask와 and를 하면 현재 집합 상태에서 최소 원소는 0이 되고, 이보다 오른쪽에 있는 비트는 모두 다시 1이 되고, 왼쪽에 있는 원소는 그대로가 된다. 이 점을 생각하면서 다음 명제에 대해 생각해보자.

오른쪽부터 x개의 원래 1이었던 비트들이 모두 1인 상태면 자신이 가능한 2^x개의 모든 상태를 한 번씩 순회한 후 모두 0으로 된 다음에야 이보다 왼쪽에 있는 비트에 영향을 끼치고서 다시 모두 1이 된다.

이를 수학적 귀납법을 사용해서 증명해보자. 우선 초기조건부터 보자. 맨 오른쪽의 원래 1이었던 비트는 1인 상태에서 시작한다. 그 다음 i = ((i - 1) & mask))를 실행하면 이 비트만 0으로 꺼진다. 이 다음에 i = ((i - 1) & mask))를 실행하면 오른쪽에서 두 번째인 원래 1이었던 비트는 0이 되고 맨 오른쪽의 원래 1이었던 비트는 다시 1이 된다. 따라서 x가 1인 경우에 대해서 위 명제가 만족한다.

이제 임의의 x에 대해서 오른쪽부터 x+1개의 원래 1이었던 비트들이 모두 1인 상태라고 가정하자. 우선 위의 명제에 따라 이 중 오른쪽의 x개가 가능한 2^x개의 모든 상태를 한 번씩 순회한 후 모두 0으로 된다. 그 다음 i = ((i - 1) & mask))을 실행하면 오른쪽에서 x+1번째로 원래 1이었던 비트는 0이 되고 나머지 x개의 비트는 다시 1이 된다. 그러면 다시 오른쪽부터 x개의 원래 1이었던 비트들이 모두 1인 상태이므로 가능한 2^x개의 모든 상태를 한 번씩 순회한 후 모두 0으로 된다.

이 과정을 x+1개의 입장에서 보면 x+1번째 비트가 1일 때 가능한 모든 경우를 한번씩 순회한 다음 x+1번째 비트가 0일 때 가능한 모든 비트를 한 번씩 순회하고, 모두 0이 되었다. 또한 이 과정 동안 x+1번째 비트보다 왼쪽에 있는 비트들에 영향을 끼치지 않았다. 따라서 x+1에 대해서 위 명제가 만족함을 볼 수 있다.

이제 원래 mask에 대해서 총 n개의 비트가 원래 1이었다고 하자. 위의 명제에서 x에 n을 넣으면 가능한 2ⁿ개의 모든 상태를 한 번씩 순회한 후 모두 0으로 된다. 모두 0이 되면 for문의 가운데 조건에 의해 반복문을 빠져나가므로 결국 모든 부분집합을 한 번씩 순회함을 알 수 있다. 참고로 공집합은 순회하지 않음을 잘 알아두자.

부분집합의 순회에 관한 문제를 풀다보면 아래 코드처럼 모든 부분집합의 부분집합을 순회해야 할 경우가 있다.

for(mask=1; mask < (1<<n); mask++) {
    for(i = mask; i; i = ((i - 1) & mask)) {
        do something
    }
}

이 경우 do something이 몇 번이나 불릴까? 대강 생각하면 부분집합의 개수가 2ⁿ개이고 각각 최대 2ⁿ의 부분집합을 가지고 있으니 4ⁿ이라 생각할 수도 있다. 그러나 실제로 계산해보면 생각보단 적음을 알 수 있다.

원소가 k개인 집합은 총 $ _{n} C_{k} $ 개 있다. 또한 각각은 $ 2^{k} $ 개의 부분집합을 순회하게 된다. 따라서 do something이 불리는 횟수는 $ \sum _{k=0} ^{n} {_{n} C_{k}} \cdot 2^{k} $ 이 될 것이다. 이를 이항계수를 이용하면 다음과 같이 구할 수 있다.

$ \sum _{k=0} ^{n} {_{n} C_{k}} \cdot 2^{k} = (1 + 2) ^{n} = 3^n $

따라서 4ⁿ보다는 훨씬 작은 3ⁿ번 밖에 불리지 않음을 알 수 있다. 이러한 형태의 문제를 SoS(Sum of Subsets) problem이라고도 한다.

동적계획법 (Dynamic Programming, DP)