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

 

---

 

그리디(Greedy)

그리디 알고리즘은 한마디로 "현재 상황에서 지금 당장 좋은 것만 고르는 방법"이라고 표현할 수 있다. 미래는 생각하지 않는 것이다.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이기 때문에 문제에서 "가장 큰 순서대로", "가장 작은 순서대로"와 같은 기준을 제시하기도 한다. 이에서 볼 수 있듯이 주로 정렬 알고리즘과 함께 출제되기도 한다.

그리디 알고리즘을 풀 때에는 결정한 문제 풀이 방법이 그때 당시의 최선의 선택이 전체에 걸쳐서도 최선인지를 확인하여야 한다. 그리디 알고리즘은 이런 특성 때문에 항상 최적의 값을 보장하지는 않는다. 따라서 최적의 값에 근사한 값을 목표로 하는 근사적인 방법이다.

 

---

그리디 알고리즘의 조건

1. 탐욕스런 선택 조건 (Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.

2. 최적 부분 구조 조건 (Optimal Substructure) : 문제에 대한 최적해가 부분 문제에 대해서도 최적해이다.

위의 두 조건이 성립해야 그리디 알고리즘을 통해 최적해를 구할 수 있다.

 

---

그리디 알고리즘의 풀이 방법

1. 선택 절차 (Selection Procedure) : 현재 상태에서의 최적의 해를 선택한다.

2. 적절성 검사 (Feasibility Check) : 선택한 해가 문제의 조건을 만족시키는지 확인한다.

3. 해답 검사 (Solution Check) : 기존의 문제가 해결되었는지 확인한다. 만약 해결되지 않았다면 1번부터 다시 반복한다.

 

---

예제 : 거스름돈

1260원의 거스름돈을 손님에게 주어야 할 때, 500원/100원/50원/10원짜리 동전이 충분히 있다면 손님에게 최소한의 동전 개수를 주려면 어떻게 해야 할까?

정답은 가능한 큰 값의 동전부터 거슬러주면 된다. 바로 500원 2개, 100원 2개, 50원 1개, 10원 1개로 총 6개인 경우이다. 이는 큰 값의 동전이 작은 값의 동전의 배수이기에 그리디 알고리즘을 적용할 수 있는 예시이기도 하다.