그리디 알고리즘 Greedy

오늘은 그리디 알고리즘에 대하여 공부하였습니다.

백준 알고리즘에서 그리디 알고리즘 문제를 풀어본적 있지만, 이론부터 알아가면 더욱 좋을 것 같네요.!

그리디(Greedy)가 사전정의에 따르면, '탐욕스러운' 또는 '욕심 많은' 뜻이네요.

알고리즘에서는 지금 당장 좋은 것만 고르는 방법으로 지칭하곤 하더라고요.

 

그리디 알고리즘에서 대표 문제로 '거스름돈' 문제를 풀어보겠습니다..!

 

거스름돈으로 사용할 500원, 100원, 50원, 10원 동전이 무한히 존재.

손님에게 거슬러줘야 할 돈이 A원 일 때, 최소 동전 개수는? (A는 10의 배수)

 

 

import sys

# 입력값
A = int(sys.stdin.readline())

# 동전 종류 500 100 50 10
coin = [500, 100, 50, 10]
# 동전 개수
count = 0

for i in coin:
    count += A//i
    A %= i
print(count)

코드 해석은 동전의 종류는 500, 100, 50, 10으로 총 4개. 최소 동전 개수를 가지려면 A원에서 최대한 500원 동전을 할애하고, 그 다음으로 큰 100원, 50원, 10원 순으로 전개해야 한다.

입력값이 예를 들어 A=1780일 때, 1780원에서는 500원을 최대 3개를 가질 수 있다. 1780//500=3이다.

그 다음 500원을 다 할애하고 남은 돈 1780%500=280에서 100원을 최대 2개를 가질 수 있다. 280//100=2이다.

그 다음 100원을 다 할애하고 남은 돈 280%100=80에서 50원을 최대 1개를 가질 수 있다. 80//50=1이다.

그 다음 50원을 다 할애하고 남은 돈 80%50=30에서 10원을 최대 3개를 가질 수 있다. 30//10=3이다.

 

초기값을 count=0을 설정하고, 중간중간 += 연산자를 사용하면서 동전개수를 누적시킨다.

그리고 중요한점은 거스름돈(A)에서 동전을 최대로 가진 후, 거스르고 남은 돈을 지정해 주어야 한다.

 

여기서 동전개수 N개(4개)일 때, 시간 복잡도는 O(N)이다.