2.15.1 State & Transition

개념

동적 계획법(DP)은 부분 문제의 답을 저장해 두고 다시 필요할 때 사용하는 방법입니다. 피보나치 수열을 통해 같은 값을 반복해서 계산하는 재귀 풀이를 어떻게 바꿀 수 있는지 살펴봅니다.

피보나치 수열과 상태

피보나치 수열은 $F_0=0$, $F_1=1$로 시작하며, 이후의 항은 바로 앞의 두 항을 더한 값입니다.

$F_i=F_{i-1}+F_{i-2}\quad(i\ge2).$

DP에서 상태는 저장할 값이 어떤 문제의 답인지를 나타냅니다. 여기서는 $D_i$를 피보나치 수열의 $i$번째 항으로 정의합니다. 그러면 초기값은 $D_0=0$, $D_1=1$이고, 이전 상태로 다음 상태를 구하는 전이식은 $D_i=D_{i-1}+D_{i-2}$입니다.

단순 재귀에서 반복되는 계산

정의를 그대로 재귀에 적용하면 $F_0$과 $F_1$은 즉시 반환하고, 나머지는 앞의 두 항을 재귀로 구해 더합니다. $F_5$를 계산하는 첫 호출은 $F_4$와 $F_3$으로 나뉩니다.

$F_5$에서 직접 호출한 $F_3$과 $F_4$를 구할 때 호출한 $F_3$은 같은 계산입니다. 두 호출은 각각 $F_2$와 $F_1$을 구하고, 그 안에서도 같은 계산을 반복합니다. 실제로 $F_5$를 구할 때 $F_3$은 $2$번, $F_2$는 $3$번 호출됩니다. 필요한 항은 $F_0$부터 $F_5$까지 $6$개이지만, 함수 호출은 종료 조건에 도달하는 호출까지 합쳐 $15$번 발생합니다.

메모이제이션: 계산한 항을 재사용

Top-down DP는 재귀 호출에서 구한 결과를 저장하는 방식입니다. 먼저 해당 항이 저장되어 있는지 확인하고, 저장되어 있다면 그 값을 반환합니다. 처음 구하는 항이면 앞의 두 항을 구해 더한 뒤 저장합니다. 계산 결과를 기억해 두는 것을 메모이제이션이라고 합니다.

$F_5$를 구하며 $F_4$ 안에서 $F_3=2$를 계산해 저장했다면, 이후 $F_5$가 다시 $F_3$을 요청할 때는 저장된 $2$를 반환합니다. 그 아래의 $F_2$와 $F_1$ 계산도 다시 수행할 필요가 없습니다. 각 항의 덧셈은 한 번씩만 수행합니다.

계산 전 상태를 $-1$로 표시하면 실제 결과인 $F_0=0$과 구별할 수 있습니다. 재귀 종료 조건인 $F_0$과 $F_1$은 미리 저장합니다.

반복문: 작은 항부터 계산

Bottom-up DP는 필요한 작은 상태부터 순서대로 채우는 방식입니다. $D_0$과 $D_1$을 먼저 저장하고 $i=2$부터 $N$까지 증가시키며 $D_i$를 계산합니다.

$D_2=1+0=1,\quad D_3=1+1=2,\quad D_4=2+1=3,\quad D_5=3+2=5.$

$D_i$를 구할 때 참조하는 $D_{i-1}$과 $D_{i-2}$는 이미 계산되어 있습니다. 계산 순서를 직접 정하므로 재귀 호출이 필요하지 않습니다. $F_N$만 필요하면 직전 두 항만 보관하여 저장 공간을 줄일 수도 있습니다.

복잡도 비교

구하려는 항의 번호를 $N$이라고 합니다. 단순 재귀는 한 호출이 최대 두 호출로 나뉘므로 시간복잡도의 상한을 $O(2^N)$으로 잡을 수 있습니다. 동시에 쌓이는 재귀 호출의 깊이는 $O(N)$입니다.

DP의 시간은 상태 수와 각 상태를 계산하는 데 필요한 연산 수로 구합니다. 피보나치 수열은 상태가 $N+1$개이고, 초기값 이후의 상태마다 덧셈 한 번을 수행하므로 $O(N)$입니다.

예제

문제

피보나치 수열은 $F_0=0$, $F_1=1$이며, $i\ge2$일 때 $F_i=F_{i-1}+F_{i-2}$로 정의된다. $F_N$을 구하여라.

입력

첫째 줄에 음이 아닌 정수 $N$이 주어진다. $0\le N\le20$이다.

출력

$F_N$을 출력한다.