Advanced Algorithm - 탐욕(Greedy) 알고리즘

1. 탐욕 알고리즘 이란?

- 최적의 해에 가까운 값을 구하기 위해 사용되는 알고리즘이다.

- 여러가지 경우 중 하나를 결정해야할 때, 상황에 따라 매순간 최선의/최적의 경우를 선택하여 최종적인 값을 구하는 방식이다.

- 다시 말해, 문제를 풀기위해 최선의 경우를 선택하는 방식

---

2. 탐욕 알고리즘의 예

 

a) 동전 문제

- 지불해야 하는 값이 4720원 일 때, 1원 40원 100원 500원짜리 동전을 사용하여 가장 적은 동전 수를 이루는 조합을 찾아라.

• 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능

• 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 된다.    

coin_list = [1,50,100,500]

def min_coin_count(value, coin_list):
    total_coin_count = 0 #총 동전의 개수
    details = list() # 어떤 동전이 몇개 사용됐는지 정보를 담는 리스트
    
    coin_list.sort(reverse=True) 
    # 가장 큰 동전부터 지불해야 하는 값을 채우는 방식을 구현하기 위해
    # Sort 메소드를 사용하여 내림차순으로 정렬 
    
    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

 

 

[테스트]

- 결과: 총 31개의 동전을 사용, 500원(9개) 100원(2개) 5원(0개) 1원(20개) 

 

 

 

b) 부분배낭 문제(Fractional Knapsack Problem)

- 무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제

• 각 물건은 무게(w)와 가치(v)로 표현

• 물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있음, 그래서 Fractional Knapsack Problem 으로 부름

• Fractional Knapsack Problem 의 반대로 물건을 쪼개서 넣을 수 없는 배낭 문제도 존재함 (0/1 Knapsack Problem 으로 부름)

- 가장 많은 가치를 넣을 수 있는 물건을 우선으로 배낭에 넣는 방식으로 해결한다. → 물건 1

 

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

def backpack(limit, data_list):
    # 무게대비 가치가 가장 높은 물건을 찾기위해 정렬
    # 람다식을 이용하여 정렬할 기준을 표현
    # x가 각각의 tuple을 의미 ex) (10,10)
    # x[1]은 각 tuple의 가치를, x[0]은 각 tuple의 무게를 표현
    # 가치/무게 = x[1] / x[0] = 무게의 단위당 가치 = 무게 대비 가치를 계산
    # reverse=True (내림차순으로 정렬)
    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 limit - data[0] >= 0:
            limit -= data[0]
            total_value += data[1]
            details.append([data[0], data[1], 1]) #마지막 1은 물건을 쪼갠 정도(1 = 100%)
        else: #가방의 공간이 부족하다면 물건을 쪼개어 넣어야 한다.
            fraction = limit / data[0]
            limit -= fraction * data[0]
            total_value += data[1] * fraction
            details.append([data[0], data[1], fraction])
            break # 가방에 더이상 들어갈 공간이 없기 때문에 break 수행 
    return total_value, details

 

 

 

[테스트]

---

3. 탐욕 알고리즘의 단점

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

- 반드시 최적의 해를 구할 수 있는 것은 아니기 때문에 최적의 해에 가까운 값을 구하는 방법 중의 하나이다.

 

ex) 루트노드에서 시작하여 가장 작은 값을 찾아 leaf node 까지 가는 경로를 찾는 문제

 

- Greedy 알고리즘 적용시 7 → 12 를 선택하게 되므로 7 + 12 = 19가 된다.

- 하지만 실제 가장 작은 값은 10 → 5 이며, 10 + 5 = 15가 된다.

 

* 탐욕 알고리즘은 왜 7을 선택하는가? 

→ 탐욕 알고리즘은 매순간 최선의/최적의 선택을 하기 때문이다. 첫번째 자식노드인 7과 10중에서 가장 작은 값에 대한 최선의 선택은 7이기 때문이다.