[코딩 + 알고리즘 완주반] 20일차. 탐욕 알고리즘 (Greedy algorithm)

# 탐욕 알고리즘(Greedy Algorithm)

최적의 해에 가까운 값을 구하기 위해 사용

여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행

 

# 문제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 -= coin_num * coin
        details.append([coin, coin_num])
    return total_coin_count, details

 

# 문제 2) 부분 배낭 문제 (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 = 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

 

# 탐욕 알고리즘의 한계

탐욕 알고리즘은 근사치 추정에 활용

반드시 최적의 해를 구할 수 있는 것은 아님