그리디 알고리즘
🤑 그리디 알고리즘 (Greedy Algorithm) 간략 정리
그리디 알고리즘은 '각 단계에서 최적이라고 생각되는 것을 선택'해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘이다.
🎯 특징 및 목표
그리디 알고리즘은 항상 최적의 값을 보장하지 않는다. 대신, **최적의 값에 '근사한 값'**을 목표로 한다. 특정 문제에서는 그리디 방식이 곧 최적의 해답이 되는 경우도 있지만, 그렇지 않은 경우도 많다는 점을 기억해야 한다.
🚶♂️ 3단계 절차
그리디 알고리즘은 보통 다음 세 단계를 거쳐 진행된다.
- 선택 절차 (Selection Procedure): 현재 상태에서 가장 최적의 선택을 찾는다. (예: 가장 가치가 큰 동전 선택)
- 적절성 검사 (Feasibility Check): 선택된 것이 문제의 조건에 만족하는지 확인한다. (예: 선택된 동전이 거스름돈보다 크지는 않은지)
- 해답 검사 (Solution Check): 현재까지의 선택이 전체 문제의 최종 답을 만족하는지 확인한다. (예: 모든 거스름돈을 다 채웠는지)
🪙 예시: 동전 개수가 최소인 거스름돈 문제
백준 14916번: 거스름돈 문제처럼 동전 개수를 최소로 하는 거스름돈 문제는 대표적인 그리디 알고리즘으로 해결할 수 있다.
- 선택: 현재 남은 거스름돈에 대해 가장 가치가 큰 동전부터 선택한다. (예: 5원, 2원 중 5원 먼저 선택)
- 적절성: 선택된 동전이 남은 거스름돈보다 크다면, 그 동전은 사용할 수 없으므로 다음으로 가치가 큰 동전으로 넘어간다.
- 해답: 모든 거스름돈을 다 내어주었다면, 동전 개수가 최소인 답을 찾은 것이다. 이 경우 그리디가 최적해를 보장한다.