[코테] 그리디 공부하기

Day2

그리디(greedy) = 탐욕적 = 현재에만 집중! 나중은 생각하지 않아!

그리디 알고리즘은 문제 출제의 범위가 넓어서 암기가 거의 불가능하므로 많은 유형의 문제들을 접해봐야 함.

문제 속에 숨어 있는 기준을 찾아서 접근해야 하고, 정렬 알고리즘과 함께 엮여서 자주 출제됨.

 

예제1) 거스름 돈

Q. 손님에게 거스름돈 N원을 가장 적은 수의 동전으로 주려면 어떻게 해야할까? 

A. 손님에게 가장 큰 화폐 단위부터 돈을 거슬러 주자.

 

N = 1260일 때 500원, 100원, 50원, 10원짜리 동전 최소한의 개수로 거슬러 주기.

n = 1260
count = 0

# 큰 액수의 돈부터 차례로 확인
coin_type = [500, 100, 50, 10]

for coin in coin_type:
  count += n // coin # 거슬러 줄 수 있는 동전의 개수를 count로 세기 (몫이 더해짐)
  n = n % coin # (나머지로 바꿈)

print(count)