[알고리즘] 탐욕(그리디) 알고리즘

1. 탐욕 알고리즘

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

→ 매순간 최적이라고 생각되는 경우를 선택

 

2. 예시

1) 동전
- 지불해야 하는 값이 4720원일 때 1원, 50원, 100원, 500원 동전으로 동전의 수가 가장 적게 지불해야 한다.
- 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능하다

coin_list = [500, 100, 50, 1]

def min_coin_count(value, list):
    total_coin_count = 0
    temp = list()
    coin_list.sort(reverse=True) # 내림차순
    
    # 핵심 : 가장 큰 값이 500원의 개수가 많을수록 전체 동전 개수가 적게 된다
    for coin in coin_list:
    	coin_num = value // coint
        total_coin_count += coin_num
        value -= coin_num * coin
        temp.append([coin, coint_num])
        
	return total_coin_count, temp
    
## 출력
min_coin_count(4720, coin_list)

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

2) 부분 배낭(Fractional Knapsack) ↔ 0/1 Knapsack Problem
- 무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣음
- 물건을 쪼개 일부분을 배낭에 넣을 수 있음

물건(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를 내림차순 정렬
    # 이렇게 정렬하면 맨 앞의 물건이 가장 최적이라고 생각
    data_list = sorted(data_list, key=lambda x: x[1]/x[0], reverse=True)
    total_value = 0
    temp = list()
    
    for data in data_list:
    	if capacity - data[0] >= 0:
            capacity -= data[0]
            total_value += data[1]
            temp.append([data[0], data[1], 1]) # 마지막 1 : 물건을 전체 다 넣음(쪼개지X)
         else: # 전체 용량보다 무게가 더 크면 쪼개서 넣어야 함
            fraction = capacity / data[0] # 얼마큼 넣었는지
            # capacity -= data[0] * fraction 어차피 0
            total_value += data[1] * fraction # 쪼개서 넣으니깐 전체 가치에도 일부분만 추가됨
            temp.append([data[0], data[1], fraction])
            break # 전체 용량 넘은 거니깐 여기서 끝
            
     return total_value, temp
            

## 출력
get_max_value(data_list, 30)

▷ 출력 결과
(24.5, [[10,10,1], [15,12,1], [20,10,0.25]])

 

3. 한계

▷ 탐욕 알고리즘은 근사치 추정에 활용이 되지만, 항상 최적의 해를 보장할 수는 없다.
(매 순간 최적인 것을 선택하기 때문)

 

+ 백준 문제 https://leunco.tistory.com/51

[백준] 11399번 : ATM

 

출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online
강의에서 들은 거지만, 강사분께서 따로 사이트에 정리를 해놓으셔서 링크 같이 첨부