초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.
피보나치 수열의 50번째 수를 재귀로 구하면 함수를 400억 번 넘게 부릅니다. 왜 이렇게 많이 부르는지, 어떻게 줄이는지 알아봅시다.
0, 1, 1, 2, 3, 5, 8, …처럼 앞의 두 수를 더해 다음 수를 만드는 수열을 피보나치 수열(Fibonacci sequence)이라 합니다. 0번째부터 세어 n번째 수를 fib(n)이라 하면 다음과 같으니 재귀로 그대로 옮길 수 있습니다.
출력 없음출력에서 같은 n이 몇 번 불리는지 세어 봅시다.
호출이 어떻게 퍼지는지 그려 보면 문제가 보입니다.
원 안의 숫자 k는 fib(k) 호출입니다. 원을 누르면 같은 값을 구하는 호출을 모두 칠합니다.
점선 원은 적어 둔 값을 꺼내 쓴 호출입니다.
n이 6이면 fib(2)를 다섯 번이나 처음부터 계산합니다. n이 하나 늘 때마다 호출 수는 약 1.6배가 됩니다. 한 번 구한 값을 표에 적어 두고 꺼내 쓰면 fib(0)부터 fib(n)까지 한 번씩만 계산하니, fib(50)도 호출 99번이면 끝납니다.
출력 없음재생해 위 출력과 비교해 봅시다.
큰 문제를 쪼갠 작은 문제들이 여러 번 겹쳐 나올 때, 각 답을 한 번만 구해 표에 적어 두고 다시 쓰는 방법을 동적 계획법(dynamic programming)이라 합니다. 병합 정렬은 쪼갠 두 절반이 겹치지 않으니 적어 둘 필요가 없었습니다. 표는 재귀 없이 fib(0)부터 차례로 채워도 됩니다.
거스름돈을 가장 적은 개수의 동전으로 주는 문제를 봅시다. 큰 동전부터 내는 그리디로 될 것 같지만, 동전이 1, 4, 5원이면 8원을 5 + 1 + 1 + 1로 네 개 냅니다. 4 + 4면 두 개입니다.
8원을 줄 때 마지막 동전 하나를 정하면 남은 돈은 더 작은 거스름돈 문제가 됩니다. 4원을 내면 남은 4원, 5원을 내면 3원, 1원을 내면 7원입니다. 그중 가장 적은 쪽에 하나를 더하면 8원의 답입니다. 남은 금액 문제는 계속 겹쳐 나오니 0원부터 표를 채워 올라갑니다.
0원은 동전 0개로 만듭니다. 1원부터 채워 봅시다.
8원까지 채운 뒤 동전을 1, 3, 4원으로, 거슬러 줄 돈을 6원으로 바꿔 봅시다.
금액이 A원, 동전이 k종류면 칸 A개를 채우며 칸마다 k개씩만 보니 O(A × k)입니다.
글의 첫 fib(적어 두지 않는 재귀)로 fib(12)를 계산합니다. 그동안 fib(1)은 모두 몇 번 불릴까요? 숫자로 답하세요.