12 Greedy Algorithm
[동영상] Greedy 방법이란?
동전단위가 100, 50, 10, 1원이 있을 때, 372원을 최소 개수의 동전으로 거슬러 주고 싶다면?
어떤 기준으로 동전을 선택했나? [스스로 답을 하기 바람]
Greedy(욕심쟁이) 방법: 목적을 달성하기 위해 현재의 정보만으로 가장 좋은 선택을 반복해서 답을 구성하는 방법
이러한 지역적인 선택(local decision)이 해(global solution)를 보장함을 증명하는 과정이 반드시 필요!- 예를 들어, 동전 교환 문제에서, 단위가 10원, 7원, 1원인 경우에 15원을 거슬러준다고 하자. greedy 방법에 따른 답은 10원 1개, 1원 5개로 6개의 동전이 필요하지만, 정답은 7원 2개, 1원 1개로 3개면 거슬러 쥬. 즉, 동전단위에 따라 greedy 방법이 최적 해(optimal solution)를 보장할 수도 그렇지 않을 수도(반례가 있을 수도) 있다.
