[알고리즘] 그리디 (Greedy)

그리디 (Greedy)

• Greedy Algorithm은 말 그대로 탐욕 알고리즘으로 부르며, 매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘이다.
• 매 선택마다 그 순간에 대해서는 최적이지만, 그 선택들이 모였을 때 최적해를 보장해주지 않는다.

그리디 알고리즘의 특징

• 보통 최적해를 구하는 알고리즘보다 빠른 경우가 많다.
• 크루스칼, 다익스트라 알고리즘 등에 사용된다.
• 직관적인 문제 풀이에 적합하다.

그리디 알고리즘의 문제 예

동전 반환 문제

만약 손님이 지불한 돈과 구입한 물건을 계산한 후 거스름돈을 지폐 단위가 최대한 큰 순으로 거슬러 줘야 한다면 어떻게 해야 될까?

지불 금액 = 5,000원
물건 금액 = 3,250원
거스름돈 = 1,750원

정답은 간단하다
거스름돈의 가장 큰 단위 부터 거슬러 주면 된다.

1,000원 X 1
500원 X 1
100원 X 2
50원 X 1