탐욕 알고리즘

탐욕 알고리즘이란?

 Greedy algorithm 또는 탐욕 알고리즘 이라고 불리운다.

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

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

 

 

예를 들어 4720원을 1원 50원 100원 500원으로 지불하되 가장 적은 동전만 낸다고 생각하자.

여러 경우중 500원을 가장 많이내는 경우가 최적이고 그 다음은 100원 ... 이렇게 진행해서 최종값을 구할 수 있게된다.

coin_list=[500,100,50,1]
price = 4720
def coin(coin_list,price):

total_coin =0
details=list()

for coin in coin_list:
  coin_count = price//coin  
  total_coin += coin_count
  price -=coin * coin_count
  details.append([coin,coin_count])
  
  return total_coin,details

탐욕 알고리즘의 한계

 

탐욕 알고리즘은 근사치 추정에 활용한다.

반드시 최적의 해를 구할 수 있는 것이 아니기 때문이다.

최적의 해를 구할 수 있는 방법중 하나이다.