그리디 알고리즘

미리 정한 기준에 따라서 매번 현시점에 가장 유리한 해법을 선택하는 알고리즘

 

[특징]

1)최적해 미보장 : 순간(Local)의 선택은 최적이지만 최종(Global)해는 보장 못함

2)빠른 최적화 :  정확한 해보다는 빠른 단계적 최적화에 중점

3) 설계 간단 : 설계가 매우 간단하고 다양한 영역에 응용 가능

- 현 우리나라 동전 체계로는 항상 최적의 답이 보장됨

 

[절차]

1)해선택 : 현재 상태에서 가장 적합한 해를 찾아 해모음에 포함((지문) 가장 가치가 높은 동전 선택)

2)적정성 검사 : 새로 갱신된 해답모음이 적절한지 검사(지문 : 거스름돈 총액 초과 여부 검사)

3)해검사 : 새로 얻은 해답모음이 최적의 해인지 결정(지문:해가 총 거스름돈 총액에 도달했는지 검사)