동적 계획법에 대해서는 오래전 포스팅을 한적이 있다.
당시에 거스름돈에을 주는 방법에 대해서 로직을 설명하였는데, 이번 포스팅은 실제 예제를 구현해 보겠다.
동적 프로그래밍은 탐욕프로그래밍과는 달리 최적화된 솔루션을 다 찾는 알고리즘이다.
이전 포스팅(Greedy Algorithm 과 거스름돈 예제) 에서 설명했던 것처럼 거스름돈 예제에 있어서 탐욕 프로그래밍은 완벽한 해를 찾지 못한다. 물론 성능은 탐욕프로그래밍이 훨씬 좋다.
거스름돈 M원에 대해서 동전 C1,...Cn 으로 최소의 동전 개수로 주는 것을 생각해 보면 다음의 Sub 해법들이 존재하는데..
(M-C1) 원에 대해서 최소한의 동전 개수 +1
(M-C2) 원에 대해서 최소한의 동전 개수 +1
...
(M-Cn) 원에 대해서 최소한의 동전 개수 +1
이 해법들의 가장 작은 값이 M원을 거슬러주는 최소 동전 개수가 되는 것이다. 예를 들어 500원, 400원, 100원 동전으로 1200원을 거슬러준다고 생각할때 최소 동전 개수를 구하는 방법은
1) 700 원(1200-500)에 대한 최소 동전 개수 +1
2) 800 원(1200-400)에 대한 최소 동전 개수 +1
3) 1100원(1200-100)에 대한 최소 동전 개수 +1
중 최소 동전 개수가 된다.
700원에 대한 최소 동전 개수는
1) 200(700-500)원에 대한 최소 동전 개수+1
2) 300(700-400)원에 대한 최소 동전 개수+1
3) 600(700-100)원에 대한 최소 동전 개수 +1 중 최소 동전 개수가 된다.
200원에 대한 최소 동전 개수는
1) 100(200-100)원에 대한 최소 동전 개수 +1
일반화 해보면 최소 동전 개수 S(M) = Min(S(M-C1)+1,S(M-C2)+1,...,S(M-Cn)+1) 이 된다. 1200원에 대한 거스름돈을 거꾸로 계산해 보면
S(100)=1
S(200)=2
S(300)=3
S(400)=1
S(500)=1
S(600)=Min(S(600-500)+1,S(600-400)+1,S(600-100)+1)=Min(S(100)+1,S(200)+1,S(500)+1)=Min(2,3,2)=2
S(700)=Min(S(700-500)+1,S(700-400)+1,S(700-100)+1)=Min(S(200)+1,S(300)+1,S(600)+1)=Min(3,4,3)=3
....
S(1200)=Min(S(1200-500)+1,S(1200-400)+1,S(1200-100)+1)=Min(S(700)+1,S(800)+1,S(1100)+1)
이 되는 것이다. 따라서 거스름돈을 거꾸로 계산하고 중간 결과값들을 저장해 두고 사용하며, 원하는 값(1200원)에 도달할때까지 계산하면 된다.
다음은 이를 구현한 코드이다
이전 포스팅(Greedy Algorithm 과 거스름돈 예제) 의 경우 입력값을
3
500 400 100
1200
을 주게 되면 출력이
500
500
100
100
가 되어 최적값이 나오지 않는다. (해는 나오는데)
이번 포스팅의 동적 프로그래밍을 적용한 알고리즘은
3
500 400 100
1200
을 주게 되면
400
400
400
을 출력하며 정확한 값을 보여준다.
