탐욕법 (Greedy Algorithm)

탐욕법 (Greedy Algorithm) 은 최적해를 구하는 상황에서 사용하는 방법이다. 여러 경우 중 하나를 선택하고 싶은 경우, 각 상황마다 그 상황에서 가장 좋다고 생각하는 것을 선택해 나가는 방식으로 진행하여 답을 구하는 알고리즘이다. 그러나 그 상황에서 가장 좋다고 생각하는 것이 무조건적으로 가장 좋은 결과를 얻는 것은 당연히 아니다. 예를 들어

 

위와 같은 상황에서 0에서 시작했을 때 탐욕법을 사용하면 첫 번째 선택에서 가장 큰 결과값인 10의 경로를 택할 것이고, 그 다음 선택에서 가장 큰 결과값인 40의 경로를 택하여 총 50의 보상을 받게되지만, 실제 가장 큰 보상을 받을 수 있는 경로는 5를 선택한 후 100을 선택하는 경로이다 (최적의 해).

 

그러나 탐욕법은 최적의 해와 근접한 답을 주거나, 어떤 경우에는 탐욕법의 결과가 곧 정답인 문제들이 있다. 가장 유명한 예인 동전 지불에 대해 알아보자.

 

거스름돈을 돌려줘야 할 때, 가장 적은 수의 동전을 주는 방법을 탐욕법으로 알아내 보자.

 

내 정답

 

coins = [500, 100, 50, 10]

def greedy_coins(money):
    result = []
    count = 0
    for coin in coins:
        num_coin = money // coin
        count += num_coin
        result.append(num_coin)
        money = money % coin
    return result, count

m = 5380
r, c = greedy_coins(m)
print(r, c)

 

결과

 

PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/11. 동적 계획법/greedy_coins.py"
[10, 3, 1, 3] 17

 

첫 번째 반환값은 각 동전의 개수, 두 번째 반환값은 총 동전 개수이다.

 

출처

https://gomguard.tistory.com/119