탐욕 알고리즘: 답을 하나씩 고르는데, 미리 정한 기준에 따라서 매번 ‘가장 좋아 보이는’답을 선택함

• 최적화 문제를 푸는데 주로 사용
• 입력사례를 분할하지 않음
• 순서대로 답을 하나씩 모아서 최종 답을 구하는데, 가장 좋아 보이는 답을 선택
• 어떤 선택이든지 선택할 당시는 최적
• 최적인 해답을 얻는지 확인하는 절차를 반드시 거쳐야 함

거스름돈 문제를 푸는 탐욕 알고리즘을 공부

• 편의점의 게산대에서 일하는 은수는 현금을 내는 손님에게 거스름돈을 주는게 좋음
• 거스름돈이 870원인 경우 10원짜리 동전을 87개 주면 짜증..
• 최적의 답 = 동전의 개수가 최소가 되는 집합

위 문제의 알고리즘 푸는 순서

1. 빈손으로 시작함
2. 액면가가 가장 높은 동전을 집어 손에 놓음 → 선택 과정
3. 손에 있는 거스름돈의 총액이 거슬로 주어야 할 액수를 초과하는지 봄 → 적절성 검사
4. 만약 거스름돈의 총액이 거슬러주어야 할 액수를 초과하지 않으면, 방금 올려 놓은 동전은 거스름 돈에 포함됨
5. 만약 거스름돈의 총액이 거슬러 주어야 할 액수와 같은지 검사함 → 해답점검
6. 만약 같지 않다면 다시 선택과정으로 돌아가서 다른 동전을 찾고 되풀이 함