[이코테] CHAPTER 03 그리디(Greedy)

그리디(Greedy) 알고리즘

탐욕적으로 문제를 푸는 알고리즘( 현재 상황에서 지금 당장 좋은 것만 고르는 방법)

기준에 따라 좋을 것을 선택하는 알고리즘이므로 문제에서 "가장 큰 순서대로","가장 작은 순서대로"와 같은 기준을 제시

-> 이 기준들은 정렬 알고리즘을 사용하였을 경우 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝 지어 출제

 

대표적인 예제 : 거스름돈

가정 ) 거스름돈으로 사용할 돈은 500,100,50,10원짜리 동전이 무한히 존재

손님에게 거슬러 줘야할 돈 N원일 때 거슬러 줘야 할 동전의 최소 개수 구하기

( 단, 거슬러 줘야할 돈 N원은 항상 10의 배수 )

 

문제 해설 ) 가장 큰 화폐 단위부터 돈을 거슬러 준다. -> 이때, 정렬 알고리즘을 활용하여 사용한다.

if N=1260일 경우, 

    1. 500원으로 2개를 먼저 나누어 줘서 1260원 중 1000원을 먼저 거슬러준다.

    2. 100원으로 2개를 먼저 나누어 줘서 남은 금액 260원 중 100원을 먼저 거슬러준다.

    3. 50원으로 1개를 먼저 나누어 줘서 남은 금액 60원 중 50원을 먼저 거슬러준다.

    4. 10원으로 1개를 먼저 나누어 줘서 남은 금액 10원 10원을 거슬러준다.

    5. 즉, 500원 2개, 100원 2개, 50원 1개, 10원 1개로 동전의 최소 개수는 6개이다.

 

n=1260
count=0

coin_type=[500,100,50,10]

for coin in coin_type:
    # // : 몫, % : 나머지
    count+= n //coin #coin=500일경우, n//coin=2로 count에 2 플러스
    n%=coin #coin=500일 경우, n%coin=260으로 n은 260 대입

print(count)

백준 그리디 

 

1. 11399 - Python(파이썬) ,Java(자바)

백준- 11399( ATM )- Python(파이썬)

백준 11399- Java