목차
계산기를 두드리다 보면 아까 낸 값을 또 내게 된다. 그럴 때 사람은 쪽지에 적어두고 다음부터는 쪽지를 본다. 동적 계획법이라는 긴 이름이 가리키는 건 그것뿐이다.
같은 걸 몇 번이나 다시 세고 있었나
피보나치 수를 재귀로 짜면 이렇게 된다. 정의를 그대로 옮긴 것이라 읽기도 쉽다.
long fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}맞는 코드다. 그런데 fib(40)을 부르면 몇 초씩 걸린다. 이유는 호출을 펼쳐 보면 바로 보인다.
점선으로 묶인 두 뭉치는 글자 하나 다르지 않은 같은 계산이다. 여기 딸린 칸까지 세면 fib(1)은 다섯 번, fib(2)는 세 번 계산된다.
틀린 절차가 아니다. 같은 뭉치를 통째로 다시 세고 있을 뿐이다.
fib(5) 하나를 구하는 데 fib(2)를 세 번 센다. fib(1)은 다섯 번이다. 값이 매번 같은데도 그때마다 처음부터 다시 계산한다. n이 커지면 이 중복이 곱으로 불어나서, fib(40)은 호출이 3억 번을 넘는다.
절차가 틀린 게 아니라 같은 일을 반복하고 있는 것이다. 그러니 고칠 것도 절차가 아니다.
쪽지에 적어두면 한 번씩만 센다
한 줄이면 된다. 구한 값을 적어두고, 묻기 전에 쪽지부터 본다.
Long[] memo = new Long[n + 1];
long fib(int n) {
if (n <= 1) return n;
if (memo[n] != null) return memo[n]; // 쪽지를 먼저 본다
return memo[n] = fib(n - 1) + fib(n - 2); // 구했으면 적어둔다
}구해야 할 값의 개수는 그대로다. 사라진 것은 같은 값을 또 세던 높이이고, 남는 것은 값마다 한 칸이다.
같은 값을 두 번 계산하지 않으니 계산하는 값은 n개뿐이다. 3억 번이 마흔 번이 된다. 코드는 두 줄 늘었고 절차는 그대로다.
쪽지가 통하려면 두 가지가 필요하다
아무 문제에나 쪽지를 붙일 수는 없다. 두 성질이 있어야 한다.
하나, 같은 작은 문제가 여러 번 나와야 한다. 매번 다른 문제만 나오면 적어둔 쪽지를 다시 볼 일이 없다. 쪽지는 쓰는 값만 내고 못 번다. 분할 정복에서 본 병합정렬이 그렇다. 반씩 나눈 조각은 서로 겹치지 않아서 적어둘 이유가 없다.
둘, 작은 답으로 큰 답을 만들 수 있어야 한다. fib(5)가 fib(4)와 fib(3)으로 결정되는 것처럼. 큰 문제의 답이 작은 문제의 답만으로 안 정해지면, 적어둔 값이 쓸모가 없다.
이 둘을 어려운 말로 겹치는 부분 문제와 최적 부분 구조라고 부른다. 말은 어려운데 묻는 건 간단하다. “같은 게 또 나오나, 그리고 작은 답으로 큰 답이 나오나.”
내려가면서 적을까, 올라가면서 채울까
같은 발상을 두 방향으로 짤 수 있다.
위에서 내려가는 쪽은 방금 본 코드다. 원래 문제를 그대로 물어보고, 필요한 작은 값이 없으면 그때 구한다. 재귀에 쪽지 한 장을 얹은 것이라 원래 정의와 코드가 닮아 읽기 쉽다.
아래에서 올라가는 쪽은 순서를 뒤집는다. 작은 것부터 표를 채워 올라간다.
long[] dp = new long[n + 1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
return dp[n];| 위에서 내려가기 | 아래에서 올라가기 | |
|---|---|---|
| 코드 모양 | 정의와 닮았다 | 반복문 |
| 안 쓰는 값 | 계산 안 한다 | 전부 채운다 |
| 깊이 | 재귀라 쌓인다 | 안 쌓인다 |
| 공간 줄이기 | 어렵다 | 쉽다 |
실무에서 갈리는 건 아래 두 줄이다. 재귀로 짜면 깊이가 깊어질 때 터질 수 있고, 반복문으로 짜면 그 걱정이 없다. 그리고 공간을 줄이기가 훨씬 쉽다.
책상이 좁아진다
동적 계획법은 시간을 사면서 공간을 낸다. 이건 대가지 부작용이 아니다.
fib은 쪽지가 n장이면 되지만, 문제에 따라 표가 2차원이 되기도 한다. 문자열 둘을 비교하는 문제라면 표가 n × m이 되고, 둘 다 1만이면 칸이 1억 개다. 시간을 줄였는데 메모리에서 터진다.
그런데 아래에서 올라가는 방식이면 줄일 여지가 있다. fib의 표는 n칸인데, 실제로 보는 건 바로 앞 두 칸뿐이다.
long a = 0, b = 1;
for (int i = 2; i <= n; i++) { long t = a + b; a = b; b = t; }
return b;표가 통째로 사라지고 변수 둘만 남았다. 2차원 표도 마찬가지로 바로 앞 줄만 필요하면 두 줄만 들고 있으면 된다. 이걸 알아보는 기준은 하나다. 표의 어느 칸이 어디를 참조하는가.
여기서 쪽지 비유가 깨진다. 사람의 쪽지는 대충 적어두고 눈으로 훑어 찾는다. 프로그램의 쪽지는 그럴 수 없다. 이 쪽지가 어떤 문제의 답인지를 정확한 이름으로 붙여 두고, 그 이름으로 정확히 찾아야 한다. 그리고 이름을 잘못 붙이면 다른 문제의 답을 가져다 쓴다. 그래서 다음 절의 이야기가 이 방법에서 가장 어렵다.
진짜 어려운 건 무엇을 적을지 정하는 일이다
동적 계획법을 배울 때 사람들이 헤매는 자리는 재귀도 표도 아니다. 쪽지 한 장에 무엇을 적을지 정하는 것이다.
fib은 쉬웠다. 쪽지 하나가 “n번째 피보나치 수”라는 게 명백했다. 실제 문제는 그렇지 않다.
- 물건을 골라 담는 문제라면 쪽지는 “앞에서 i개까지 봤고 남은 무게가 w일 때의 최대 가치”가 된다.
- 문자열 둘을 맞추는 문제라면 “첫 문자열 i번째까지와 둘째 문자열 j번째까지의 답”이 된다.
쪽지의 이름이 정해지면 나머지는 거의 자동으로 따라온다. 그 이름으로 “이 값은 어떤 값들로 정해지나”를 쓰면 그게 곧 코드다. 반대로 이름이 안 잡히면 코드도 안 나온다.
그래서 이 방법을 연습할 때 물어야 할 것은 “어떻게 짜지”가 아니다. “지금 내가 푸는 작은 문제를 한 문장으로 뭐라고 부를 것인가.” 그 문장에 들어가는 값들이 곧 표의 축이 된다.
실무에서: 이름만 다를 뿐 늘 쓰고 있다
실무에서 표를 채우는 코드를 짤 일은 거의 없다. 그런데 **“한 번 계산한 것은 다시 계산하지 않는다”**는 발상 자체는 매일 쓴다.
캐시가 정확히 그것이다. 계산이든 조회든 비싼 것을 한 번 해서 적어두고 다음부터는 적어둔 걸 준다. 그래서 동적 계획법에서 겪는 문제가 캐시에서 이름만 바꿔 다시 나타난다.
- 무엇을 키로 삼을 것인가. 쪽지의 이름을 정하는 그 문제다. 키에 들어가야 할 값을 빠뜨리면 다른 요청의 답을 준다. 사용자별로 달라지는 결과를 사용자 없이 캐싱한 사고가 이 모양이다.
- 언제 버릴 것인가. 프로그램 안의 표는 함수가 끝나면 사라지지만, 캐시는 남는다. 원본이 바뀌었는데 쪽지가 남아 있으면 틀린 답을 아주 빠르게 준다.
- 책상이 얼마나 넓은가. 다 적어둘 수는 없으니 무엇을 버릴지 정해야 한다. 그 규칙에 붙은 이름들이 또 알고리즘이다.
정리하면 이렇다. 표를 손으로 채우는 일은 드물어도, **“이 값을 방금 전에도 계산하지 않았나”**를 의심하는 습관은 실무 성능 개선의 절반쯤을 차지한다. 반복문 안에서 매번 같은 쿼리를 날리는 코드가 정확히 fib 재귀와 같은 모양이다.
정리
- 동적 계획법은 계산한 값을 적어두고 다시 묻지 않는 것이다. 절차가 아니라 중복을 고친다.
- 통하려면 둘이 필요하다. 같은 작은 문제가 또 나오고, 작은 답으로 큰 답이 나올 것.
- 짜는 방향은 둘이다. 위에서 내려가면 정의와 닮고, 아래에서 올라가면 깊이 걱정이 없고 공간을 줄이기 쉽다.
- 시간을 사고 공간을 낸다. 표가 커지면 참조하는 범위를 보고 줄인다.
- 가장 어려운 건 점화식이 아니라 쪽지 한 장을 한 문장으로 뭐라 부를지 정하는 것이다.
- 실무에서는 캐시라는 이름으로 만난다. 키를 잘못 잡으면 남의 답을 아주 빠르게 준다.
다음 글은 반대편 극단을 본다. 앞뒤를 재지 않고 지금 제일 좋아 보이는 것만 고르는 방법, 그리고 그게 언제 맞고 언제 틀리는지다.