그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)

그리디 알고리즘 (욕심쟁이 알고리즘, 탐욕 알고리즘, Greedy Algorithm 등)이란

문제를 해결하는 과정에서 현재 상태에서 가장 최적의 해를 선택하여 문제를 해결하는 방법을 의미합니다.

 

동적 계획법과 자주 같이 언급되는 알고리즘으로 모든 경우를 살펴본 뒤 최적의 해를 구하는 동적 계획법과는 다르게

현재 상태에서 가장 최적이라고 여겨지는 해답만을 선택하기 때문에 동적계획법에 비해 속도가 빠르다는 장점이 있으나

모든 경우를 살펴보는 것이 아니기 때문에 늘 최적의 해라는 보장은 없다는 단점이 있습니다.

동적 계획법 (다이나믹 프로그래밍, Dynamic programming)

 

그리디 알고리즘으로 해결할 수 있는 가장 대표적인 문제는 거스름돈 문제입니다.

 

---

거스름돈 문제

 

500원, 100원, 50원, 10원, 5원, 1원 동전들이 충분히 존재하고 값이 n인 물건을 구매하고 1000원을 냈다고 가정하자.

이 때 거스름돈으로 받을 수 있는 동전의 총 개수 중 최소값은?

---

위의 문제를 해결하기 위해 사용할 수 있는 대표적인 알고리즘이 그리디 알고리즘입니다.

동전을 최소로 주기 위해서는 가치가 큰 동전들의 수가 많아야 한다. 예를 들어 600원을 거스름돈으로 주어야한다면

100원짜리 6개를 주는 것보다 500원짜리 1개와 100원짜리 1개 즉 2개를 주는 경우가 동전을 훨씬 적게 줄 수 있습니다.

이러한 것을 고려해 보았을 때 거스름돈을 줄 때 가치가 큰 동전들을 많이 주는 것이 동전을 줄일 수 있는 방법입니다.

 

이를 그리디 알고리즘을 적용하여 해결하면 다음과 같습니다.

int Greedy(int n)
{
    int count = 0;
    n = 1000 - n;
    while (n > 0)
    {
        if (n >= 500)
            n -= 500;
        else if (n >= 100)
            n -= 100;
        else if (n >= 50)
            n -= 50;
        else if (n >= 10)
            n -= 10;
        else if (n >= 5)
            n -= 5;
        else 
            n -= 1;
        count++;
    }
    return count;
}

 현재 주어야할 금액 중 남은 금액이 500원보다 크거나 같으면 500원을 주고 500원보다 작고 100원보다 크거나 같으면 100원을 주는 방식을 반복하여 가치가 가장 큰 동전의 수를 증가시켜 총 동전의 수를 줄일 수 있습니다.

 

위의 방식을 해석해보면 현재 주어야할 금액 중 가장 큰 가치의 동전, 즉 현재 상황에서 가장 최적의 해를 고르는 것을 반복하여 문제를 해결한 것을 알 수 있습니다.