동적 계획법

Dynamic Programming, DP.

개요

동적 계획법은 어떤 최적화 문제를, 작은 부분 문제로 나누어 차례대로 해결하는 알고리즘을 말한다.

이름이 Dynamic Programming이지만 그닥 역동적인 알고리즘은 아닌데, 예산을 따오기 위해 멋진 이름을 지었다고 카더라(...). 또한 Programming은 컴퓨터 프로그래밍을 의미하는 것이 아니고, 선형계획법처럼 최적화 문제의 해결 방법이라는 의미이다.

예시

그냥 이론을 설명하기에는 복잡하니, 예시를 보며 이해해 보자.

피보나치 수열 구하기

피보나치 수열은 제 0항을 0, 제 1항을 1로 하고, 그 다음 항부터는 이전 두 개 항의 합으로 나타나는 수열이다.

이를 점화식으로 표현하면 [math]\displaystyle{ \mathrm{fib}(n) = \mathrm{fib}(n - 1) + \mathrm{fib}(n - 2) (n \gt 2), \mathrm{fib}(0) = 0, \mathrm{fib}(1) = 1 }[/math]가 된다.

이를 계산하는 프로그램을 작성해 보자. 점화식에 충실하게 재귀함수로 풀면 다음과 같을 것이다. 편의상 Python3으로 작성하였다.

def fib(n):
    if n == 1 or n == 0:
        return n
    return fib(n - 1) + fib(n - 2)

분명 잘 작동하긴 하는데, 문제는 숫자가 조금만 커져도 시간이 너무 오래 걸린다는 점이다. [math]\displaystyle{ \mathrm{fib}(5) }[/math]의 계산 과정을 그림으로 그려보면 다음과 같다.

위의 동그라미는 아래 두 개의 동그라미의 합으로 채워진다. 얼마나 많은 계산이 필요한지 알 수 있다. 그런데 저 계산들 중 중복되는 것이 보이지 않는가?

저 과정에서 [math]\displaystyle{ \mathrm{fib}(2) }[/math]는 3번, [math]\displaystyle{ \mathrm{fib}(3) }[/math]는 2번 계산됨을 알 수 있다. 이걸 일일히 계산하지 말고, 한번 구한 값을 그냥 어디 적어(memo)놨다가 다시 쓰면 어떨까?

이 기법이 바로 메모화(memoization)이다.

저 그림의 맨 왼쪽 아래부터 계산하기 시작해보자. [math]\displaystyle{ \mathrm{fib}(2) = 1 + 0 = 1 }[/math]로 채워진다. 그 위의 [math]\displaystyle{ \mathrm{fib}(3) = 1 + 1 = 2 }[/math]가 될 것이다. 이제 [math]\displaystyle{ \mathrm{fib}(4) }[/math]를 계산해야 한다. 원래는 [math]\displaystyle{ \mathrm{fib}(4) = 2 + \mathrm{fib}(2) }[/math]로 오른쪽의 [math]\displaystyle{ \mathrm{fib}(2) }[/math]를 다시 계산해야겠지만, 앞서 [math]\displaystyle{ \mathrm{fib}(2) }[/math]를 계산할 때 어디 적어뒀다면 이를 바로 읽어와 [math]\displaystyle{ \mathrm{fib}(4) = 2 + 1 = 3 }[/math]을 간단히 계산할 수 있다. 마찬가지로, [math]\displaystyle{ \mathrm{fib}(5) }[/math]의 계산 역시 [math]\displaystyle{ \mathrm{fib}(3) }[/math]의 계산 결과가 저장되어 있다면, 곧바로 [math]\displaystyle{ \mathrm{fib}(5) = 3 + 2 = 5 }[/math]라는 값을 구할 수 있다. 메모하지 않았다면 [math]\displaystyle{ \mathrm{fib}(3), \mathrm{fib}(2) }[/math] 따위를 여러번 다시 구해야 할 판인데, 계산이 확 줄어들었다.

코드로 적으면 다음과 같다.

def fib(n):
    DT = [None] * (n + 1)
    DT[0], DT[1] = 0, 1
    return cal_fib(DT, n)

def cal_fib(DT, n):
    if DT[n] == None:
        DT[n] = cal_fib(DT, n - 1) + cal_fib(DT, n - 2)
    return DT[n]

시간 복잡도 분석

우선 메모화를 적용하지 않고 계산했을 때의 시간 복잡도를 구해보자. 계산 시간은 그냥 동그라미 개수라고 생각해도 좋다.

N	0	1	2	3	4	5	6
fib	0	1	1	2	3	5	8
계산량	1	1	3	5	8

N이 1일 때를 제외하고, 각 N에 대해 계산량이 [math]\displaystyle{ \mathrm{fib}(N+2) }[/math] 임이 보인다. big-O 표기법에 따르면 [math]\displaystyle{ O(\mathrm{fib}(n)) }[/math] 인데, 좀 큰 [math]\displaystyle{ n }[/math] 에 대해 [math]\displaystyle{ \mathrm{fib}(n) \approx 1.6^n }[/math] 이므로, [math]\displaystyle{ O(1.6^n) }[/math]로 쓸 수 있다.

지수함수라는 놈이 얼마나 흉악한 놈인지는 다들 알겠지만 한번 짚어보자. [math]\displaystyle{ n = 100 }[/math]정도만 생각해봐도 대충 [math]\displaystyle{ 1.6^{100} = 2.6 \times 10^{20} }[/math]쯤 되는데, 이건 컴퓨터가 뚝딱 계산할 수 있는 양이 아니다. 요즘 CPU 클럭수가 대략 4GHz, 초당 [math]\displaystyle{ 4 \times 10^9 }[/math]회니까, 65,000,000,000초, 752314일쯤 걸리지 않을까? 물론 시간복잡도에 숫자 때려넣은 걸 클럭수로 나눈 것과 실제 수행 시간이 일치하지는 않지만, 대충 감은 잡을 수 있다.

Bottom-up Approach

메모화를 통해 빠르게 피보나치 수열의 값을 구할 수 있게 되었다. 그런데 아직 문제가 하나 남았다. 저 구현이 아직 재귀함수의 형태를 띠고 있다는 것이다. 재귀함수는 디버깅이 힘들고, 무엇보다 호출 스택의 한계 때문에 일정 이상으로 재귀하게 되면 프로그램이 터져 버리는 문제가 발생할 가능성이 있다. 모든 재귀함수는 반복문으로 고칠 수 있다는 사실이 증명되어 있으므로, 저걸 반복문으로 고치는게 좋겠다.

메모화 재귀에서는 [math]\displaystyle{ \mathrm{fib}(5) }[/math]를 먼저 호출하고, 그 곳에서 [math]\displaystyle{ \mathrm{fib}(4), \mathrm{fib}(3), \cdots }[/math]등을 위에서 아래로 (Top-down) 호출하게 된다. 하지만 실제로 피보나치 수를 저장한 테이블이 차오르는 순서는 반대로, 아래에서부터 올라오게 된다. 위에서 아래로 내려가는 과정을 생략하고, 그냥 아래서부터 채워 올라오는 것이 바로 Bottom-up Approach이다.

def fib(n):
    if n == 0: return 0
    DT = [None] * (n + 1)
    DT[0], DT[1] = 0, 1
    for i in range(2, n + 1): #i = 2부터 n까지 증가한다.
        DT[i] = DT[i - 1] + DT[i - 2]
    return DT[n]

물론 피보나치 수열 문제는 가까운 두 값만 필요하므로, 굳이 리스트(테이블)을 생성하지 않고,

def fib(n):
    if n == 0: return 0
    temp0, temp1 = 0, 1
    for i in range(2, n + 1): #i = 2부터 n까지 증가한다.
        #temp0에는 temp1을, temp1에는 temp0과 temp1을 더한 값을 넣는다.
        temp0, temp1 = temp1, temp0 + temp1
    return temp1

처럼 하면 메모리 공간을 절약할 수 있다. 다만 이 풀이는 동적계획법적인 풀이라고 보기는 힘들고, 피보나치 수열을 구하는 수많은 방법 중 하나라고 생각하자. 동적 계획법은 메모리를 희생해서 수행 시간을 개선하는 방법이라고 생각해도 좋다.

거스름돈 문제

리브레 제국의 화폐 체계는 영 이상해서, 이 나라의 상인들은 거스름돈 계산을 힘들어 한다. 국왕인 당신은 이러한 백성들을 어엿비 녀겨 거스름돈을 계산하는 프로그램을 만들기로 결심했다.

이 나라에는 [math]\displaystyle{ x_1 }[/math]원, [math]\displaystyle{ x_2 }[/math]원, [math]\displaystyle{ \cdots , x_i }[/math]원 짜리 동전이 있고, 거슬러 주는 동전의 개수는 최대한 줄여야 한다.

행렬을 곱하는 순서

행렬을 곱할 때, 어떤 것을 먼저 곱하는지에 따라 계산량은 크게 달라진다. 계산을 가능한 한 적게 할 수 있도록, 적절히 괄호를 묶어주기 위한 알고리즘을 생각해보자.