[알고리즘] 그리디(Greedy), 탐욕 알고리즘 | 거스름돈 문제

그리디(Greedy) 알고리즘이란?

그리디 알고리즘은 "매 선택에서 그 순간 당장 최적인 답을 선택" 하여 적합한 결과를 도출하는 알고리즘 설계 기법이다. 그리디 알고리즘은 최적 부분 구조(optimal substructure)를 가진 문제를 해결하는데 강점이 있다. 최적 부분구조란 매 순간의 최적해의 합이 문제에 대한 최적해여야 한다는 의미이다.  

 

예를 들어 누군가 A도시에서 B도시를 거쳐 C도시로 간다고 하자. 

 

greedy

A도시에서 B도시를 갈 때 가장 짧은 거리인 150km 경로를 선택하고, B도시에서 C도시로 갈 때 가장 짧은 거리인 140km 경로를 선택하면, 전체적으로도 최적의 경로가 된다. 매 순간 최적 경로의 합이 전체 경로의 최적 경로가 되었다. 이러한 최적 부분 구조를 가진 문제는 그리디 알고리즘으로 최적의 해로 해결 할 수 있다.

 

그러나 그리디 알고리즘은 모든 문제에서 최적의 해를 보장해주지는 않는다. 

 

예를 들어 다음과 같은 트리에서 한 레벨마다 하나의 노드씩을 선택해 그 합이 최대가 되도록 하는 문제가 있다고 하자.

 

최적의 해 보장하지 않음

실제 최적의 해는 7+1+99 = 107 이다.

하지만 그리디 알고리즘으로 그때마다 최적의 해를 고르면 7+9+13 = 29이다.

따라서 최적의 해를 구할 수 없고 그 차이 또한 크다. 

 

이러한 이유로 그리디 알고리즘을 사용할 수 있는 문제와 사용할 수 없는 문제를 잘 구분해서 적용해야 한다.

 

거스름돈 문제

그리디 알고리즘의 대표적이면서 간단한 예제인 거스름돈 문제에 대해 알아보자.

 

 

당신은 상점의 주인이다. 손님은 항상 1000원 짜리 지폐 한 장을 내고 물건을 사간다. 물건의 값은 1원 이상 1000원 미만이다. 당신은 500원, 100원, 50원, 10원, 5원, 1원 짜리 동전을 충분히 가지고 있다. 당신은 손님이 물건을 구매했을 때 동전의 개수를 최소한으로 하여 거스름돈을 주고 싶다. 어떻게 하면 될까?

 

아래의 예시를 보자.

 

 

 

 

풀이는 간단하다. 거스름돈의 잔액을 보고 가장 큰 금액의 동전을 계속해서 고르면 된다. 즉 매 순간 최적의 해를 택하면 되는 것이다. 

 

다음 문제를 풀어보는 것도 추천한다.

https://www.acmicpc.net/problem/5585

 

 

 

---