TIL #21 : 탐욕 알고리즘

tobi·2021년 8월 19일

algorithm

알고리즘

목록 보기

5/8

📝 탐욕 알고리즘

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

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

📝 탐욕 알고리즘 문제 예시

1. 동전 문제

Q. 지불해야 하는 값이 5650원일 때, 1원, 50원, 100원, 500원 동전으로 동전의 수가 가장 적게 지불하는 경우는?

💡 가장 큰 동전부터 값을 최대한으로 채우는 방식으로 구현 가능 !

def solution(price, coin_list):
    total_coin_cnt = 0
    
    for coin in sorted(coin_list,reverse=True):
        cnt =  price//coin
        total_coin_cnt+=cnt
        price -= coin*cnt
        print('%d원짜리 : %d개' %(coin, cnt))
    
    return total_coin_cnt

coin_list = [500, 100, 50, 1]
print(min_coin_cnt(5650,coin_list))

👇 [실행 결과]
 500원짜리 : 11개
 100원짜리 : 1개
 50원짜리 : 1개
 1원짜리 : 0개
 13

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

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

각 물건은 무게와 가치로 표현
물건을 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어지는 것이 가능
💡 무게당 가치가 큰 순서로 정렬 후, 가치가 큰 물건부터 배낭에 채우는 방식으로 구현 가능 !

def solution(item_info, capacity):
    total_value=0

    for item in sorted(item_info, key= lambda x: x[1]/x[0], reverse=True):
        if capacity >= item[0]:
            total_value+=item[1]
            capacity-=item[0]
        else:
            total_value+= (item[1]/item[0])*capacity
            break
    
    return total_value

item_info = [(10,10),(15,12),(20,10),(25,8),(30,5)]
print(solution(item_info, 30))

👇 [실행 결과]
 24.5