[Python] 알고리즘 - 탐욕법(Greedy Algorithm)

[Python] 알고리즘 - 탐욕법(Greedy Algorithm)

---

• Greedy알고리즘은 간단히 말하면, 주어지는 모든 각 상황들에서 차례로 최적의 방법을 선택해나가는 것이다.
• 이는 불완전한 알고리즘이며, 무조건적으로 정답을 찾지는 못하는 알고리즘이다.
• 각 상황에서 최적을 선택했을 때, 그것이 전체 상황에서 최적이 아닌 경우가 있기 때문이다.
• 그래서 Greedy알고리즘은 "탐욕스러운 선택 조건"을 필요로 하며, 이것은 "각 상황의 선택하는 부분이 전체(영원)의 최적이어야 한다"라는 조건이다.

가장 유명한 예시로는 동전 문제가 있다.

def minimum_count(value, coins):
    total_num_coin = 0
    dic = {}
    for coin in coins:
        q = value//coin
        dic[coin] = q
        total_num_coin += q
        value -= coin*q
    return total_num_coin, dic

coins = [500, 100, 50, 10]
value = 7870
total_num_coin, dic = minimum_count(value, coins)

print(f'총 필요한 동전 최소갯수는 {total_num_coin}입니다')
for key in dic.keys():
    print('='*40)
    print(f'{key}원짜리 동전 개수는 {dic[key]}개입니다')

총 필요한 동전 최소갯수는 21입니다
========================================
500원짜리 동전 개수는 15개입니다
========================================
100원짜리 동전 개수는 3개입니다
========================================
50원짜리 동전 개수는 1개입니다
========================================
10원짜리 동전 개수는 2개입니다

 

일정 금액을 500,100,50,10원짜리 동전들로 지불할 때 지불하는 동전의 개수가 최소가 되게 하는 알고리즘이다.