병아리 개발자의 실력 양성기

코인 문제 경우 1. 정해진 금액을 가장 적은 수의 코인(동전)으로 구성하는 문제를 풀 때(단 각 동전 액면은 무한히 사용 가능), 1, 2, 5, 10, 20, 50, 100, 200 cents 로 되어 있는 유로화 코인이나 1, 5, 10, 50, 100, 500으로 된 원화 동전은 가장 큰 액면부터 차례로 채우면 최적해를 구할 수 있다. 두 경우 모두 뒤의 액면 중에는 이전 액면의 배수가 존재하므로 어느 액면이나 그 전단계의 동전을 통해 구할 수 있고, 이런 경우는 가장 큰 코인부터 답에 포함하게 된다면, 더 적은 액면으로 구성한 뒤 더 큰 액면으로 바꾼 결과와 다름이 없어 최적해가 되는 것이다. 예를 들어 1520원을 구성하고 싶으면 500 * 3 + 10 * 2 이렇게 5개 동전이 최적해이다. ..

DP의 핵심요소는 메모이제이션(캐싱)이라고 할 수 있다. 이미 계산한 결과를 저장하는 재귀라고도 할 수 있다. 기억 공간을 반복될 계산결과의 저장에 할당함으로써 귀중한 연산시간을 절약하는 것이다. DP를 이용해 해결할 수 있는 대표적이며 가장 간단한 예로 피보나치 수열이 있다. 어떻게 이 문제가 재귀, top-down DP, bottom-up DP, 그리고 그 기억공간을 추가로 절감하는 방식으로 수행되는지를 살펴본다. 재귀 피보나치 수열은 수학적으로 다음 점화식(recurrence relation)으로 정의된다. $$ f_n = f_{n-1} + f_{n-2} $$ $$ f_0 = 0; \ f_1 = 1 $$ n번째 수를 구하기 위해서는 n-1번째, n-2번째 수를 알아야 하고, 그들을 알기 위해서는 다..