피보나치와 동적 계획법

컴퓨터에게 40번째 피보나치 수를 가장 뻔한 방법으로 구하게 하면 3억 3100만 번이 넘게 호출합니다. 표를 쓰게 하면 덧셈 39번이면 됩니다. 이 차이가 바로 동적 계획법이며, 거의 모든 사람이 피보나치 수에서 동적 계획법을 처음 만납니다.

피보나치 수가 담긴 표 칸 한 줄. 채우는 중인 칸은 주황색, 더하는 두 칸은 파란색
피보나치 수가 담긴 표 칸 한 줄. 채우는 중인 칸은 주황색, 더하는 두 칸은 파란색

문제

피보나치 수는 0, 1로 시작하고, 그 뒤의 수는 모두 바로 앞 두 수의 합입니다. 0, 1, 1, 2, 3, 5, 8, 13, 21처럼 이어집니다. 규칙으로 쓰면 F(0) = 0, F(1) = 1, F(n) = F(n − 1) + F(n − 2)입니다. 이 규칙은 재귀적이라 그대로 재귀 프로그램으로 옮기기 쉽지만, 그 프로그램은 매우 느립니다.

재귀는 왜 같은 일을 반복할까

F(5)를 구하려고 프로그램은 F(4)와 F(3)을 요청합니다. F(4)는 F(3)과 F(2)를 요청하므로, F(3)은 두 번, F(2)는 세 번, F(1)은 다섯 번 계산됩니다. 트리로 그리면 호출은 단계마다 거의 두 배가 되고, F(n)의 전체 호출 수는 2·F(n + 1) − 1번입니다. 작은 문제들이 겹쳐서 같은 문제가 계속 다시 나옵니다. 이것이 동적 계획법이 도움이 된다는 신호입니다.

기억하는 두 가지 방법

메모이제이션은 재귀를 그대로 두지만 모든 답을 표에 적고, 각 호출은 일을 하기 전에 먼저 표를 확인합니다. 타뷸레이션은 표를 상향식으로 채웁니다. 먼저 F(0)과 F(1), 그다음 이 둘로 F(2), F(2)와 F(1)로 F(3), 이런 식으로 F(n)까지 갑니다. 어느 쪽이든 각 항은 한 번만 계산되므로, F(n)은 지수적으로 많은 호출 대신 덧셈 n − 1번이면 됩니다.

예제

F(7)을 상향식으로 구해 봅시다. 0과 1에서 시작합니다. 그다음 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8, 5 + 8 = 13이므로 덧셈 여섯 번 만에 F(7) = 13입니다. 단순 재귀라면 같은 답을 얻는 데 2·F(8) − 1 = 41번 호출합니다. 하향식에서는 처음 호출들이 트리의 왼쪽 가장자리를 따라 F(1)까지 내려가고, 다시 올라오는 길에는 거의 두 번에 한 번꼴로 호출이 답을 이미 표에서 찾습니다.

이름의 유래

리처드 벨만은 1950년대 초 랜드 연구소(RAND Corporation)에서 일하던 중 동적 계획법이라는 이름을 붙였습니다. 그는 나중에 programming은 '계획'이라는 옛 의미로, dynamic은 인상적으로 들리고 반대하기 어려운 말이라서 골랐다고 썼습니다. 더 작은 형태의 문제의 답으로 문제를 푸는 이 방법은 오늘날 맞춤법 검사기, 경로 탐색기, DNA 비교 등에서 쓰입니다.

1962년의 리처드 벨먼, 알프레드 아이젠스타트 촬영. 그는 1950년대 초 랜드 연구소에서 일하면서 동적 계획법이라는 이름을 붙였다.
1962년의 리처드 벨먼, 알프레드 아이젠스타트 촬영. 그는 1950년대 초 랜드 연구소에서 일하면서 동적 계획법이라는 이름을 붙였다.

직접 살펴보기

앱을 열고 단계를 누르세요. 상향식에서는 주황색 칸이 지금 채우는 칸이고, 파란색 두 칸이 더하는 항입니다. 하향식으로 바꾸면 표 아래의 호출 스택이 n까지 늘어났다가 답이 돌아오면서 줄어드는 것을 볼 수 있습니다. 덧셈 횟수 아래의 힌트는 표에서 바로 답을 얻은 호출이 몇 번인지 셉니다.

자주 묻는 질문

중복 부분 문제란 무엇인가요?

풀이에 두 번 이상 필요한 작은 문제입니다. F(n)과 F(n − 1)은 둘 다 F(n − 2)가 필요하므로 단순 재귀는 이를 두 번 계산하고, 아래로 갈수록 낭비가 더 불어납니다. 동적 계획법은 각 문제를 한 번만 풀고 답을 기억합니다.

메모이제이션이 타뷸레이션보다 빠른가요?

둘 다 덧셈은 똑같이 합니다. 타뷸레이션은 호출을 하지 않아 보통 조금 더 빠르고, 스택 공간이 부족해질 일도 없습니다. 메모이제이션은 작은 답 중 일부만 필요할 때 편리합니다. 필요한 것만 계산하기 때문입니다.

피보나치 수를 더 빨리 구할 수 있나요?

네. F(2k) = F(k)·(2·F(k + 1) − F(k))와 F(2k + 1) = F(k)² + F(k + 1)²을 이용하는 빠른 배가법은 약 log₂ n단계면 됩니다. 황금비를 쓰는 비네 공식도 같은 수를 주지만, 반올림 오차 때문에 n이 크면 믿을 수 없습니다.

표에는 메모리가 얼마나 필요한가요?

표 전체는 수 n + 1개를 담지만, 새 항에는 바로 앞 두 항만 필요하므로 수 두 개만 저장하는 반복문으로 상수 메모리에서 같은 일을 할 수 있습니다. 모든 항이 필요하거나 방법이 어떻게 동작하는지 보고 싶을 때는 표 전체를 저장하는 것이 유용합니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

동적 계획법으로 피보나치 수 구해 보기