그리디 알고리즘(탐욕법) Greedy Algorithm
최적해를 구하는 상황에서 사용하는 방법이다.
그 상황에서 가장 좋다고 판단되는 것을 선택해 나가는 방식이다.
그렇기 때문에 가장 좋은 결과가 보장되지는 않는다.
예시 1
동전 개수를 가장 적게 사용하여 10원, 100원, 500원으로 710원 만들기
500원 1개
100원 2개
10원 1개
이 예시는 간단하여 탐욕법으로도 올바른 답이 나온다.
예시 2
ex) 10원, 30원, 40원, 50원으로 70원 만들기
50원 1개, 10원 2개 --> 총 3개의 동전 이용
40원 1개, 30원 1개 --> 총 2개의 동전 이용
하지만, 이럴 경우에는 탐욕법이 가장 좋은 답을 도출해내지 못한다.
이럴 경우에는 동적 계획법을 이용할 수 있다.
출처: https://www.youtube.com/watch?v=CxBYY7XTQvI
동적 계획법 Dynamic Programming
전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용해서 전체 문제를 해결하는 방식이다.
이 때문에 그리디 알고리즘보다 더 정확한 해를 도출해낸다.
예시
2원, 3원, 5원 동전으로 11원 만들기
F(11) = 11원을 만드는데 필요한 동전 개수
F(11)는 F(9), F(8), F(6) 각각의 경우에 1을 더하면 된다.
(F(9)일 경우에는 2원 동전 하나 더, F(8)의 경우 3원 동전 하나 더, F(6)일 경우 5원 동전 하나 더)
F(11)=Min( F(9),F(8),F(6) )+1
--> F(n)=Min( F(n-2)+F(n-3)+F(n-5) )+1
가능하지 않을 때는 -1
F(0)=0
F(1)=-1
F(2)=1
F(3)=1
F(4)=Min( F(2),F(1),F(-1) )+1 = 2
F(5)=Min( F(3),F(2),F(0) )+1 = 1
...
F(11)=3
