탐욕 알고리즘(Greedy Algorithm)

1. 탐욕 알고리즘(Greedy algorithm)이란?

• 최적의 해에 가까운 값을 구하기 위해 사용됨(완벽하게 최적의 해는 아님)
• 여러 경우 중 하나를 결정해야 할 때마다, 매 순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 최종적인 값을 구하는 방식

 

2. 탐욕 알고리즘 예

 

문제 1 : 동전 문제

• 지불해야 하는 값이 4720원일 때 1원 50원 100원 500원 동전으로 지불하는 경우 중 동전의 수가 가장 적은 경우를 구하시오
• 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능
• 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 생각하면 됨

def min_coin_count(value, coin_list):   #value는 지불값
    total_count = 0
    details = list()
    coin_list.sort(reverse = True)      #내림차순으로 정렬됨
    for coin in coin_list:
        coin_num = value // coin
        total_count += coin_num
        value -= coin_num * coin
        details.append([coin, coin_num])
    return total_count, details

coin_list = [500, 100, 50, 1]

min_coin_count(4720, coin_list)

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

 

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

• 무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제
• 각 물건은 무게(w)와 가치(v)로 표현될 수 있음
• 물건을 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있음. 그래서 Fractional Knapsack Problem이라고 부름
  • Fractional Knapsack Problem의 반대로 물건을 쪼개서 넣을 수 없는 배낭 문제도 존재함 (0/1 Knapsack Problem으로 부름)

data_list = [(10, 10), (15, 12), (20, 10), (25, 8), (30, 5)]

def get_max_value(data_list, capacity):
    # 만약 (30, 5)면, x[1] = 5 / x[0] = 30으로 두 수를 나눈 값을 key값으로 나열 후 내림차순으로 정렬
    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]])

 

3. 탐욕 알고리즘의 한계

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

'시작'노드에서 시작해서 가장 작은 값을 찾아 leaf node까지 가는 경로를 찾을 시에

• Greedy 알고리즘 적용시 시작 -> 7 -> 12를 선택하게 되므로 7 + 12 = 19
• 하지만 실제 가장 작은 값은 시작 -> 10 -> 5이며, 10 + 5 = 15가 답
  • 지금 선택할 수 있는 것 중 최적을 선택하기 때문에 뒤는 생각하지 않기 때문