그리디(Greedy)=탐욕법 알고리즘 [이코테-나동빈]

그리디(Greedy) = 탐욕법 알고리즘  

: 현재 상황에서 지금 당장 좋은 것만 고르는 방법

*매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향은 고려하지 않음

 

알고리즘 테스트에서는 창의력, 문제를 풀기위한 아이디어를 떠올리면 그리디 알고리즘은 해결할 수 있다!

 

문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시할 수 있으니 정렬알고리즘과 같이 사용하는 경우가 많다.

거스름돈 문제

카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원이 무한히 존재할 때 거스름돈으로 N원을 줘야하는데

이때 거슬러 줘야할 동전의 최소 개수를 구하는 경우

단 N은 항상 10의 배수이다.

#그리디 알고리즘
#거스름돈 대표적 문제
n = int(input())
count = 0

#큰 단위 화폐부터 차례로 확인
coin_types =[500, 100, 50, 10]

for coin in coin_types:
    #해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
  temp = n // coin     # 거스름돈과 coin을 나누어서 몫을 계산함
  count = count + temp # 몫과 count 더 해줌
 
  n = n%coin           # 위에서 몫 만큼 coin을 거슬러주었으니 나머지 거스름돈을 계산하고 변수에 할당 
  
print(count)

n은 input으로 값을 받아서 여러 값에도 적용할 수 있도록 하였다.

예를 들어 n=1380 이었다면

count는 9가 나올 것이다.

9가 나오는 경우는 [500, 500, 100, 100, 100, 50, 10, 10, 10] 이렇게 될 수 있다.

 

위의 예는 가장 큰 단위부터 돈을 거슬러주는 방법으로 접근을 했을때 해결 가능성이 높다!

 

하지만 그리디 알고리즘은 모든 알고리즘 문제에 적용할 수 있는 것은 아니다.

다른 알고리즘은 최적의 해를 찾을 수 없을 수 있기 때문에 주의해야 한다!