풀어둔 답을 다시 쓰기

같은 걸 또 풀어요

재귀는 큰 문제를
작은 문제로 쪼개 풀어요.
피보나치가 딱 그래요.
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이 조금만 커져도
순수 재귀의 막대는
화면을 뚫고 나갈 듯 솟아요.
메모의 막대는
거의 가만히 있고요.
같은 답을 또 풀지 않는다,
이 한 가지가
느림과 빠름을 가르는 거예요.

정리

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

같은 걸 또 품 → 적어두기 → 확 빨라짐. (분할정복은 안 겹쳐 메모 불필요였음을 회수)

지난 시간 분할정복에선
쪼갠 조각이 서로 겹치지 않아서
적어둘 게 없었어요.
바로 거기가 갈림길이에요.
조각이 겹칠 때,
그러니까 같은 작은 문제가
자꾸 다시 나올 때,
비로소 적어두기 한 수가
모든 걸 바꾸는 거예요.