11. 알고리즘 탐욕 알고리즘 (그리디 greedy)

1. 탐욕 알고리즘이란?

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

2. 탐욕 알고리즘 예

문제 1 동전문제

• 지불해야하는 값이 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=value%coin
        details.append([coin, coin_num])
    return total_coin_count, details

min_coin_count(4720,coin_list)

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

문제 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=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]
            capacity -=data[0]*fraction
            total_value +=data[1]*fraction
            details.append([data[0],data[1],fraction])
    
    return total_value, details

get_max_value(data_list,30)

(24.5, [[10, 10, 1], [15, 12, 1], [20, 10, 0.25], [25, 8, 0.0], [30, 5, 0.0]])

여러 조합, 다음 단계를 생각하지 않고 현 단계의 최적의 경우만 생각하고 문제를 푸는 알고리즘이다.
최적의 해에 가까운 값을 구할 수는 있지만 완벽한 최적의 해라고 말하기는 어렵다. 따라서 근사치 추정에 활용된다.

예를 들어 서울에서 부산까지 가는 경로에서 톨게이트 마다 값이 다르다고 치면, 현재 톨게이트들의 값만 비교하여 저렴한 길로 가는 것이지, 각 톨게이트를 지나면 나오는 다음 톨게이트의 값들 까지 고려하지 않는다는 뜻이다.