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

탐욕 알고리즘

• 최적의 값에 가장 가까운 값을 구하는 알고리즘이다.

 

알고리즘 예시: 동전 문제

4720원을 1원, 50원, 100원, 500원 동전으로 지불 할때, 가장 적은 동전의 개수로 지불하라.

coin_list = [500, 100, 50, 1]

def min_coin_count(value, coin_list):
    total_coin_count = 0
    details = list()
    coin_list.sort(reverse = True)
    for coin in coin_list:
        coin_num = value // coin
        total_coin_count += coin_num
        value -= coin_num * coin
        details.append([coin, coin_num])
    return total_coin_count, details

min_coin_count(4720, coin_list)

Out[2]:

(31, [[500, 9], [100, 2], [50, 0], [1, 20]])

 

알고리즘 예시: 부분 배낭 문제 (Fractional Knapsack Problem)

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

 

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

def get_max_value(data_list, capacity):

	# data_list를 가치/무게 값이 큰 순으로 정렬
    data_list = sorted(data_list, key=lambda x:x[1] / x[0], reverse=True)
    total_value = 0
    details = list()
    
    for data in data_list:
    	# capacity가 물건 전부를 다 담을 수 있는 경우
        if capacity - data[0] >= 0:
            capacity -= data[0]
            total_value += data[1]
            details.append([data[0], data[1], 1])
        
        # capacity가 충분치 않아서, 물건의 일부만 담을 수 있는 경우
        else:
        	# 물건의 몇 프로만 담을 수 있는가
            fraction = capacity / data[0]
            total_value += data[1] * fraction
            details.append([data[0], data[1], fraction])
            break
    return total_value, details

get_max_value(data_list, 30)

Out[9]:

(24.5, [[10, 10, 1], [15, 12, 1], [20, 10, 0.25]])

 

GitHub - DAWUNHAN/Algorithms-and-DataStructure: Algorithms and DataStructure with Python