알고리즘 - Greedy Algorithm(탐욕 알고리즘)

Greedy Algorithm 이란?

Greedy Algorithm(탐욕 알고리즘) 최적해를 구하는 방법에 사용되는 알고리즘 중 하나이다. Greedy Algorithm은 각 단계에서 가장 최적인 선택으로 하는 것이며, 한번 선택된 것을 번복하지 않는다.

Greedy Algorithm 다음과 같은 경우에 유용하게 사용 가능하다.

1. 최적화 문제에서 최적해를 구하고자 할 때
2. 제한적인 자원을 최대한 활용해야 할 때
3. 간단하고 효율적인 알고리즘을 구현해야 할 때

하지만 Greedy Algorithm은 항상 최적해를 보장하지 않는다 상황마다 최적해와 다른 결과를 도출할 수도 있기때문에, 상황에 맞게 최적해를 보장할 수 있는지 확인하는것이 필요하다.

---

Greedy Algorithm 예시

Greedy Algorithm의 대표적인 동전, 거스름돈 예시를 들어 설명해보겠다.

320원을 거슬러 주기위해 동전 500원, 100원, 50원, 10원 동전으로 Greedy Algorithm을 사용하여 최소한의 동전으로 거슬러 주는 방법은 다음과 같다

1. 가장 큰 500원으로 최대한 거슬러 줄 수 있는 만큼 거슬러 준다. 하지만 320원 보다 큰 500원은 사용할 수 없으므로 500원 동전은 사용하지 않는다.

2. 다음으로 100원으로 최대한 거슬러 줄 수 있는 만큼 거슬러준다. 320원을 100원으로 나눈 몫이 3이므로 300원을 거슬러 준다. 즉, 100원 동전을 3개 사용한다.

3. 다음으로 50원 동전을 사용하는데 500원과 마찬가지로 잔여금이 20원이기 때문에 사용하지 않고, 10원 동전을 사용하여 20원을 거슬러 준다. 즉, 10원 동전을 2개 사용한다.

최종적으로 320원을 만드는 데는 100원 동전 3개와 10원 동전 2개가 사용 된다는 것을 알 수 있다.

하지만 앞서 Greedy Algorithm은 항상 최적해를 보장하지 않는다고 했는데, 만약 800원을 거슬러 줘야하는데 500원 400원 100원이 있다고 한다면 Greedy Algorithm에 따르면 500원 + 100원 + 100원 + 100원을 거슬러 줘야한다고 나온다.

하지만 최적해는 400원 + 400원의 동전을 거슬러 주는 것이다.

Greedy Algorithm을 사용하여 해법을 찾았을 때는 그 최적해를 보장 할 수 있는지 확인 해야한다.