다음 편: [코딩테스트] 2. 메모이제이션
코딩테스트에서 재귀로 짠 코드가 작은 입력엔 통과하는데 N이 조금만 커져도 시간초과가 나는 경험을 하게 된다. 재귀 자체가 느린 게 아니다. 특정 구조에서 재귀는 같은 연산을 수천, 수억 번 반복한다. DP를 이해하려면 먼저 이 구조를 직접 추적해봐야 한다.
재귀로 시작하는 이유
피보나치는 DP 입문에서 항상 등장하는 예시다. 이유가 있다. 정의 자체가 재귀적이라 코드가 수학적 정의를 그대로 따른다. 그러면서도 문제점이 가장 극명하게 드러난다.
피보나치 수열의 정의는 이렇다.
fib(1) = 1
fib(2) = 1
fib(n) = fib(n-1) + fib(n-2)이 정의를 코드로 그대로 옮기면 아래가 된다.
int fib(int n) {
if (n <= 2) return 1;
return fib(n - 1) + fib(n - 2);
}짧고 직관적이다. 수학 정의와 코드가 1:1로 대응한다. 그런데 이 짧은 코드가 실제로 어떻게 실행되는지 들여다보면 이야기가 달라진다.
재귀가 숨기고 있는 것
코드는 간결해 보이지만, 실행 과정은 그렇지 않다. 함수를 호출하면 그 안에서 또 두 번의 호출이 일어나고, 그 안에서 또 각각 두 번씩 일어난다. 실제로 몇 번이나 호출되는지 추적해보자.
호출 트리를 직접 펼쳐보면
fib(6)을 호출했을 때 내부에서 발생하는 모든 함수 호출을 펼치면 이렇다. 각 노드의 색은 중복 계산 빈도를 나타낸다.
- 주황색 노드 :
fib(4)— 2번 계산 - 빨간색 노드 :
fib(3),fib(2)— 3~5번 계산
fib(6) 하나를 구하는 데 총 25번의 함수 호출이 발생한다.
왜 이렇게 되는가
fib(6)은 fib(5)와 fib(4)를 호출한다. fib(5)는 자기 계산을 위해 fib(4)를 또 호출한다. 이 둘은 서로 모른다. fib(6)이 fib(4)를 이미 계산하고 있더라도, fib(5)는 그 사실을 알 방법이 없다. 그래서 fib(4)를 처음부터 다시 계산한다.
이 일이 모든 레벨에서 반복된다. fib(4) 안에서도 fib(3)을 두 번 계산하고, fib(3) 안에서도 fib(2)를 두 번 계산한다. 트리 전체를 보면 같은 값이 여러 경로에서 독립적으로 재계산되고 있다.
비유하자면 이렇다. 팀 프로젝트에서 A가 특정 조사를 마쳤는데, B가 그 사실을 모르고 똑같은 조사를 따로 한다. C도, D도 마찬가지다. 결과는 같은데 작업은 4배 든다. 재귀 트리에서 벌어지는 일이 정확히 이것이다.
얼마나 느려지는가
호출 횟수가 느낌상 많다는 건 알겠는데, 정확히 얼마나 많은지 수치로 짚어보자.
지수 증가의 실체
매 단계에서 호출이 두 갈래로 나뉜다.
fib(n)
├── fib(n-1)
│ ├── fib(n-2) ←── fib(n)도 이걸 따로 계산
│ └── fib(n-3)
└── fib(n-2) ←── 이미 위에서 계산했는데 또 계산
├── fib(n-3)
└── fib(n-4)n이 1 늘어날 때마다 호출 횟수는 약 2배가 된다. 시간복잡도는 O(2^N)이다.
구체적인 수치를 보면 체감이 다르다.
| N | 호출 횟수 (대략) |
|---|---|
| 10 | 약 100번 |
| 20 | 약 10,000번 |
| 30 | 약 100만 번 |
| 40 | 약 10억 번 |
| 50 | 약 1조 번 |
N = 50이면 1초에 10억 번을 처리하는 컴퓨터로도 약 1,000초가 걸린다. 코딩테스트 제한 시간이 보통 1~2초인 걸 감안하면, N이 조금만 커져도 재귀 그대로는 통과 자체가 불가능하다.
중복 부분 문제
이 현상에는 이름이 있다.
fib(4)는 fib(6)을 계산하는 경로에서도, fib(5)를 계산하는 경로에서도 필요하다. 같은 하위 문제가 서로 다른 경로에서 반복 등장하는 구조를 중복 부분 문제라 한다. DP는 바로 이 구조가 있을 때 효과가 있다.
DP를 공부하다 보면 "최적 부분 구조"와 "중복 부분 문제"라는 두 조건이 자주 등장한다. 둘 중 중복 부분 문제가 이 편의 핵심이다. 같은 하위 문제가 반복해서 계산된다면, 결과를 저장해서 재사용하면 된다.
재귀가 괜찮은 경우와 아닌 경우
"재귀는 느리다"는 말은 반만 맞다. 재귀 자체가 느린 게 아니라, 특정 구조에서 재귀가 느려지는 것이다.
분할 정복은 왜 괜찮은가
병합 정렬을 생각해보자. 배열을 반으로 나눠 각각 정렬하고 합치는 방식이다.
mergeSort([1,5,3,2,4,6])
├── mergeSort([1,5,3]) ← 이 부분만 정렬
└── mergeSort([2,4,6]) ← 이 부분만 정렬 (위와 겹치지 않음)오른쪽 절반을 정렬하는 데 왼쪽 절반의 결과가 필요하지 않다. 두 하위 문제는 완전히 독립적이다. 같은 부분 배열을 두 번 정렬하는 일은 없다.
반면 피보나치는 다르다.
fib(6)
├── fib(5)
│ └── fib(4) ← 여기서도 필요
└── fib(4) ← 여기서도 필요 (중복!)하위 문제들이 겹친다. 이 차이가 성능 차이를 만든다. 분할 정복은 O(N log N)이고, 재귀 피보나치는 O(2^N)이다.
요약하면 이렇다.
- 하위 문제가 겹치지 않으면 : 재귀 그대로 써도 된다 (분할 정복)
- 하위 문제가 겹치면 : 저장해서 재사용해야 한다 (DP)
자주 하는 실수
재귀와 DP를 처음 배울 때 빠지기 쉬운 오해들이다.
"재귀가 느리니까 반복문으로 바꾸면 된다"
재귀를 반복문으로 바꾼다고 중복 계산이 사라지지 않는다. 반복문으로 짜도 fib(4)를 여러 번 계산하는 구조는 똑같이 만들 수 있다. 문제는 재귀가 아니라 중복 계산이다. 중복 계산을 없애는 게 핵심이고, 그 방법이 메모이제이션이나 Bottom-up DP다.
"N이 작으면 재귀로 충분하다"
N = 35 정도까지는 재귀도 빠르게 느껴진다. 그래서 "이 문제는 N이 작으니까 재귀로 해도 되겠지"라고 생각하기 쉽다. 그런데 코딩테스트 문제는 대부분 N의 최댓값에 맞춰 시간제한을 설정한다. 입력 예시가 작아도, 실제 채점 데이터는 최대 입력을 기준으로 돌린다. N = 40이 제한이라면 재귀로는 통과 불가능하다.
재귀가 깊어지면 스택 오버플로우도 발생한다. 시간초과는 연산이 너무 많은 것, 스택 오버플로우는 함수 호출이 너무 깊이 쌓이는 것이다. N = 100,000짜리 피보나치를 재귀로 짜면 시간초과보다 스택 오버플로우가 먼저 나올 수 있다. DP의 Bottom-up 방식은 이 두 문제를 모두 해결한다.
"값이 같으면 같은 계산이 아니다"
fib(4)가 두 곳에서 호출될 때, 입력은 같지만 각각 독립적인 계산이 수행된다. 함수가 반환한 값을 누가 저장해두지 않으면, 다음 호출에서 그 값을 알 방법이 없다. 반환값을 저장하지 않으면 계산한 것과 안 한 것이 같다.
이게 메모이제이션의 핵심 아이디어다. 계산한 결과를 어딘가에 저장해두면, 다음에 같은 입력이 들어왔을 때 계산 없이 바로 꺼내 쓸 수 있다.
해결 방향
원인은 단순하다. 이미 계산한 값을 저장하지 않는다는 것이다.
fib(4)를 처음 계산했을 때 결과를 어딘가에 저장해두면, 다음에 또 필요할 때 다시 계산하지 않아도 된다. 각 값은 딱 한 번만 계산된다.
저장 전략에는 두 가지가 있다. 재귀 구조를 유지하면서 저장을 추가하는 메모이제이션, 작은 값부터 채워 올라가는 타뷸레이션이다. 다음 편에서 메모이제이션부터 구현해본다.