탐욕 알고리즘 이란?
- 최적의 해에 가까운 값을 구하기 위해 사용됨
- 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최적적인 값을 구하는 방식
탐욕 알고리즘 예
문제1: 동전 문제
- 지불해야 하는 값이 4720원일 때 1원 50원 100원 500원 동전으로 동전의 수가 가장 적게 지불하시오.
- 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능
- 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨
coin_list = [500, 100, 50, 1]
def min_coin_count(value, coin_list):
total_coin_count = 0
details = []
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
print(min_coin_count(4720, coin_list))실행결과
(31, [[500, 9], [100, 2], [50, 0], [1, 20]])
- 4개의 동전의 종류로 값을 계산할 때 500원 갯수를 계산할 때 다른 동전의 조합들을 고려하지 않는다. 지금 그 순간의 그 동전의 값으로만 계산한다. 그래서 매순간 최적이라고 생각되는 경우를 선택하는 알고리즘을 탐욕 알고리즘(Greedy Algorithm)이라고 한다.
문제2: 부분 배낭 문제 (Fractional Knapsack Problem)
- 무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제
- 각 물건은 무제(w)와 가치(v)로 표현될 수 있음
- 물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있음, 그래서 Fractional Knapsack Problem으로 부름
- Fractional Knapsack Problem의 반대로 물건을 쪼개서 넣을 수 없는 배낭 문제도 존재함(0/1 Knapsack Problem으로 부름)
- 물건1:(w=10, v=10) 물건2:(w=15, v=12) 물건3:(w=20, v=10) 물건4:(w=25, v=8) 물건5:(w=30, v=5)
data_list = [(10,10), (15,12), (20,10), (25,8), (30,5)]
def get_max_value(data_list, capacity):
data_list = sorted(data_list, key=lambda x:x[1]/x[0], reverse=True)
total_value = 0
details = list()
for data in data_list:
if capacity - data[0] >= 0:
capacity -= data[0]
total_value += data[1]
details.append([data[0], data[1], 1])
else:
fraction = capacity / data[0]
total_value += data[1] * fraction
details.append([data[0], data[1], fraction])
break
return total_value, details
print(get_max_value(data_list, 30))실행결과
(24.5, [[10, 10, 1], [15, 12, 1], [20, 10, 0.25]])
위 사진에서 '시작'노드에서 시작해서 가장 작은 값을 찾아 leaf node까지 가능 경로를 찾을 시에 탐욕 알고리즘 적용시 시작 -> 7 -> 12를 선택하게 되므로 7 + 12 = 19가 되지만 실제로 가장 작은 값은 시작 -> 10 -> 5를 선택하게 되므로 10 + 5 = 15가 답이다.
