알고리즘 : 탐욕 알고리즘

탐욕 알고리즘은?

• Greedy algorithm 또는 탐욕 알고리즘 이라고 함
• 최적의 해에 가까운 값을 구하기 위해 사용
• 여러 경우 중 하나를 결정해야 할 때마다 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행, 최종값을 구함

 

탐욕 알고리즘의 예

예시문제1 : 동전

- 지불해야 하는 값이 4830원 일 때 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(4830, coin_list)
#출력결과 (31, [[500, 9], [100,3], [50, 0], [1, 30]])

 

예시문제2 : 부분 배낭 문제(Fractional Knapsack Problem)

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

물건(i)	물건1	물건2	물건3	물건4	물건5
무게(w)	10	15	20	25	30
가치(v)	10	12	10	8	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=lamba x: x[1] / x[0], reverse=True)
    total_value = 0
    datails = 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

get_max_value(data_list, 30)
#출력결과 (24.5, [[10, 10, 1], [15, 12, 1], [20, 10, 0.25]])

 

탐욕 알고리즘의 한계

• 탐욕 알고리즘은 근사치 추정에 활용 (반드시 최적의 해를 구할 수 있는 것은 아니기 때문)
• 최적의 해에 가까운 값을 구하는 방법 중 하나임