동적 계획법: 작은 답을 적어 두고 다시 쓰기

피보나치 수를 식 그대로 재귀(recursion) 호출하면 같은 계산을 수십, 수백 번 되풀이합니다. 한 번 구한 답을 적어 두면 하나씩 한 번만 구하면 됩니다. 재귀 트리(recursion tree)에서 되풀이를 세어 보고, 배낭 문제의 표를 한 칸씩 채워 보세요.

한 줄 답. 동적 계획법은 큰 문제를 작은 문제로 나누고, 작은 문제의 답을 한 번만 구해 적어 둔 뒤 다시 쓰는 방법입니다. 두 조건이 맞을 때 씁니다. 같은 작은 문제가 되풀이되고(중복 부분 문제, overlapping subproblems), 작은 문제의 가장 좋은 답으로 큰 문제의 가장 좋은 답을 만들 수 있을 때(최적 부분 구조, optimal substructure)입니다. 쓰는 법은 둘, 메모이제이션(memoization)과 타뷸레이션(tabulation)입니다. 위에서 재귀 호출하며 답을 적어 두거나, 아래에서부터 표를 채웁니다.

막대로 n 을 바꿔 보세요. 원 하나가 함수를 한 번 부른 것이고, 원 안의 숫자 k 는 fib(k) 를 불렀다는 뜻입니다. 같은 k 는 같은 색입니다. 자리가 좁으면 숫자 없이 색만 남깁니다. 트리 아래 줄은 k 마다 부른 횟수입니다. 메모이제이션으로 바꾸면: 굵은 고리와 「이미 풂」이 붙은 원은 적어 둔 답을 꺼내 오는 부름이고, 화살표는 그 답을 처음 계산한 원에서 옵니다. 흐린 원은 메모이제이션이면 아예 부르지 않는 부름입니다. 흐리지 않은 원을 세면 메모이제이션의 부른 횟수가 됩니다.

해 볼 것. ① 처음(n = 6)에는 그냥 재귀가 25번, 메모이제이션이 11번 부릅니다. 트리에서 fib(4) 가 2번, fib(3) 이 3번, fib(2) 가 5번 나옵니다. ② n = 3 이면 둘 다 5번입니다. 되풀이가 거의 없으면 적어 둬도 얻는 것이 없습니다. ③ n = 10 이면 177번과 19번입니다. fib(1) 하나만 55번 불립니다. ④ n = 12 까지 올리면 465번과 23번입니다. n 이 하나 늘 때마다 그냥 재귀는 약 1.62배(177 → 287 → 465)가 되고, 메모이제이션은 2번씩 늘어납니다.

1. 동적 계획법이란: 두 조건

피보나치 수는 앞의 두 수를 더해 만듭니다: 0, 1, 1, 2, 3, 5, 8, 13, … 식으로는 이렇습니다.

fib(n) = fib(n − 1) + fib(n − 2)      (n ≥ 2)
fib(0) = 0,  fib(1) = 1

이 식대로 짠 함수는 fib(6) 을 구하려고 fib(4) 를 2번, fib(2) 를 5번 다시 구합니다. 같은 답을 매번 처음부터 다시 계산하는 것입니다. 동적 계획법은 이 낭비를 없앱니다. 다음 두 조건이 맞는 문제에 씁니다.

  1. 중복 부분 문제: 같은 작은 문제가 되풀이된다. fib(6) 안에서 fib(4) 가 두 번 필요합니다. 되풀이가 없으면 적어 둬도 다시 꺼낼 일이 없습니다. 병합 정렬처럼 나눈 반쪽들이 겹치지 않는 문제는 분할 정복(divide and conquer)으로 그냥 나눠서 풉니다(병합 정렬과 퀵 정렬).
  2. 최적 부분 구조: 작은 문제의 가장 좋은 답으로 큰 문제의 가장 좋은 답을 만든다. 아래 배낭 문제에서, 한도 8 의 가장 좋은 답에 C(무게 4)가 들어 있다면, 나머지는 「C 앞의 물건들로 한도 4 를 가장 좋게 채운 답」이어야 합니다. 나머지를 더 좋게 채우는 길이 있다면 그것으로 바꿔 끼워 전체가 더 좋아질 테니까요.

2. 두 가지 쓰는 법

메모이제이션: 위에서 재귀 호출하며 적어 두기. 식 그대로 재귀 호출하되, 답을 구하면 적어 두고, 부를 때마다 먼저 적어 둔 것이 있는지 봅니다. 있으면 계산하지 않고 꺼냅니다. 필요한 작은 문제만 풉니다. 실험의 「메모이제이션」이 이것입니다. Python 에서는 표준 라이브러리 functools.cache 를 함수 위에 한 줄 붙이면 됩니다.

from functools import cache

@cache
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(10))           # 55
print(fib.cache_info())  # CacheInfo(hits=8, misses=11, maxsize=None, currsize=11)

cache_info() 의 misses 11 은 새로 계산한 수(fib(0) ~ fib(10)), hits 8 은 적어 둔 답을 꺼낸 수입니다. 합 19 가 실험에서 n = 10 일 때 「메모이제이션」의 부른 횟수와 같습니다. 문서에 따르면 cache 는 크기 제한이 없는 함수 캐시이고, 인자를 사전(dict)의 키로 써서 답을 찾습니다. 그래서 인자는 해시할 수 있는 값이어야 하고(해시 표), 같은 인자에 늘 같은 답을 내는 함수에만 붙여야 합니다.

타뷸레이션: 아래에서 표 채우기. 가장 작은 문제부터 차례로 답을 표에 채웁니다. fib(0), fib(1), fib(2), … 순서로 채우면 각 칸을 채울 때 필요한 앞 칸이 이미 있습니다. 재귀 호출하지 않고 반복문 하나로 끝납니다. 채우는 순서는 직접 정해야 하고, 필요 없는 칸까지 다 채웁니다. 아래 배낭 실험이 이 방식입니다.

3. 배낭 문제: 표를 한 칸씩 채우기

무게 한도가 있는 배낭에 물건을 담습니다. 물건마다 무게와 값이 있고, 하나씩만 있으며 쪼갤 수 없습니다(넣거나 안 넣거나). 한도를 넘지 않으면서 값의 합을 가장 크게 하려면 무엇을 넣어야 할까요? 이 쪽의 물건은 지어낸 넷입니다: A 무게 5 값 11, B 무게 4 값 8, C 무게 4 값 7, D 무게 2 값 3. 한도는 8 입니다.

표의 줄은 「물건을 어디까지 볼지」, 칸은 「한도」입니다. 칸 하나를 채우는 식이 점화식입니다.

best[0][c] = 0,   best[i][0] = 0
best[i][c] = best[i − 1][c]                                  (wᵢ > c: 들어가지 않을 때)
best[i][c] = max(best[i − 1][c], vᵢ + best[i − 1][c − wᵢ])   (wᵢ ≤ c)
45678 B까지C까지 811111111811111115 안 넣음 11넣음 7 + 8 = 1515 > 11
C 줄, 한도 8 칸 하나를 채울 때 보는 두 칸. 파랑: C 를 안 넣으면 바로 위 칸의 11. 초록: 넣으면 위 줄에서 C 의 무게 4 만큼 왼쪽 칸의 8 에 C 의 값 7 을 더해 15. 큰 쪽(굵은 화살표)인 15 를 적습니다.

「넣을 때」를 늘 위 줄에서 가져오므로 같은 물건을 두 번 넣지 않습니다.

「다음」을 누르면 한 칸씩 채웁니다. 주황 테두리가 지금 채우는 칸입니다. 파랑 화살표 ↓ 는 안 넣을 때 바로 위 칸에서, 초록 화살표 ↘ 는 넣을 때 위 줄에서 무게만큼 왼쪽 칸에서 값을 가져옵니다. 화살표가 나오는 칸 위에 셈을 적고, 큰 쪽 화살표를 굵게 그립니다. 물건이 무거워 못 넣는 칸은 파랑 화살표 하나뿐입니다. 다 채우면 오른쪽 아래에서부터 주황 화살표를 따라 거꾸로 올라가며 고른 물건에 ✓ 를 붙입니다.

해 볼 것. ① 걸음 6(A까지, 한도 5)에서 처음으로 물건이 들어갑니다: 0 대신 11. 걸음 13(B까지, 한도 4)에서는 B 가 들어가 8 입니다. ② 걸음 25(C까지, 한도 8)에서 안 넣으면 11, 넣으면 7 + 8 = 15 입니다. B 와 C 를 같이 넣는 길이 여기서 나옵니다. ③ 걸음 31(D까지, 한도 6)은 두 값이 11 로 같습니다. ④ 걸음 33 이 마지막 칸이고 답은 15 입니다. 걸음 34 ~ 37 에서 거꾸로 따라가면 D 는 빠지고 C, B 가 골라집니다. 걸음 38 에서 모든 묶음 16가지를 따진 값도 15 이고, 그리디는 14 입니다.

4. 손으로 따라가기

실험과 같은 물건, 같은 한도로 표를 끝까지 채운 모습입니다. 줄마다 왼쪽에서 오른쪽으로, 위 줄만 보고 채웁니다.

줄 \ 한도012345678
없음000000000
A까지 (5, 11)0000011111111
B까지 (4, 8)0000811111111
C까지 (4, 7)0000811111115
D까지 (2, 3)0033811111415
  1. A 줄. A 의 무게가 5 라 한도 0 ~ 4 에는 들어가지 않아 위 칸 0 을 그대로 씁니다. 한도 5 부터는 max(0, 11 + 0) = 11.
  2. B 줄, 한도 8. 안 넣으면 위 칸 11. 넣으면 8 + best[A][8 − 4] = 8 + 0 = 8. A 와 B 는 합쳐 무게 9 라 같이 못 넣습니다. 큰 쪽을 적어 11.
  3. C 줄, 한도 8. 안 넣으면 11. 넣으면 7 + best[B][4] = 7 + 8 = 15. 큰 쪽을 적어 15.
  4. D 줄, 한도 7. 안 넣으면 11. 넣으면 3 + best[C][5] = 3 + 11 = 14. 큰 쪽을 적어 14(A 와 D).
  5. D 줄, 한도 8. 안 넣으면 15. 넣으면 3 + best[C][6] = 3 + 11 = 14. 큰 쪽을 적어 15. 이것이 답입니다.
  6. 역추적(traceback): 거꾸로 따라가기. D 줄 한도 8 의 15 는 위 칸 15 와 같으니 D 없이 나옵니다. C 줄의 15 는 위 칸 11 과 다르니 C 를 넣었습니다. 한도를 8 − 4 = 4 로 옮기면 B 줄의 8 은 위 칸 0 과 다르니 B 를 넣었습니다. 한도가 4 − 4 = 0 이 되고, A 줄의 0 은 위 칸과 같아 A 는 빠집니다. 고른 물건은 B, C, 무게 8, 값 15.

Python 으로 옮기면 이렇습니다(15줄).

def knapsack(items, limit):
    """items: [(이름, 무게, 값), ...]. 한도 안에서 가장 큰 값의 합과 고른 물건."""
    best = [[0] * (limit + 1)]                       # 물건 0개: 모두 0
    for _, weight, value in items:
        above = best[-1]
        best.append([max(above[c], value + above[c - weight]) if weight <= c else above[c]
                     for c in range(limit + 1)])
    picked, c = [], limit
    for i in range(len(items), 0, -1):               # 역추적
        if best[i][c] != best[i - 1][c]:
            picked.append(items[i - 1][0])
            c -= items[i - 1][1]
    return best[-1][limit], picked[::-1]

print(knapsack([("A", 5, 11), ("B", 4, 8), ("C", 4, 7), ("D", 2, 3)], 8))   # (15, ['B', 'C'])

5. 그리디가 틀리는 예

그리디는 지금 가장 좋아 보이는 것을 고르고 되돌리지 않습니다. 배낭에서 흔히 떠올리는 그리디는 「무게 1 당 값(값÷무게)이 큰 것부터 넣기」입니다. 실험의 물건은 값÷무게가 A 2.2, B 2, C 1.75, D 1.5 입니다.

A 가 무게당 값은 가장 좋지만, A 를 먼저 넣으면 남은 한도 3 이 거의 쓸모없어집니다. 그리디는 이 뒤의 일을 보지 않습니다. 동적 계획법은 칸마다 「넣을 때」와 「안 넣을 때」를 둘 다 따지고 둘 다 표에 남겨 두므로, 한 번의 선택이 나중을 망치는지 알 수 있습니다.

6. 걸리는 시간

동적 계획법의 시간은 칸 수 × 칸마다 하는 일입니다. 칸 하나는 한 번만 채우기 때문입니다(시간 복잡도).

배낭의 C 는 물건의 수가 아니라 한도라는 숫자의 크기입니다. 한도가 두 배면 표도 두 배입니다. 한도를 원 단위 예산처럼 아주 큰 수로 적으면 표가 감당할 수 없이 커집니다. 이때는 단위를 줄이거나(만 원 단위로) 다른 방법을 봅니다. 메모리는 표 전체가 (n + 1) × (C + 1) 칸입니다. 답의 값만 필요하면 바로 위 줄만 남겨 C + 1 칸으로 줄일 수 있습니다. 위의 코드처럼 거꾸로 따라가려면 표 전체를 남겨야 합니다.

7. 언제 무엇을 쓰나: 그리디, 동적 계획법, 백트래킹

셋 다 「여러 선택 가운데 가장 좋은 것」을 찾는 방법입니다. 배낭(물건 n 개, 한도 C)을 예로 비교합니다.

그리디동적 계획법백트래킹
하는 일지금 가장 좋아 보이는 것을 고르고 되돌리지 않는다작은 문제의 답을 표에 적어 두고 다시 쓴다하나씩 넣어 보고, 안 되면 되돌아가 다른 길을 넣어 본다
답틀릴 수 있다(이 쪽: 14)늘 맞다(15)늘 맞다(15)
걸리는 시간가장 좋을 때·보통·가장 나쁠 때 모두 O(n log n). 값÷무게로 정렬하는 데 드는 시간가장 좋을 때·보통·가장 나쁠 때 모두 O(n·C). 표의 칸 수가장 좋을 때는 가지치기로 일찍 끝난다. 보통은 입력과 가지치기에 따라 다르다. 가장 나쁠 때 O(2ⁿ): 물건 하나 늘면 두 배
더 드는 메모리O(n): 정렬한 순서O(n·C): 표. 값만이면 O(C)O(n): 지금까지 고른 것
좋은 점빠르고 짧다정확하고, 시간이 입력의 모양에 흔들리지 않는다조건이 복잡해도 쓸 수 있다. 가능한 답을 모두 내야 할 때도 쓴다
나쁜 점맞다는 것을 보일 수 있는 문제에만 쓸 수 있다작은 문제를 무엇으로 잡을지 정해야 한다. 한도 같은 숫자가 크면 표가 커진다가장 나쁠 때 아주 느리다
쓰는 경우쪼갤 수 있는 배낭, 최소 신장 트리, 다익스트라작은 문제가 되풀이되고 그 가짓수(칸 수)가 감당할 만할 때n 이 작거나, 가지치기가 잘 듣거나, 모든 경우를 나열해야 할 때

어디에 쓰나

자주 묻는 것

메모이제이션과 타뷸레이션 가운데 무엇을 쓰나요?

점화식을 그대로 옮기고 싶으면 메모이제이션이 쉽습니다. Python 이면 @cache 한 줄로 끝나고, 필요한 작은 문제만 풉니다. 재귀가 아주 깊어질 것 같거나 메모리를 줄여야 하면 타뷸레이션을 씁니다. 재귀가 없고, 바로 앞 줄만 남기는 식으로 메모리를 줄이기 쉽습니다.

동적 계획법이면 늘 빠른가요?

아닙니다. 걸리는 시간은 칸 수 × 칸마다 하는 일입니다. 칸이 너무 많으면 느립니다. 배낭은 칸 수가 한도라는 숫자에 비례해서, 한도가 아주 큰 수면 표가 감당할 수 없이 커집니다. 작은 문제가 되풀이되지 않는 문제라면 적어 둬도 다시 꺼낼 일이 없어 얻는 것이 없습니다.

그리디로 풀어도 되는지 어떻게 아나요?

지금 가장 좋아 보이는 것을 고르는 것이 늘 가장 좋은 답의 일부라는 것을 보일 수 있을 때만 됩니다. 물건을 쪼개 담을 수 있는 배낭이면 값÷무게가 큰 것부터 담는 그리디가 맞습니다. 쪼갤 수 없으면 이 쪽의 예처럼 틀릴 수 있어 동적 계획법을 씁니다.

낱말

여기서 쓴 말책에서 부르는 말
작은 답을 적어 두고 다시 쓰기동적 계획법(dynamic programming, DP)
위에서 재귀 호출하며 적어 두기메모이제이션(memoization), 하향식(top-down)
아래에서 표 채우기타뷸레이션(tabulation), 상향식(bottom-up)
같은 작은 문제가 되풀이된다중복 부분 문제(overlapping subproblems)
작은 문제의 가장 좋은 답으로 큰 문제의 가장 좋은 답을 만든다최적 부분 구조(optimal substructure)
칸 하나를 앞 칸들로 적는 식점화식(recurrence relation)
표의 칸 하나, 작은 문제 하나상태(state)
함수가 자기를 다시 부르기, 그 부름을 그린 그림재귀(recursion), 재귀 트리(recursion tree)
쪼갤 수 없는 배낭 문제0-1 배낭 문제(0-1 knapsack problem)
쪼갤 수 있는 배낭 문제분할 가능 배낭 문제(fractional knapsack problem)
거꾸로 따라가 고른 것 찾기해 복원(reconstruction), 역추적(traceback)
숫자의 크기(한도)에 비례하는 시간의사 다항 시간(pseudo-polynomial time)
나눈 문제가 겹치지 않을 때 나눠 풀기분할 정복(divide and conquer)

출처

← 그리디백트래킹 →