동적 계획법

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]가 된다.

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

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

거스름돈 문제

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

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

행렬을 곱하는 순서

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