[자료구조/알고리즘 이론] 그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘

그리디 알고리즘의 핵심은 문제를 해결할 때 각 단계에서 매번 최선의 선택을 하는 것입니다. 당장 눈 앞의 선택지 중에 최선을 선택을 하여 결과적으로 최고/최적의 결과값을 도출해 내는 기법입니다. 이름이 Greedy Algorithm(탐욕 알고리즘)인 것을 생각해 보면 어느 정도 쉽게 이해가 됩니다.

 

그리디 알고리즘은 단계별로 그냥 최적의 선택만 하면 되기 때문에 단순하여 구현이 쉽다는 장점이 있습니다. 

 

그리디 알고리즘에도 치명적인 단점이 존재합니다. 바로 매 순간 현재 단계에서 최선의 선택을 하더라도, 전체 문제의 관점에서 보았을 때 최선의 선택이 아닐 수 있다는 점입니다. 이런 점 때문에 그리디 알고리즘을 사용할 때는 아래의 조건을 충족하는 문제에서만 사용하여야 합니다.

 

1. 현재의 선택이 이후 선택에 영향을 주지 않는 경우

2. 각 문제가 독립적이며 전체 문제의 해결 방법이 부분 문제의 해결 방법으로 구성되는 경우

 

위의 조건을 만족한다면 그리디 알고리즘을 활용할 수 있습니다.

 

그리디 알고리즘 구현

그리디 알고리즘을 사용하면 안 되는 경우와 사용해도 되는 경우를 예시를 통해 먼저 알아봅시다.

 

그리디 알고리즘을 사용할 수 없는 경우는 외판원 문제(TSP), 0-1 배낭문제(0-1 Knapsack Problem) 등이 있습니다. 외판원 문제의 경우 모든 경로를 탐색해야 하는데, 특정 경로가 전체 경로에 미치는 영향을 반드시 고려해야 합니다. 0-1 배낭문제도 마찬가지로 배낭의 물건들의 조합을 모두 고려해야 하며, 특정 아이템을 선택하는 것이 다른 아이템의 선택에 영향을 미칩니다.

 

즉, 앞서 설명한 1번과 2번 조건을 만족시키지 않습니다. 

 

아래의 문제들은 그리디 알고리즘을 적용할 수 있는 몇 가지 대표적인 예시입니다.

 

1. 다익스트라 알고리즘(Dijkstra Algorithm)

2. 크루스칼/프림 알고리즘(Kruskal's / Prim's Algorithm)

3. 분할 냅색 문제(Fractional Knapsack Problem)

 

위와 같은 예시가 있지만 가장 간단한 거스럼돈 문제를 통해 그리디 알고리즘 구현에 대해 알아봅시다.

 

380엔을 지불하기 위해 1000엔 지폐를 내는 상황을 가정해 봅시다. 받을 수 있는 잔돈의 단위로는 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 있습니다.

 

먼저 받아야 할 총 거스럼돈의 액수는 620엔입니다. 받을 수 있는 잔돈의 단위는 500, 100, 50...으로 정해져 있기 때문에 매 순간 남은 잔돈의 액수를 잔돈의 단위로 나눈 몫을 계산했을 때 가장 작은 몫을 선택하면 됩니다. 단 몫이 0보다 커야 한다는 조건이 있습니다. 몫의 값이 0보다 작으면 잔돈의 액수가 몫보다 작다는 뜻이니까요.

 

첫 번째 단계에서 500엔으로 나누었을 때 몫이 1로 최소가 됩니다. 따라서 현재 잔돈의 개수는 1개입니다.

 

두 번째 단계에서 남은 120엔을 100으로 나누었을 때 몫이 1로 최소가 됩니다. 따라서 현재 잔돈의 개수는 2개입니다.

 

세 번째 단계에서 남은 20엔을 10엔으로 나누었을 때 몫이 2로 최소가 됩니다. 따라서 최종 잔돈의 개수는 4개가 됩니다.

 

그리디 알고리즘 구현 코드

매번 몫의 min값을 갱신하는 방식으로 구현해도 되지만 어차피 coins가 내림차순 정렬이라 몫이 0보다만 크면 되기 때문에 for문으로 구현했습니다.

# greedy algorithm
def greedy(price, paid):
    coins = [500, 100, 50, 10, 5, 1]
    remain = price - paid
    answer = 0
    while remain:
        for c in coins:
            if remain // c > 0:
                div = remain // c
                answer += div
                remain -= c * div
                break
        else:
            return 0
        
    return answer

print(greedy(1000, 380))

 

References

https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://namu.wiki/w/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://www.quora.com/Why-don-t-we-use-greedy-approach-in-TSP-problem

https://www.geeksforgeeks.org/introduction-to-greedy-algorithm-data-structures-and-algorithm-tutorials/#examples-of-greedy-algorithm