어떻게 풀어둔 답을 다시 쓰기

같은 것을 또 푼다

재귀는 큰 문제를 작은 문제로 쪼개 푼다. 피보나치가 딱 그렇다.
fib(5)는 fib(4)와 fib(3)을, fib(4)는 또 fib(3)과 fib(2)를 부른다. 그런데 가만히 보면 fib(2)가 이 가지 저 가지에서 자꾸 또 나와요.
아래 나무에서 노드를 하나 눌러 확인해 보자.

같은 작은 문제가 트리 곳곳에 또 나와요. (노드 클릭 → 같은 값 모두 강조)

같은 fib(2)를 한 번이 아니라 여러 번 푼다. fib(3)도 마찬가지다.
n이 커지면 이 중복은 무섭게 불어난다.
이미 풀어 둔 답을 풀고 또 푸는 것은 누가 봐도 아까운 일이에요.

답을 적어 둔다

해법은 의외로 단순하다. 한 번 푼 답을 메모지에 적어 두는 것이다.
다음에 같은 것이 또 필요하면 다시 계산하지 않고 메모에서 꺼내 쓴다. 처음 보는 것만 계산하고, 본 적 있는 것은 꺼내 쓰면 돼요.
버튼을 눌러 호출을 하나씩 처리해 보자.

처음 본 것은 계산해 적고, 본 적 있는 것은 메모에서 꺼내 써요. 이것이 메모이제이션이다.

계산은 처음 딱 한 번뿐이다. 나머지는 전부 메모에서 꺼내 쓰니 같은 것을 두 번 푸는 일이 싹 사라진다.
이렇게 풀어 둔 답을 적어 두고 다시 쓰는 방법을 메모이제이션이라고 해요.
이름은 거창하지만 속은 '적어 두기'다.

아래부터 표 채우기

같은 생각을 거꾸로 할 수도 있다. 위에서 쪼개 내려가는 대신 맨 아래 작은 값부터 표를 채워 올라가는 것이다.
fib(0)과 fib(1)은 그냥 안다. 그 둘을 더해 fib(2)를 얻고, fib(1)과 fib(2)를 더해 fib(3)을 얻는다.
아래 칸들이 이미 적혀 있으니 위 칸은 더하기만 하면 돼요.

0,1부터 한 칸씩 위로 채워요. (다음 칸 = 바로 아래 두 칸의 합 · 상향식)

이 방식에는 메모지조차 필요 없다. 표 자체가 메모이기 때문이다.
아래에서 위로 차례대로 한 번만 훑으면 다시 풀 일이 아예 없다.
메모이제이션이 '필요할 때 적어 두기'라면 이것은 '미리 다 적어 두기'예요. 둘의 속뜻은 똑같다.

확 빨라진다

그렇다면 얼마나 빨라질까? 적어 두기 하나로 달라지는 것은 어마어마하다.
순수 재귀는 중복까지 다 푸니 n이 커질수록 일거리가 폭발하듯 늘어난다. 메모는 각 칸을 딱 한 번씩, n에 비례해서만 푼다.
n을 키워 가며 둘을 견줘 보면 차이가 확 드러나요.

같은 n에서 푸는 횟수를 견준다. (순수 재귀=지수로 폭발 · 메모=n에 비례한 선형)

n이 조금만 커져도 순수 재귀의 막대는 화면을 뚫고 나갈 듯 솟는다. 메모의 막대는 거의 그대로다.
같은 답을 다시 풀지 않는다는 이 한 가지가 느림과 빠름을 가르는 거예요.

정리

동적 계획법은 이름은 어렵지만 속은 세 걸음이다.
같은 것을 또 푼다는 것을 알아채고, 한 번 푼 답을 적어 두고, 다시 쓰니 확 빨라진다.
아래 카드를 하나씩 눌러 세 걸음을 정리해요.

같은 걸 또 품 → 적어 두기 → 확 빨라짐. 조각이 겹치지 않는 분할 정복에서는 적어 둘 필요가 없었다는 것도 다시 짚는다.

앞서 본 분할 정복에서는 쪼갠 조각이 서로 겹치지 않아 적어 둘 것이 없었다.
바로 그 지점이 갈림길이다. 조각이 겹칠 때, 다시 말해 같은 작은 문제가 자꾸 다시 나올 때 비로소 적어 두기라는 한 수가 모든 것을 바꿔요.