[알고리즘]그리디 알고리즘_거스름돈 예제(나누기/몫을 활용한 계산)

[그리디 알고리즘과 거스름돈 예제] 

 

-그리디 알고리즘

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

 

 

-그리디 알고리즘과 거스름돈 예제 
└거스름돈을 주는 상황에서 그리디 알고리즘을 적용하면 '가장 큰 화폐 단위부터' 돈을 거슬러주는 것!
ex) 500원/100원/50원/10원이 있고 1260원을 거슬러주려면?
=> 500 500 100 100 50 10 순서로 거슬러 주면 된다.

n = 1260
count = 0

#거스름돈
coin_types = [500, 100, 50, 10]

for coin in coin_types : #coin : 500 -> 100 -> 50 -> 10
    count += n // coin #해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    # //연산자 나누기 연산 후 소수점 이하의 수를 버리고, 정수 부분의 수만 구함
    #위 코드에서 +=연산자가 가장 우선순위가 낮음
    n %= coin

print(count)

 

-for문 이해해보기

 

-나누기 몫과 나머지 이해하기 

나누기를 뺄셈으로 생각해보자~!

 

1260원에서 500원이 몇개 필요한지 알려면?

└1260원에서 500원을 몇개 뺄까요? 그 몇개는 나누기의 몫을 의미

└빼고 난 나머지는 얼마일까요? - 나머지는 나누기의 나머지를 의미

 

1260원에서 500원이 몇개 필요한지 알려면?

└1260/500 => 몫 : 2(500을 두번 뺀다~), 나머지는 : 260(500을 두번 뺀 후 남은 수)

└따라서 1260에서 500은 2개 있고, 1260원에서 500원을 2번 빼면 260원이 남는다~

 

 

-나누기 몫과 나머지 이해하기2

100/30가 있으면 100에 30이 몇 개 있는지를 구한다고 생각해보자!! 

100%30가 있으면 100에 30을 최대한으로 빼고 난 남은 수라고 생각해보자!!  

 

234에 백의자리는 몇? 십의자리는 몇? 일의자리는 몇? (= 234에 100은 몇 개, 10은 몇 개, 1은 몇 개 있는가?)

234에 100이 몇 개 있는가?(=234/100의 몫) 2개 ------------------------> 백의 자리는 2인 것을 알 수 있다.

234에서 100을 2번 빼면 남은 수는 얼마인가?(=234%100) 34

 

34에 10이 몇 개 있는가?(=34/10의 몫) 3개 ------------------------> 십의 자리는 3인 것을 알 수 있다.

34에서 10을 3번 빼면 남은 수는 얼마인가?(=34%10) 4

 

4에 1이 몇 개 있는가?(=4/1의 몫) 4개 ------------------------> 일의 자리는 4인 것을 알 수 있다.