1. 그리디 알고리즘의 의미
이름에서도 알 수 있듯 탐욕법이라고도 불립니다. 어떤 문제를 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘을 의미합니다.
여기서 탐욕적이라는 말은 ‘현재 상황에서 지금 당장 좋은 것만 고르는 방법‘입니다. 그리디 알고리즘은 매순간 가장 좋아보이는 것을 선택하고, 그 선택이 미래에 미치는 영향따위는 고려하지 않습니다.
그리디 알고리즘은 기준에 따라 가장 좋은 것을 선택하는 알고리즘이므로 문제에서 제시하는 기준을 잘 확인할 필요가 있습니다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때, 만족시킬 수 있으므로 그리디 알고리즘과 정렬 알고리즘은 자주 세트로 출제됩니다.
2. 문제풀이
1) 거스름돈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 내 풀이
# 500, 100, 50, 10 무한
# 거슬러 줘야할 돈 N원
# 거슬러줘야할 동전의 최수 개수
# 잔돈이 얼마가 됐건 가장 큰 단위인 500원 부터해서 차례대로 주면, 최소가 되지않나?
# 내 풀이 과정
"""
N = 5120
count = N//500
residual = N%500
count2 = residual//100
residual2 = residual%100
print(count)
print(residual)
"""
N = 5120
count = 0
coins = [500, 100, 50, 10]
for coin in coins:
count += N//coin
N = N%coin
print(count)
1
2
3
4
5
6
7
8
9
10
11
# 답안 예시
n = 1260
count = 0
# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += n//coin
n %= coin
print(count)