[알고리즘 기초] 그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘이란 ?

당장 눈앞의 최적의 조건을 따르는 알고리즘 ! ex) 거스름돈 문제

 

주로 무조건 큰, 긴 , 작은 , 짧은 등등 극단적으로 접근한다는 점에서 '정렬'과 같이 쓰이는 경우가 많다 

 

최적의 해를 보장하는 경우도 많지만 그렇지 못하는 경우가 더 많아서 DP(다이나믹 프로그래밍 ) 등을 사용할 수도 있다

 

ex) 거스름돈 문제 

500,100,50,10 원의 동전으로 거스름돈을 반환해야 할 때 가장 적은양의 거스름돈을 반환하도록 해보자 !!

500원이 가장많아야하고 100->50->10 순서로 거슬러주면 된다 

 

 

파이썬 코드

value = int(input()) #거스름돈
result = 0 #동전의 개수 

result += value//500 #500으로 나눈것의 몫을 더해준다 
value %= 500 #500 으로 나눠준것의 나머지 

result += value // 100
value %= 100

result += value // 50
value %= 50

result += value // 10
value %= 10

print(result)

가장 큰 500부터 접근을 하게된다