[알고리즘] 탐욕법 : 그리디 알고리즘 Greedy Algorithm

 

탐욕법 : 그리디 알고리즘 (Greedy Algorithm)

 

 

그리디 알고리즘 (Greedy Algorithm)이란 여러 가지 선택지 중에서 지금 이 순간 최적이라고 생각되는 것을 선택하는 알고리즘이다.

 

지금 당장 최선의 선택을 하므로, 정답을 항상 구할 수는 없다.

 

하지만, 그리디 알고리즘 자체가 최적의 해를 구하는 것이 아니라, 상대적으로 최적의 해에 가까울 수 있는 해를 구하는 알고리즘이다.

 

 

 

 

예를 들어, 아래 그림과 같이 Start에서 층을 내려가면서 숫자의 최댓값을 구하는 문제가 있다고 하자.

       

Start에서 시작을 했을 때, 5와 10중에 최댓값에 더 최적화된 선택지는 10이 된다.

그리고 그다음 선택지인, 1과 2중에 최댓값에 더 최적화된 선택지는 2가 되므로,

위 문제를 그리디 알고리즘으로 해결하면 12의 답을 얻게 된다.

 

        

하지만, 문제 전체를 봤을 때, 최댓값은 5를 거쳐 9까지 가게 되는 14의 답이 최댓값이다.

 

 

 

이처럼, 최적의 해를 구할 수 없음에도 그리디 알고리즘은 시간복잡도가 낮기 때문에, 자주 사용되는 알고리즘이다.

 

 

---

그리디 알고리즘 조건

그리디 알고리즘으로 문제의 답을 구하기 위해서는 아래의 두 조건을 만족해야 한다.

 

1. Greedy-choice property (탐욕적인 선택)

각 단계에서 가장 이득을 보이는 선택을 하면 전체적으로 최적해를 구할 수 있어야 한다.

 

예를 들어, 거스름돈 1200원을 동전만을 사용해서 최소 개수로 거슬러 주려는 문제가 있다.

그렇다면 우리는 첫 동전으로 동전의 가장 큰 단위인 500원부터 선택을 하여야, 다음 단계에서 최적해에 가장 근접해진다. 두 번째 동전 역시, 100원 50원이 아닌 500원을 선택하여야 최적 해에 가장 근접해진다. 세 번째 네 번째도 마찬가지로, 최적 해를 구하기 위한 100원짜리 동전을 선택하면 최적 해를 구할 수 있게 된다. 

 

 

 

 

 

2. Optimal substructure ( 최적의 부분 구조)

전체 문제의 최적해는 하위 문제의 최적해를 포함하는 것이어야 한다.

 

예를 들어, 아래의 예시를 보자.

가산에서 수원으로 가려고 할 때, 최단거리를 구하는 문제이다.

이 문제의 최적의 해는,

가산에서 안양까지의 최단거리의 최적 해와 안양에서 수원까지의 최단거리의 최적 해의 합으로 이루어져 있다는 말이다.

 

 

 

 

이 두 조건을 만족하면 그리디 알고리즘을 적용할 수 있으며 이를 만족하지 않는다면 그리디 알고리즘을 사용하여도 정확한 해답을 얻지 못할 수 있다.

 

---

그리디 알고리즘 예제 - 거스름돈

Q.

5000원이 있고, 800원짜리 아이스크림을 사서 거스름돈을 받아야 할 때, 동전의 개수를 최소로 받는 경우는?

(단, 거스름돈의 종류는 500원, 100원, 50원, 10원이 있다.)

 

A.

위 문제는 주어진 동전이 모두 배수 관계에 있기 때문에, 그리디 알고리즘의 조건을 모두 만족한다.

따라서, 단위가 큰 동전을 우선적으로 선택해야 동전을 최소로 받을 수 있다.

 

거스름돈이 4200원 이므로,

500원 8개, 100원 2개의 과정으로 답을 도출할 수 있다.

 

답은 10개.

 

 

 

 

하지만, 이 문제에서 400원짜리 동전이 추가되면 어떻게 될까?

 

Q.

5000원이 있고, 800원짜리 아이스크림을 사서 거스름돈을 받아야 할 때, 동전의 개수를 최소로 받는 경우는?

(단, 거스름돈의 종류는 500원, 400원, 100원, 50원, 10원이 있다.)

 

A.

무턱대고 그리디 알고리즘으로 해결하려 하면, 500원 8개, 100원 2개의 과정으로 답을 도출하여,

10개라는 해를 얻는다.

 

하지만 최적의 해는, 500원 6개, 400원 3개

총 9개가 정답이다. 

 

400원짜리 동전이 추가가 됨으로써, 1200원을 거슬러 주어야 할 때,

500원 2개, 100원 2개보다는 400원 3개가 더 적은 개수를 거슬러주게 되는 것이다.

 

즉, 이 경우엔 가장 정답에 가까운 500원짜리 동전을 선택하는 것이 아니라, 400원짜리 동전을 선태해야 하므로,

앞서 말한 조건인 Greedy-choice property (탐욕적인 선택 속성)를 만족하지 못한다.

 

따라서, 이 문제는 조건을 만족하지 못하므로, 그리디 알고리즘보다는 DP 다이나믹 프로그래밍 기법을 사용하여 최적의 해를 구해야 한다.