복잡한 문제를 더 작은 부분 문제로 나눠 풀되, 한 번 푼 부분 문제의 답을 저장해 다시 계산하지 않는 방법. 두 조건이 맞을 때 쓴다.
- 겹치는 부분 문제(Overlapping Subproblems): 같은 부분 문제가 여러 번 나온다
- 최적 부분 구조(Optimal Substructure): 부분 문제의 최적해를 조합해 전체 최적해를 만들 수 있다
피보나치로 보기
단순 재귀 fib(n) = fib(n-1) + fib(n-2)는 같은 값을 수없이 다시 계산해 O(2ⁿ)이다. fib(45)만 돼도 눈에 띄게 느리다.
// 메모이제이션: 위에서 아래로(top-down), 재귀 + 캐시
const memo = new Map<number, number>()
function fibMemo(n: number): number {
if (n <= 2) return 1
if (!memo.has(n)) memo.set(n, fibMemo(n - 1) + fibMemo(n - 2))
return memo.get(n)!
}
// 타뷸레이션: 아래에서 위로(bottom-up), 반복문 + 표
function fibTable(n: number) {
const t = [0, 1, 1]
for (let i = 3; i <= n; i++) t[i] = t[i - 1] + t[i - 2]
return t[n]
}둘 다 O(n)이 된다.
- 메모이제이션(Memoization)은 원래 재귀 구조를 그대로 두고 캐시만 더해 쓰기 쉽다. 하지만 n이 크면 재귀가 깊어져 스택 오버플로가 날 수 있다(재귀)
- 타뷸레이션(Tabulation)은 작은 문제부터 표를 채운다. 스택을 쓰지 않고, 필요한 칸만 남기면 공간도 줄일 수 있다(피보나치는 변수 두 개면 된다)
배낭 문제(Knapsack Problem), 최장 공통 부분 수열(Longest Common Subsequence, LCS), 편집 거리(Edit Distance), 동전 거스름돈(Coin Change)이 대표 문제다. 부분 문제가 겹치지 않는다면 분할 정복으로 충분하다. 같은 "계산 결과 재사용" 아이디어가 React의 memo·useMemo·useCallback과 캐시 전반(읽기 캐시 전략)에도 있다.