다이나믹 프로그래밍
다이나믹 프로그래밍이란 "하나의 문제는 단 한번만 풀도록 하는 알고리즘" 입니다. 한 번 푼 것을 여러 번 다시 푸는 비효율적인 알고리즘을 개선시키는 방법이기도 합니다.
**피보나치 수열**은 **특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 두칸 앞에 있는 숫자의 합**을 구해야 합니다. 바로 다음과 같다.
피보나치 수열의 점화식 : D[i]=D[i-1]+D[i-2]
다이나믹 프로그래밍은 다음의 가정 하에 사용할 수 있습니다.
1번 가정 : 큰 문제를 작은 문제로 나눌 수 있다.
2번 가정 : 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일합니다.
즉, 쉽게 말해 크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤에 처리하여 나중에 전체의 답을 구하는 것입니다. 다만 이 과정에서 메모이제이션이 사용이 됩니다. 이미 계산한 결과는 배열에 저장함으로써 나중에 동일한 계산을 해야 할 때는 저장된 값을 단순히 반환하기만 하면 되는 것입니다. 바로 피보나치 수열을 예로 들어 문제를 확인해봅시다.
위 경우는 답이 55로 잘 출력됩니다. 하지만 다음과 같이 50번째 피보나치 수열을 구하려고 한다면 어떻게 되는지 확인해보면 실행이 되지하고 우주가 멸망할 때까지 실행이 되지 않고 계속 CPU가 돌아가는 것을 볼 수 있습니다. 이는 사실 당연한 결과입니다. 피보나치 수열이 1개만 늘어나도 계산 량은 2배로 늘어나기 때문입니다. 간단하게 2의 50제곱이라고 보시면 됩니다. 그렇기에 이를 해결하기 위해 메모이제이션 기법을 활용하시면 됩니다.
위와 같이 해주시면 이미 계산된 결과는 배열 D에 저장되기 때문에 한 번 구한 값을 다시 구하는 일은 존재하지 않습니다. 위와 같인 작업하면 순식간에 계산된 겨로가를 출력되는 것을 확인할 수 있습니다.
