[파이썬][알고리즘] 탐욕 알고리즘

탐욕 알고리즘

• 최적의 해에 가까운 값을 구하기 위한 방법이다.
• 여러 경우가 있을 때 매 순간 조건에 맞는 최적의 경우를 찾아나가는 방식이다.

예시

1. 동전 문제
   • 지불해야 할 값이 6870원 일 때 10, 50, 100, 500원 동전으로 가장 적은 수의 동전으로 계산
     • 가장 큰 동전부터 지불

coins = [500, 100, 50, 1]

def coin_count(price, coins):
    coin_count = 0
    ledger = list()
    coins.sort(reverse=True) # 내림 차순으로 정리
    for coin in coins:
        coin_num = price // coin
        coin_count += coin_num
        price -= coin_num * coin
        ledger.append([coin, coin_num])
    return coin_count, ledger

coin_count(6870, coins)

(37, [[500, 13], [100, 3], [50, 1], [1, 20]])

2. 부분 배낭 문제
   • 무게 제한이 k인 배닝에 최대 가치를 가지도록 물건을 넣는 문제
     • 물건은 무게(w)와 가치(v)로 표현
     • 물건은 쪼갤 수 있다.

  

thing_info = [(10, 10), (15, 12), (20, 10), (25, 8), (30, 5)]

# 단위 무게 당 가장 높은 가치를 가진 순으로 정렬
thing_info = sorted(thing_info, key = lambda x: x[1] / x[0], reverse=True) 
thing_info

[(10, 10), (15, 12), (20, 10), (25, 8), (30, 5)]

def max_value(thing_info, capacity):
    total_value = 0
    bag_thing = list()

    for info in thing_info:
        if capacity - info[0] >= 0:
            capacity -= info[0]
            total_value += info[1]
            bag_thing.append([info[0], info[1], 1])
        else:
            fraction = capacity / info[0]
            total_value += info[1] * fraction
            bag_thing.append([info[0], info[1], fraction])
            break
    return total_value, bag_thing

max_value(thing_info, 50)

(33.6, [[10, 10, 1], [15, 12, 1], [20, 10, 1], [25, 8, 0.2]])

탐욕 알고리즘의 한계

• 근사치를 추정하기 위해 사용된다.
• 반드시 최적의 해를 구할 수 있는 것은 아니다.
  • 최적의 값과 다른 값을 나타낼 수도 있다.