TIL #12 - 3.13

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

• 최적의 해에 가까운 값을 찾기위한 방식
• 여러 경우의수가 주어질 때마다 최선의 방식이라고 생각되는 것을 선택해서 값을 구하는 과정

동전문제

5120원이 주어졌을 때 500, 100, 50, 1 으로 지불할 수 있는 최소한의 동전 수를 구하시오

coin_list = [500,100, 50,1]
total_coin_count = 0 
details = []
def coin_function(value, coin_list):
	for coin in coin_list:
	coin_num = value // 500
    total_coin_count += coin_num
    value -= coin_num * coin
    details.append([coin, coin_num])
   return total_coin_count, detail
    

탐욕 알고리즘의 한계

• 최적의 해에 가까운 값을 찾아내지만 최적의해가 아닐 수 있음.
• 근사 추정에 활용하는 구조