그리디

• 매 선택마다 지금 이 순간 가장 최적인 답을 선택하는 알고리즘
• 최적해를 보장하지 않는다.
• 최적해를 구하는 알고리즘보다 빠른 경우가 많다. 대개 선형 시간 안에 끝난다.
• 크루스칼, 다익스트라 알고리즘 등에 사용된다.
• 직관적인 문제 풀이에 적합하다. ex) 자판기의 잔돈 반환 문제

예시 : 동전 반환 문제

지불 금액 : 5000원
요금 : 3140원
거스름돈 : 1860원

거스름돈인 1860원을 가장 큰 단위부터 처리한다.

1. 1860원 => 1000원 반환
2. 1860 - 1000 = 860원 => 500원 반환
3. 860 - 500 = 360원 => 100원 반환
   ...

거스름돈을 넘지 않는 가장 최고 단위의 화폐를 그때 그때 선택하면 된다.

출처

프로그래머스 데브코스 프론트엔드 Day4 [강의] 그리디