[이코테] 그리디 알고리즘 (탐욕법)

국내 알고리즘 교재에서 '탐욕법'으로 소개되는 그리디 알고리즘은 나중에 미칠 영향을 고려하지 않고 당장 좋은 것만 고르는 방법이다. 진정한 상남자식 알고리즘이다. 기본 구조를 암기해야 하는 정렬 알고리즘이나 최단 경로 등과 달리, 비교적 사전 지식으로부터 자유롭다는 특성을 갖고 있다. 바꿔 말하면 그만큼 다양하게 출제될 수 있기 때문에, 많은 유형을 접해보고 공부하는 훈련이 필요하다. 창의성과 아이디어는 덤이다. '가장 좋은 것'이라는 판단을 위해서는 기준이 주어져야 하는데, 그리디 알고리즘 유형의 문제들에서는 '가장 큰 순서대로' 혹은 '가장 작은 순서대로' 등의 기준을 알게 모르게 제시해 준다. 특히 정렬 알고리즘과 짝을 이뤄 출제된다. 예제 3-1 거스름돈 당신은 음식점의 계산을 도와주는 점원이다...

원문링크 : [이코테] 그리디 알고리즘 (탐욕법)