그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘

매 선택 시, 현재 시점에서 가장 최적인 값만을 선택하여 결과를 도출하는 알고리즘

말 그대로, 현재 나한테 제일 이익이 되는 것은 무엇일지 보고 해당 값을 선택해가는 알고리즘이다. 이렇게 각 단계에서 최선의 선택을 하는 것이, 전체적으로도 최선임을 가정한 상태로 해결하게 된다.

 

다이나믹 프로그래밍(DP)와 같이, 매 순간의 최적값이 전체 문제의 최적값이라는 점은 동일하지만, DP와 다르게 꼭 세부 문제들이 동일한 구조는 아니어도 된다. 또한, 현재 시점에서의 최적 해결 방법만을 찾으면 되는 알고리즘이므로, 백트래킹과 같이 모든 경로를 탐색할 필요는 없기 때문에 연산 속도 측면에서 이득을 볼 수 있다. 그러나 반대로 생각하면 현재 시점에서의 최적 방법의 합이 전체적으로는 최적 해결 방법이 아닐 수도 있다.

 

다음과 같이 그리디 알고리즘을 적용할 수 있는 조건을 정의할 수 있다.

1. Optimal Substructure(최적 부분 구조): 전체 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성되어야 한다. → DP와 동일!
2. Greedy Choice Property(탐욕 선택 속성): 이전에 결정한 최적의 선택이, 이후의 최적 선택에 영향을 주지 않아야 한다.

이러한 그리디 알고리즘은 특정한 방법으로 풀 수 있는 것이 아니라, 문제의 상황에 따라 아이디어를 파악하고 알고리즘을 설계해야 한다. 그리디 알고리즘 문제에 접근하는 방식은 1) 관찰을 통해서 해결할 탐색 범위를 줄이는 방법을 고안하고, 2) 줄어든 탐색 범위에서 최적해를 선택했을 때, 이것이 전체 범위에서도 최적해인지를 증명하는 것과 같이 두 단계로 이루어진다. 즉, 가설 설정 → 증명의 단계로 접근하는 방식을 가져야 한다.

 

거스름돈 문제

거스름돈 문제는 그리디 알고리즘을 사용할 수 있는 대표적인 문제이다. (프로그래머스 예시)

Q. 거스름돈 N원을 500원, 100원, 50원, 10원 동전 만으로 거슬러줄 때, 제일 동전을 적게 사용하는 경우는 몇 개의 동전을 사용해야 하는가?

이때 아래와 같은 명제를 세울 수 있다:

• 동전 개수를 최소화 하려면, 500원 → 100원 → 50원 → 10원 순으로 동전을 사용해야 한다.

해당 명제로부터 “동전을 최소로 소모하려면, 100원은 4개 이하, 50원은 1개 이하, 10원은 4개 이하로 사용해야한다.”라는 다른 정리를 도출할 수 있다. 이를 100원에 대해서 우선 증명하면,

• 만약, 100원을 5개 이상 사용했을 때, 동전을 최소로 사용할 수 있다고 하자.
• 100원을 5개 이상 사용하는 순간, 이는 500원 동전으로 대체될 수 있다.
• 이때 100원을 5개 사용하는 것보다, 500원을 1개 사용하는 것이 항상 더 적은 동전을 사용하게 된다. 따라서 위 가정은 모순이다.

50원, 10원의 경우도 위와 같이 증명할 수 있다. 따라서, 100원, 50원, 10원 동전을 사용하는 최대 개수는 정해지게 되고, 이 최대 개수를 모두 사용했을 때가 490원이므로, 해당 금액 이상의 거스름돈에 대해서는 500원 동전을 우선적으로 사용하지 않는다면 아래 금액의 동전을 추가로 소모해야 한다. 따라서, 500원 동전의 경우를 제일 먼저 생각해야 한다. 차례로, 100원, 50원, 10원의 경우도 위와 같은 사고 흐름으로 증명할 수 있다.

 

Python으로 위 문제를 해결하는 코드를 작성하면 아래와 같다.

def solution(N: int):
    """N: 거스름돈의 크기"""
    coin_list = [500, 100, 50, 10]
    count = 0

    for coin in coin_list:
        while N >= coin:
            N -= coin
            count += 1

    return count

 

그렇다면 모든 거스름돈 문제에서 그리디 알고리즘을 사용하면 될까?

 

아쉽게도, 사용할 수 있는 동전이 배수관계일 때만 그리디 알고리즘이 성립하게 된다. 만약, 1/9/10원 동전이 있고, 거스름돈이 18원이라고 하자. 큰 동전부터 선택하는 방법을 이용한다면 (10, 1, 1, 1, 1, 1, 1, 1, 1) 총 9개의 동전을 사용해야 하지만, 실제로는 (9, 9) 2개의 동전을 선택하는 것이 최소이다. 따라서, 이와 같은 경우는 다른 방법을 택해야 한다.

 

⇒ 즉, 지금 당장은 손해여도 나중에 이득이 되는 경우가 존재한다면 이는 그리디 알고리즘으로 해결할 수 없다!

 

그리디 알고리즘으로 풀 수 없는 문제

그리디 알고리즘으로 풀 수 있는 문제는 (시간복잡도는 느리지만) DP나 백트래킹과 같은 방법으로 해결할 수는 있다. 그렇지만, 반대로 그리디 알고리즘으로 풀 수 있을 것 같으나 풀 수 없는 문제가 존재한다.

 

0-1 Kanpsack 알고리즘, Parametric Search와 같이 그리디로 풀 수 없는데 그리디 알고리즘으로 해결할 수 있는 것처럼 보이는 문제들을 빠르게 파악할 수 있어야 한다.

 

References

• 바킹독의 실전 알고리즘 0x11강: 그리디
• https://memodayoungee.tistory.com/103
• https://6mini.github.io/computer science/2021/12/04/dp-greedy/