Greedy Algorithm

한글로 번역하면 탐욕적알고리즘?
결정을 해야 할 때마다 미래에 대한 생각 없이 그 순간에 가장 최선의 선택을 하는 알고리즘을 의미한다.
순간 선택은 그 당시 최적(locally optimal)이다.
하지만, 최종적으로 최적(globally optimal)이라는 보장은 없다.
따라서, 탐욕적인 알고리즘은 항상 최적의 해를 주는지 검증해야 한다.

탐욕적인 알고리즘 설계 절차 :
선정과정(selection procedure)
현재 상태에서 가장 좋으리라고 생각되는(greedy) 해답을 찾아서 해답모음(solution set)에 포함시킨다.

적정성점검(feasibility check)
새로 얻은 해답모음이 적절한지를 결정한다.

해답점검(solution check)
새로 얻은 해답모음이 최적의 해인지를 결정한다.

거스름돈 문제
문제: 동전의 개수가 최소가 되도록 거스름 돈을 주자.
탐욕적인 알고리즘
거스름돈을 x라 하자.
먼저, 가치가 가장 높은 동전부터 x가 초과되지 않도록 계속 내준다.
이 과정을 가치가 높은 동전부터 내림순으로 총액이 정확히 x가 될 때까지 계속한다.