[알고리즘] 탐욕 알고리즘 Greedy

탐욕법 Greedy

• 최적의 해에 가까운 값을 구하기 위해 사용함
• 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행하여 최종적인 값을 구하는 방식
• 최적의 값이라고 단언할 수는 없음

---

예시 문제

동전 문제

• 지불해야하는 값이 4750원 일 때 10원 50원 100원 500원 동전으로 동전의 수가 가장 적게하여 지불하시오.
• 풀이
  • 금액이 큰 동전을 최대한으로 지불해야함
  • 탐욕법을 통해 매순간 최적의 동전 수를 구함

coin = [500, 100, 50, 10]

def min_coin_cnt(value, coin):
    total_coin_cnt = 0
    details = list()
    coin.sort(reverse = True)
    for co in coin:
        co_num = value // co
        total_coin_cnt += co_num
        value -= co_num * co
        details.append([co, co_num])
        
    return total_coin_cnt, details

min_coin_cnt(4720,coin)

(13, [[500, 9], [100, 2], [50, 0], [10, 2]])

---

부분 배낭 문제

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

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

get_max_value(data_list, 30)

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

---

매 순간 최적의 해를 구하지만 전체를 봤을 때 최적이 아닐 수 있음

 Greedy를 사용하여 가장 작은 값 찾기

 

---

한계

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