이취코테 - 그리디 알고리즘

- 그리디 알고리즘(탐욕법)

: 매번 처해진 상황에서 최선을 선택하는 방법
-> 정당성 분석 : 매 단계마다 최적의 해 선택을 반복할 때, 최종 문제에 대한 최적의 해가 되는지 검토 필요

일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장하지 않는 경우가 많으나,
코테에서 대부분의 그리디 문제는 그리디 알고리즘으로 얻은 해가 최적의 해가 되는지를 추론할 수 있으면 풀리도록 출제


예시 문제.

거슬러 줄 돈을 입력받아 500원, 100원, 50원, 10원 동전이 무한히 많다는 가정하에 동전의 개수가 최소가 되도록 하여 돈을 거슬러 줄 때, 거슬러 준 각 동전의 개수와 총 동전의 개수를 출력 

 

아이디어 : 

큰 화폐 단위부터 거슬러주면 됨 
-> 정당성 분석 : 큰 단위가 작은 단위의 배수이기 때문에 그리디가 최적의 해를 보장

if) 저기에 추가로 400원 동전이 있었을 때, 800원을 거슬러줘야 한다면 500*1+100*3 이 아니라 400*2가 되었을 것

 

 

- 나의 풀이 : 

change = int(input()) # 거스름 줄 돈
money_type = [500, 100, 50, 10]
money_num = []
i = 0 
for money in money_type : 
  money_num.append(change // money)
  print(f"{money}원 개수 : {money_num[i]}")
  change -= money*(change // money)
  i += 1

total = sum(money_num)
print(f"총 화폐의 개수 : {total}")

 

+ 돈의 종류가 1000원, 5000원, 10000원, 50000원 등 추가가 되면 money_type에 돈을 추가하기만 하면 동일하게 동작한다.