[이코테] 그리디 알고리즘 3-1

greedy : 탐욕적인

 

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.

 

매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 생각하지 않는다.

 

이 책의 예제를 풀어보자.

 

3-1 거스름돈

Q. 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정할 때 손님한테 거슬러 줘야할 돈이 N원이고 N원의 동전의 최소 개수를 구하라 (N은 10의 배수)

 

A. 1260원을 거슬러 줘야한다고 생각해보자. 큰 동전 부터 500원은 2개, 100원은 2개, 50원은 1개, 10원은 1개로 총 6개의 동전이 필요로 한다. %와 //를 잘 활용해서 코딩해보자.

 

# 그리디 알고리즘 :  현재 상황에서 지금 당장 좋은 것만 고르는 방법

# 문제
# 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정할 때 손님한테 거슬러 줘야할 돈이 N원이고 N원의 동전의 최소 개수를 구하라 (N은 10의 배수)

# 나의 풀이

N = int(input())

five = N//500
N = N%500
one = N//100
N=N%100
fifty =N//50
N=N%50
ten=N//10
N=N%10

print(five+one+fifty+ten)

# 정답 풀이

N = int(input())
count =0

coin_types=[500,100,50,10]

for coin in coin_types:
    count += N // coin
    N %= coin

print(count)

 

 

그리디 알고리즘은 결국 무식하게 하나하나 해보는 방법이기 때문에 효율적인 답찾기는 아닐 수 있다. 하지만 위 문제 같은 경우 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 그리디 알고리즘을 사용할 수 있다.

 

코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는 지 고민해보자.