[알고리즘] 그리디 알고리즘 _ 백준11047 파이썬

● Greedy Algorithm

 

 

그리디(Greedy) 알고리즘은 'greedy'(탐욕, 욕심쟁이)라는 뜻에서 유추할 수 있듯이 멀리 생각하지 않고 지금 당장의 단계에서 가장 좋은(최선의) 선택을 하는 문제해결 방법입니다. 각 단계에서 가장 좋은 선택을 했을 때 전체적으로 최선의 해결방법이 되길 바라는 알고리즘입니다. 

 

그리디 알고리즘은 동적프로그래밍(다이나믹, DP)에서 지나치게 많은 연산과정을 거치는 것을 보완하기 위해 나온 개념이지만, 모든 문제에서 그리디 알고리즘이 최선의 선택을 보장하는 것은 아니라는 단점이 있습니다. 사실 대다수의 경우 올바른 답을 주진 않지만 쉽고 적은 연산으로 문제를 해결하는데 좋은 결과를 보장한다는 점에서 많이 사용되는 개념입니다.

 

 

---

 

 

예시1 - 백준 11047 동전0

그리디 알고리즘 유형으로 유명한 백준 11047번의 문제입니다.

 

 

문제

 

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

 

 

입력

 

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

 

 

 

출력

 

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

 

 

예제 입력

 

10 4200

1 5 10 50 100 500 1000 5000 10000 50000

 

 

 

예제 출력

6

 

 

 

D[i] = i를 만들기 위해 필요한 동전 갯수의 최솟값

이라고 가정하면 D[i] = min(D[i-A[0]], D[i - A[1]], D[i - A[2]], ... ) + 1  이 됩니다.

이 경우 시간 복잡도가 O(NK)이기 때문에 시간 초과가 발생합니다. 따라서 이 문제는 그리디로 해결해야 합니다.

 

 

직관적으로 생각했을 때, 만약 10, 50, 100, 500원의 동전들로 물건의 가격을 지불할 때 동전을 적게 내고 싶으면 어떤 방식으로 지불해야 할까요? 일단 500원의 동전을 최대한 많이 쓰고 이후 100, 50, 10순으로 많이 써야할 것 입니다.

이 방법이 가장 돈전을 적게 소모하는 방법을 증명할 수 있을까요?

 

그리디 알고리즘을 사용하려면 해당 알고리즘이 성립함을 수학적으로 엄밀히 증명해야 합니다.

 

 

증명

 

가정1 : 동전을 최소로 소모하면서 물건값을 지불하려면 10, 100원짜리 동전은 4개 이하, 50원 동전은 1개 이하로 사용되어야 한다.

 

 

증명1 : 귀류법 이용, 10, 100원짜리 동전을 5개 이상 사용하거나 50원 동전을 2개 이상 사용해서 동전을 최소로 소모하면서 물건 값을 지불했다고 하자. 그러면 10원 100원짜리 동전을 5개 이상 사용한다고 하면 50원 500원 동전으로 대체해 동전의 갯수를 더 줄일 수 있고 50원 동전을 2개 이상 사용한다면 100원 동전으로 대체해 동전의 갯수를 줄일 수 있으므로 가정에 모순된다. 따라서 가정은 참이다.

 

 

가정2 : 동전을 최소로 소모하면서 물건값을 지불하려면 우선 500원짜리 동전을 최대한 많이 사용해야 한다.

 

 

증명2 : 가정1에서 동전을 최소로 소모하면서 물건값을 지불하려면 10원 100원짜리 동전은 4개 이하, 50원짜리 동전은 1개 이하로 사용되어야 한다. 이 경우 10, 50, 100원 동전으로는 물건 값을 최대 10*5 + 50*1 + 100*4 = 490원 밖에 감당할 수 없다. 만약 500원 동전을 최대한 다 사용하지 않으면 10, 50, 100원 동전으로 감당해야 하는 물건 값이 500원 이상이 되기 때문에 가정2가 증명된다.

 

 

결론

Lemma 2를 통해 동전을 최소로 소모하면서 물건값을 지불하려면 우선 500원 동전을 최대한 많이 사용해야 한다는 사실을 알았습니다. 마찬가지 논리를 이용하면 500원 동전을 최대한 많이 사용한 이후에는 100원 동전을, 그 이후에는 50원을, 마지막으로 10원 동전을 최대한 많이 사용해야함을 증명할 수 있고, 그리디 알고리즘의 정당성 증명이 끝났습니다.

 

500/100/50/10원 동전을 일반화시킨 문제에서의 상황도 A(i)​가 A(i-1​)의 배수이기 때문에 동일한 방식으로 A(n-1)​부터 차례로 최대한 많이 사용하는 알고리즘이 성립하고, 또 정당성을 증명할 수 있습니다

 

 

파이썬 코드

def greedy(coins, k):
    coins = reversed(coins)
    count = 0
    total = k
    for coin in coins:
        if coin <= total and total % coin >= 0:
            cnt = total // coin
            count += cnt
            total -= coin*cnt
        if total == 0:
            break
    return count
 
if __name__ == "__main__":
    n, k = map(int, input().split())
    coins = []
    for i in range(n):
        coin = int(input())
        coins.append(coin)
    print(greedy(coins, k))

 

 

다른 문제 풀어보기 백준 1931번:회의실배정, 백준 2217:로프

 

사실 그리디 알고리즘은 대다수 문제에서 사용할 수 없습니다.(잘못된 그리디 문제 예시 - knapsack, 백준1477)

 

하지만, 코딩테스트에서 그리디 문제가 나온다면 11047번이나 1931번 문제처럼 그리디로 해결 가능한 수준일 것이라고 합니다. 그 이상 이라면 어차피 대부분의 사람이 풀어내지 못해 의미가 없기 때문입니다.

 

 

 

 

[References]

 

[실전알고리즘]0x0A강-그리디_구버전