동적 계획법

동적 계획법은 같은 작은 계산이 거듭 나오는 문제를 빠르게 풉니다. 작은 문제의 답을 한 번만 구해 표에 적어 둡니다. 같은 문제가 다시 나오면 계산하지 않고 표에서 꺼내 씁니다. 동전을 가장 적게 써서 거스름돈을 주는 방법이나 두 글이 어디서 다른지 찾는 일을 이렇게 풉니다.

쉽고 빠른 이해

동적 계획법은 작은 문제의 답을 적어 두고 다시 쓰는 방법입니다. 피보나치 수열의 30번째 수를 재귀로만 구하면 함수를 269만 번 넘게 부릅니다. 답을 적어 두면 서른한 개의 수를 한 번씩만 계산하고 끝납니다.

큰 문제를 작은 문제로 쪼개다 보면 같은 작은 문제가 몇 번이고 다시 나옵니다. 매번 새로 풀면 일이 입력 크기에 대해 지수로 불어납니다.

어떻게 도나:

작은 문제의 답으로 큰 문제의 답을 만드는 식을 세웁니다
가장 작은 문제부터 답을 구해 표에 적습니다
큰 문제를 풀 때는 표에 적힌 답을 꺼내 씁니다

대가는 표를 담을 메모리입니다. 같은 작은 문제가 다시 나오지 않는 문제라면 표는 메모리만 차지합니다.

상세

동적 계획법(dynamic programming)은 알고리즘을 짜는 한 가지 방식입니다. 문제 하나를 푸는 특정한 절차가 아닙니다. 작은 문제의 답을 표에 모아 큰 문제의 답을 만드는 여러 알고리즘이 함께 쓰는 뼈대입니다.

피보나치 수열로 같은 계산이 되풀이되는 모습을 먼저 봅니다. 이어서 답을 표에 적어 두는 생각과 그 생각이 통하는 두 조건을 봅니다. 그다음 표를 채우는 두 방식과 식을 세우는 순서를 거스름돈 문제로 밟습니다. 끝으로 비용을 세는 법과 이 방식이 안 맞는 문제를 봅니다.

같은 계산이 되풀이될 때

피보나치 수열은 앞의 두 수를 더해 다음 수를 만드는 수열입니다. 0, 1, 1, 2, 3, 5, 8 로 이어집니다. n 번째 수를 fib(n) 이라고 쓰면 fib(n) = fib(n−1) + fib(n−2) 입니다.

이 식은 재귀 함수로 옮기면 짧게 적힙니다. 재귀는 함수가 자기 자신을 다시 부르는 것입니다. 아래 함수는 fib(n) 을 구하려고 fib(n−1) 과 fib(n−2) 를 다시 부릅니다.

Python

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

fib(5)   # 5
fib(30)  # 832040

첫 if 두 줄은 n 이 0 이나 1 일 때 n 을 바로 돌려줍니다. 이렇게 더 쪼개지 않고 답이 나오는 가장 작은 경우를 기저 사례(base case)라고 합니다. 기저 사례가 있어야 재귀가 끝납니다.

코드는 맞는 답을 냅니다. 문제는 함수를 부르는 횟수입니다. fib(5) 하나를 구할 때 어떤 호출이 일어나는지 그림으로 봅니다.

flowchart TD
    A["fib(5)"] --> B["fib(4)"]
    A --> C["fib(3) 다시"]
    B --> D["fib(3)"]
    B --> E["fib(2) 다시"]
    D --> F["fib(2)"]
    D --> G["fib(1)"]
    F --> H["fib(1)"]
    F --> I["fib(0)"]
    E --> J["fib(1)"]
    E --> K["fib(0)"]
    C --> L["fib(2) 다시"]
    C --> M["fib(1)"]
    L --> N["fib(1)"]
    L --> O["fib(0)"]

그림에서 fib(3) 은 두 번, fib(2) 는 세 번 계산됩니다. 왼쪽 가지가 이미 구한 값을 오른쪽 가지가 모른 채 처음부터 다시 구합니다. fib(1) 과 fib(0) 은 기저 사례라 바로 답이 나오므로 「다시」를 붙이지 않았습니다.

n 이 커지면 이 중복이 불어납니다. fib(5) 에는 함수가 열다섯 번 불립니다. fib(30) 에는 269만 번 넘게 불립니다. 부르는 횟수가 n 에 대해 지수로 늘기 때문입니다.

한 번 푼 답을 표에 적어 두기

해결책은 한 번 구한 답을 버리지 않는 것입니다. fib(3) 을 처음 구했을 때 그 값을 표에 적어 둡니다. 다음에 fib(3) 이 필요하면 계산하지 않고 표에서 꺼냅니다.

큰 문제를 풀려면 먼저 풀어야 하는 작은 문제를 부분 문제(subproblem)라고 부릅니다. fib(5) 의 부분 문제는 fib(4) 부터 fib(0) 까지입니다. 부분 문제는 큰 문제와 모양이 같습니다. 크기만 작습니다.

동적 계획법은 부분 문제마다 답을 한 번만 구해 표에 적어 두는 방법입니다. 큰 문제의 답은 표에 적힌 답을 모아 만듭니다. 표는 흔히 배열이나 해시테이블로 둡니다.

이름의 「계획법」은 영어 programming 을 옮긴 말입니다. 여기서 programming 은 코드를 짜는 일이 아니라 표를 채워 가며 답을 짜 나가는 방법을 가리킵니다. 「동적」도 프로그램이 실행 중에 무언가를 정한다는 뜻이 아닙니다. 이름보다 「작은 답을 표에 적어 다시 쓰는 방법」으로 기억하면 됩니다.

중복 부분 문제와 최적 부분 구조

동적 계획법이 통하려면 문제가 두 조건을 갖춰야 합니다. 같은 부분 문제가 되풀이되어야 하고, 작은 답을 모아 큰 답을 만들 수 있어야 합니다.

첫째는 중복 부분 문제(overlapping subproblems)입니다. 같은 부분 문제가 풀이 중에 여러 번 나온다는 뜻입니다. 피보나치 수열에서는 fib(3) 이 여러 번 나옵니다. 겹치는 하위 문제라고도 부릅니다.

같은 부분 문제가 다시 나오지 않으면 표에 적은 답을 꺼낼 일이 없습니다. 이런 문제는 쪼개서 풀고 답을 합치는 분할 정복으로 충분합니다.

분할 정복의 예로 배열을 반으로 나눠 정렬하는 병합 정렬이 있습니다. 나눈 두 조각은 서로 겹치지 않아 같은 부분 문제가 다시 나오지 않습니다.

둘째 조건을 말하려면 낱말 하나가 필요합니다. 최적해(optimal solution)는 문제가 정한 기준에서 가장 앞서는 답입니다. 길 찾기라면 가장 짧은 길이, 거스름돈이라면 동전이 가장 적은 조합이 최적해입니다.

둘째는 최적 부분 구조(optimal substructure)입니다. 큰 문제의 최적해 안에 부분 문제의 최적해가 들어 있다는 뜻입니다. 서울에서 부산까지 가장 짧은 길이 대전을 지난다고 해 봅시다. 그 길의 서울-대전 구간도 서울에서 대전까지 가장 짧은 길이어야 합니다.

이 성질이 있어야 부분 문제마다 최적해 하나만 표에 남겨도 됩니다. 나머지 답은 버립니다. 큰 문제를 풀 때 버린 답이 다시 필요해지지 않습니다.

위에서 내려가기와 아래에서 올라가기

표를 채우는 순서는 둘로 나뉩니다. 하나는 큰 문제에서 출발해 필요한 부분 문제로 내려가는 방식입니다. 다른 하나는 가장 작은 부분 문제부터 채워 올라가는 방식입니다.

위에서 내려가는 방식은 앞의 재귀 함수에 표를 붙입니다. 함수가 불리면 먼저 표를 봅니다. 답이 있으면 계산하지 않고 꺼내 돌려줍니다. 이 방식을 메모이제이션(memoization)이라고 부릅니다.

Python

from functools import cache

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

fib(30)  # 832040

@cache 는 함수의 인자와 돌려준 값을 표에 적어 두는 파이썬 기능입니다. 같은 인자로 다시 부르면 함수 본문을 건너뛰고 표의 값을 돌려줍니다. 앞의 코드와 달라진 것은 첫 두 줄뿐입니다.

표를 붙이면 fib(5) 를 부르는 모습이 아래처럼 줄어듭니다. 실선은 처음 계산하는 호출입니다. 점선은 표에서 답을 꺼내는 호출입니다.

flowchart TD
    A["fib(5)"] --> B["fib(4)"]
    B --> C["fib(3)"]
    C --> D["fib(2)"]
    D --> E["fib(1)"]
    D --> F["fib(0)"]
    C -.->|표에서 꺼냄| E
    B -.->|표에서 꺼냄| D
    A -.->|표에서 꺼냄| C

fib(0) 부터 fib(5) 까지 여섯 개의 수를 한 번씩만 계산합니다. fib(30) 도 fib(0) 부터 fib(30) 까지 서른한 개만 계산하면 끝납니다.

위에서 내려가는 방식은 재귀를 쓰므로 호출이 호출 스택에 쌓입니다. 호출 스택은 아직 끝나지 않은 함수 호출을 순서대로 기억해 두는 메모리 영역입니다. 재귀가 너무 깊어지면 이 영역이 바닥나 프로그램이 멈춥니다.

아래에서 올라가는 방식은 재귀를 쓰지 않습니다. 반복문으로 가장 작은 부분 문제부터 표를 채웁니다. 큰 칸을 채울 때는 그 칸이 기대는 작은 칸이 이미 채워져 있습니다. 이 방식을 표 채우기(tabulation)라고도 부릅니다.

Python

def fib(n):
    table = [0] * (n + 1)
    if n > 0:
        table[1] = 1
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]

fib(30)  # 832040

table[i] 에 fib(i) 를 적습니다. i 를 2 부터 올려 가며 채우므로 table[i - 1] 과 table[i - 2] 는 언제나 먼저 채워져 있습니다.

두 방식은 같은 표를 채웁니다. 두 방식이 갈리는 곳은 다섯입니다.

	위에서 내려가기	아래에서 올라가기
다른 이름	하향식 · 메모이제이션	상향식 · 표 채우기
코드	재귀 함수에 표를 붙인다	반복문으로 표를 채운다
푸는 부분 문제	큰 문제에 필요한 것만	표의 모든 칸
채우는 순서	재귀가 알아서 정한다	짜는 사람이 정한다
호출 스택	재귀 깊이만큼 쌓인다	쌓이지 않는다

필요한 부분 문제가 드문드문하면 위에서 내려가는 쪽이 일을 덜 합니다. 표의 칸을 거의 다 써야 하는 문제라면 아래에서 올라가는 쪽이 호출 스택이 바닥날 걱정 없이 돕니다.

점화식을 세우는 순서

새 문제를 동적 계획법으로 풀 때는 표의 한 칸이 무엇을 담는지부터 정합니다. 그다음 점화식을 세웁니다. 점화식은 큰 칸의 값을 작은 칸의 값으로 적은 식입니다. 앞에서 본 fib(n) = fib(n−1) + fib(n−2) 도 점화식입니다.

이 순서를 거스름돈 문제로 밟아 봅니다. 동전이 1원·3원·4원 세 가지일 때 6원을 가장 적은 개수의 동전으로 만드는 문제입니다.

먼저 떠오르는 방법은 큰 동전부터 쓰는 것입니다. 4원 하나를 쓰면 남은 2원을 1원 둘로 채워 동전이 세 개 듭니다. 3원 둘을 쓰면 두 개로 끝나므로 이 방법은 틀린 답을 냅니다. 매 순간 가장 좋아 보이는 것을 고르는 이런 방식을 그리디 알고리즘이라고 합니다.

동적 계획법은 가능한 선택을 모두 따져 봅니다. 대신 같은 계산은 표에 적어 두어 되풀이하지 않습니다. 순서는 넷입니다.

칸이 담는 값을 정합니다. best[a] 를 a원을 만드는 데 드는 가장 적은 동전 수로 둡니다. 구할 답은 best[6] 입니다
점화식을 세웁니다. 마지막에 c원짜리 동전을 쓰면 남은 a−c원도 가장 적게 만들어야 합니다. best[a] 는 쓸 수 있는 동전 c 마다 best[a−c] + 1 을 구해 그중 가장 작은 값입니다
기저 사례를 정합니다. 0원은 동전 없이 만들므로 best[0] = 0 입니다
채우는 순서를 정합니다. best[a] 는 a 보다 작은 칸에만 기댑니다. a 를 1 부터 6 까지 올려 가며 채우면 됩니다

2번이 앞에서 본 최적 부분 구조를 씁니다. a원의 최적해는 a−c원의 최적해에 동전 하나를 더한 것입니다.

이 순서를 코드로 옮깁니다. 바깥 반복문은 금액을 1원씩 올립니다. 안쪽 반복문은 그 금액에 동전을 하나씩 대 봅니다.

Python

def min_coins(coins, amount):
    best = [0] + [float("inf")] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                best[a] = min(best[a], best[a - c] + 1)
    return best[amount]

min_coins([1, 3, 4], 6)  # 2

float("inf") 는 아직 만드는 방법을 못 찾은 칸을 무한대로 둔다는 뜻입니다. 어떤 값보다도 크므로 처음 찾은 방법이 바로 그 칸에 들어갑니다. 코드가 다 돈 뒤 칸마다 든 값은 이렇습니다.

금액 a	0	1	2	3	4	5	6
best[a]	0	1	2	1	1	2	2

best[6] 을 채울 때는 세 칸을 봅니다. 마지막 동전이 1원이면 best[5] + 1 = 3 입니다. 3원이면 best[3] + 1 = 2 입니다. 4원이면 best[2] + 1 = 3 입니다.

가장 작은 2 가 답입니다. 어느 동전을 썼는지도 알려면 칸마다 고른 동전을 함께 적어 둡니다.

best[6] 에서는 3원을 골랐으니 3원을 빼고 best[3] 으로 갑니다. best[3] 에서 또 3원을 골라 best[0] 에 닿습니다. 고른 동전을 모으면 3원 둘이 그 조합입니다.

비용을 세는 법

동적 계획법의 시간은 표의 칸 수와 한 칸을 채울 때 드는 일을 곱해 셉니다. 모든 칸을 한 번씩 채우기 때문입니다. 앞의 피보나치와 거스름돈으로 세어 봅니다.

이 곱은 흔히 빅오 표기법으로 적습니다. 빅오 표기법은 입력이 커질 때 일이 어떤 빠르기로 느는지를 적는 표기입니다. O(n) 은 일이 n 에 비례해 는다는 뜻입니다. O(nk) 는 두 수 n 과 k 의 곱에 비례한다는 뜻입니다.

문제	칸 수	한 칸의 일	시간	표의 메모리
피보나치 수열	n + 1	덧셈 한 번	O(n)	O(n)
거스름돈	금액 n + 1	동전 종류 k 개를 하나씩 대 보기	O(nk)	O(n)

재귀로만 짠 피보나치는 부르는 횟수가 지수로 늘었습니다. 표를 붙이면 칸 수에 비례하는 O(n) 으로 줄어듭니다. 이 차이가 동적 계획법을 쓰는 이유입니다.

그 대신 표를 담을 메모리가 듭니다. 입력이 커질 때 메모리가 느는 정도를 공간 복잡도라고 합니다. 위 표의 마지막 열이 두 문제의 공간 복잡도입니다.

동적 계획법은 계산을 줄이려고 메모리를 내주는 방법입니다. 이렇게 한쪽을 줄이려고 다른 쪽을 내주는 선택을 시간과 공간 맞바꿈이라고 부릅니다.

표를 다 남겨 둘 필요가 없는 경우도 많습니다. fib(i) 는 바로 앞의 두 칸만 봅니다. 두 칸만 남기고 앞의 칸을 버리면 메모리가 입력 크기와 상관없이 일정해집니다.

Python

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

fib(30)  # 832040

a 와 b 가 표의 마지막 두 칸 노릇을 합니다. 시간은 O(n) 으로 같습니다. 메모리는 O(1) 로 줄어듭니다. O(1) 은 입력이 커져도 메모리가 늘지 않는다는 뜻입니다.

표가 2차원이 되는 문제

부분 문제를 가리키는 데 수가 둘 필요하면 표도 2차원이 됩니다. 두 문자열을 비교하는 문제는 수를 둘 씁니다. 첫 문자열의 앞 i 글자와 둘째 문자열의 앞 j 글자가 부분 문제 하나입니다.

편집 거리가 대표적인 예입니다. 편집 거리는 한 문자열을 다른 문자열로 바꾸는 데 드는 가장 적은 편집 횟수입니다. 편집 한 번은 글자 하나를 넣거나 지우거나 다른 글자로 바꾸는 일입니다.

kitten 을 sitting 으로 바꾸는 데는 편집이 세 번 듭니다. k 를 s 로, e 를 i 로 바꾼 뒤 끝에 g 를 넣습니다. 편집 거리가 짧을수록 두 문자열이 비슷합니다.

표를 그릴 때 첫 문자열의 글자를 세로(행)로, 둘째 문자열의 글자를 가로(열)로 놓습니다. 칸 (i, j) 는 i 번째 행과 j 번째 열이 만나는 칸입니다. 이 칸은 첫 문자열의 앞 i 글자를 둘째 문자열의 앞 j 글자로 바꾸는 가장 적은 편집 횟수를 담습니다.

칸의 값은 마지막 편집 한 번이 무엇이었는지로 나눠 구합니다. 거스름돈에서 마지막 동전을 하나씩 대 본 것과 같은 생각입니다. 경우는 셋이고, 각 경우가 이웃한 칸 하나에 기댑니다.

위 칸 (i−1, j) — 지우기. 첫 문자열의 i 번째 글자를 지웁니다. 남은 앞 i−1 글자를 앞 j 글자로 바꾼 횟수에 1 을 더합니다
왼쪽 칸 (i, j−1) — 넣기. 앞 i 글자를 앞 j−1 글자로 바꾼 뒤 둘째 문자열의 j 번째 글자를 끝에 넣습니다. 그 칸의 값에 1 을 더합니다
왼쪽 위 칸 (i−1, j−1) — 바꾸기. 첫 문자열의 i 번째 글자를 둘째 문자열의 j 번째 글자로 바꿉니다. 두 글자가 다르면 그 칸의 값에 1 을 더하고, 같으면 바꿀 필요가 없어 그대로 씁니다

세 값 가운데 가장 작은 것이 칸 (i, j) 의 값입니다. 표를 왼쪽 위에서 오른쪽 아래로 한 줄씩 채우면 세 이웃은 언제나 먼저 채워져 있습니다.

기저 사례는 0 번째 행과 0 번째 열입니다. 앞 0 글자는 빈 문자열이라 글자 수만큼 넣거나 지우기만 하면 됩니다. 그래서 칸 (0, j) 는 j, 칸 (i, 0) 은 i 입니다.

두 문자열의 길이가 m 과 n 이면 칸이 (m + 1)(n + 1) 개입니다. 한 칸의 일은 세 값을 비교하는 것뿐이라 시간은 O(mn) 입니다.

이 밖에 널리 알려진 동적 계획법 문제 셋을 표로 모았습니다.

문제	묻는 것	쓰이는 곳
배낭 문제	무게 한도 안에서 가치 합이 가장 큰 물건 조합	—
최장 공통 부분 수열	두 문자열에 같은 순서로 들어 있는 가장 긴 글자들	두 파일에서 안 바뀐 줄을 찾는 diff
벨만-포드 알고리즘	한 출발점에서 다른 모든 점까지의 최단 거리	이웃 라우터끼리 거리를 주고받는 거리 벡터 라우팅

세 문제는 칸이 담는 값과 점화식만 다릅니다. 작은 칸부터 채워 큰 답을 만드는 뼈대는 같습니다.