기억력 좋은 알고리즘의 비밀
크리스는 알고리즘 공부를 하다가 유명한 수열인 피보나치 수열을 마주쳤다.
1, 1, 2, 3, 5, 8, 13... 앞의 두 수를 더해서 다음 수를 만드는 간단한 규칙이다.
"재귀 함수 배웠으니까 이걸로 구현하면 멋지겠는데?"
JavaScript
// ❌ 크리스의 순진한 재귀 함수 function fib(n) { if (n <= 2) return 1; return fib(n - 1) + fib(n - 2); } // fib(10) 정도는 금방 나온다. // 하지만 fib(50)을 넣는 순간... 브라우저가 멈췄다.
크리스는 당황했다. 고작 50번째 숫자를 구하는 건데 최신형 맥북이 비명을 지르며 멈춰버린 것이다.
이유는 **"기억력"**이 없기 때문이다. 크리스의 코드는 이미 계산했던 값을 까먹고 또 계산하고, 또 계산하고 있었다.
오늘은 멍청한 반복 계산을 천재적인 효율로 바꿔주는 마법, **동적 프로그래밍(Dynamic Programming, DP)**에 대해 알아본다.
1. 재귀의 저주: 했던 거 또 하기
fib(5)를 구하는 과정을 상상해 보자.
그림을 보면 fib(3)이 여러 번 호출되고, fib(2)는 더 많이 호출된다.
숫자가 조금만 커져도 연산 횟수는 $2^N$으로 폭발한다(지수 시간). fib(50)을 계산하려면 약 1,000조 번 이상의 연산이 필요하다. 컴퓨터가 멈출 만하다.
2. 동적 프로그래밍의 핵심: 메모이제이션 (Memoization)
동적 프로그래밍(DP)이라는 이름은 사실 좀 어렵게 들리지만, 개념은 아주 단순하다.
"한 번 푼 문제는 답을 적어두고(Memo), 나중에 베껴 쓰자!"
이것을 **메모이제이션(Memoization)**이라고 한다.
크리스의 코드 심폐소생술
JavaScript
// ✅ DP 적용 (Top-Down 방식) function fibMemo(n, memo = []) { // 1. 메모장에 답이 있으면? 계산 안 하고 리턴! (핵심) if (memo[n] !== undefined) return memo[n]; // 2. 기본 조건 if (n <= 2) return 1; // 3. 계산 결과를 메모장에 적어둔다. const res = fibMemo(n - 1, memo) + fibMemo(n - 2, memo); memo[n] = res; return res; }
이제 fib(50)을 실행해도 0.001초도 안 걸린다.
이미 계산한 fib(3)을 다시 만나면, 복잡한 트리를 내려가지 않고 배열(memo)에서 값을 쏙 꺼내오기 때문이다($O(1)$).
전체 시간 복잡도는 **$O(N)$**으로, 1,000조 번의 연산이 단 50번으로 줄어들었다.
3. 또 다른 방법: 타뷸레이션 (Tabulation)
메모이제이션이 "위에서 아래로(Top-Down)" 필요한 걸 찾으러 내려가는 방식이라면,
JavaScript
// ✅ DP 적용 (Bottom-Up 방식) function fibTable(n) { if (n <= 2) return 1; // 처음부터 표를 만들고 시작한다. const fibNums = [0, 1, 1]; // 3번부터 n번까지 순서대로 채운다. for (let i = 3; i <= n; i++) { fibNums[i] = fibNums[i - 1] + fibNums[i - 2]; } return fibNums[n]; }
재귀 호출로 인한 스택 오버플로우(Stack Overflow) 위험이 없기 때문에, 데이터가 엄청나게 클 때는 이 방식이 더 안전하다.
4. 언제 DP를 써야 할까?
모든 문제에 DP를 쓸 수 있는 건 아니다. 두 가지 조건이 맞아야 한다.
이 두 가지 냄새가 난다면, 즉시 메모장을 꺼내야 한다.
5. 결론: 똑똑한 게으름
동적 프로그래밍은 개발자의 미덕인 **"게으름"**을 알고리즘화한 것이다.
"아까 계산했는데 왜 또 해? 적어놓고 베껴야지."
이 단순한 아이디어가 $O(2^N)$이라는 최악의 성능을 $O(N)$이라는 최고의 성능으로 바꿔놓았다.
알고리즘 대회나 코딩 테스트에서 "경우의 수"나 "최대/최소 비용"을 구하라는 문제의 90%는 바로 이 DP로 푼다.
그렇다면 실전에서 어떤 문제들을 만났을 때 "아, 이건 DP다!"라고 눈치챌 수 있을까?
다음 글, "[Algorithm] 동적 프로그래밍을 사용해야 할 때: 실전 패턴 분석" 편에서 계속된다.