[알고리즘] 탐욕 알고리즘(Greedy algorithm)

---

1. 탐욕 알고리즘이란?

: 매순간 최적이라고 생각되는 값을 선택하는 알고리즘입니다.

이렇게만 설명을 들으면 이해하기 어려울 수 있는데요, 아래 예시를 통해 어떤건지 더 자세히 알아봅시다.

 

---

2. 탐욕 알고리즘 예시

동전을 거슬러주는 함수를 만들어봅시다.

coinList에는 큰 액수의 동전부터 들어가 있습니다.

탐욕 알고리즘은 아래와 같이 큰 액수의 동전부터 몇개 거슬러줄지 개수를 정합니다.

public void coinFunc(int pric, List<int> coinList)
{
    int totalCount = 0;
    int nowPrice = pric;
    for (int i = 0; i < coinList.Count; i++)
    {
        int nowCount = nowPrice / coinList[i];
        nowPrice -= coinList[i] * nowCount;
        totalCount += nowCount;
    }
}

 

이렇듯 탐욕알고리즘은 바로 당장의(큰 액수부터) 최선의 선택을 하는 알고리즘입니다.

16원을 거슬러줘야 하는 상황이라 예를 들어봅니다. 동전은 1원, 8원, 10원짜리 동전이 있습니다.

탐욕 알고리즘은 가장 큰 액수은 10원짜리 동전부터 거슬러주기 때문에 10원짜리 1개, 1원짜리 6개의 동전을 거슬러주게 됩니다. 하지만 8원짜리 동전으로 거슬러주게 된다면 최소의 동전 수인 2개로 거슬러줄 수 있습니다.

 

이렇게 더 좋은 수가 있을 수 있음에도 지금 순간 최선의 답을 선택하는 알고리즘을 탐욕 알고리즘이라 합니다.

매순간 최선의 답을 선택했음에도, 전체적인 부분을 봤을 때 최선이 아닐 수 있는 것입니다. 따라서 탐욕 알고리즘은 사용하기 전에 미리 검증 단계를 거쳐서 사용해도 괜찮은지 살펴보는 것이 좋습니다.