그리디 알고리즘 (Greedy Algorithm)
- 그리디란 '탐욕'이라는 의미
즉, 현재 상황에서 지금 당장 좋은 것만 고르는 방법
[예제1] 거스름돈
✔문제
당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원,100원,50원,10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야할 동전의 최소 개수를 구하라. 단 N은 항상 10의 배수이다.
접근 방향 👉 가장 큰 화폐 단위부터 거슬러 주는 것
[작성 코드]
N = int(input())
one = N // 500
two =(N % 500)//100
three = (N % 500)%100//50
four = (((N % 500)%100)%50)//10
print(one+two+three+four)입력 : 1260
출력 : 6
- N을 입력 받고, 단계별로 몫과 나머지 개념을 이용하여 코딩
[답안 예시]
n = 1260
count = 0
coin_types = [500,100,50,10]
for coin in coin_types:
count += n // coin
n %= coin
print(count)- n의 값을 지정하고, 화폐를 큰 단위부터 순서대로 배열 지정
- count에 개수를 저장하고, n에는 남은 동전을 저장
- 화폐의 종류만이 시간 복잡도에 영향을 미친다. 시간 복잡도는 O(화폐의 종류 개수), 금액의 크기와는 무관
📌 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법의 정당성을 검토해야 한다. 이 문제에서 그리디로 해결할 수 있는 이유는, 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위를 종합해 다른 해가 나올 수 없기 때문이다.
ex. 800원을 거슬러줘야하는데 동전이 500,400,10이원이면 문제가 생긴다.
(500 + 100 + 100 + 100) << (400 + 400)
@이것이 코딩 테스트다 with 파이썬
Programmer & Media