이것이 취업을 위한 코딩 테스트다 with 파이썬
📍그리디(Greedy 란?)
✅현재 상황에서 당장 좋은 것만 고르는 방법
기준에 따라 좋은 것을 선택하는 알고리즘이므로, 문제에서
- 가장 큰 순서대로
- 가장 작은 순서대로
같은 기준을 제시해준다
이러한 기준은 정렬 알고리즘으로 만족시킬 수 있으므로, 그리디는 주로 정렬 알고리즘과 짝을 이뤄 출제된다
📍예제1 : 거스름돈
✅N원을 거슬러주기 위해 500원, 100원, 50원, 10원 동전으로 거스름돈을 만들어준다고 가정할 때, 사용할 동전의 최소 갯수를 구하라
✅가장 큰 화폐 단위(500원)부터 사용하여 거스름 돈을 만든다
- 동전을 가장 적게 사용하려면, 500원짜리 동전을 최대한 사용하면 된다
✅코드
n = int(input())
count = 0
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += n // coin # 몫 = 사용 가능한 동전 갯수
n %= coin
print(count)
📍생각해볼 문제
✅만약, 동전 단위가 500, 400, 100 일 때도 똑같은 코드로 답을 구할 수 있을까?
- 거스름돈이 800원 이라면, 500, 100, 100, 100 => 800원
- 하지만 최적해는 400, 400 이다..
- 즉, 동전들이 서로 배수의 관계가 아니므로 추가적인 검토 필요
✅문제에 따라서 그리디 알고리즘이 정당한지 검토할 수 있어야함
- 동전 단위가 서로 배수 관계가 아니라 무작위하다면, DP를 이용해야 함
📍예제2 : 큰 수의 법칙
✅N개의 자연수로 이루어진 수열에서 숫자를 M번 꺼내서 더하는데 숫자는 최대 K번 까지 사용할 수 있다고 할때 최댓값을 구하라
2 <= N <= 1000
1<= M, K <= 10000
✅naive solution
n, m, k = map(int, input().split())
data = sorted(list(map(int, input().split())), reverse=True)
total = 0
count = k
for i in range(m):
if count > 0:
count -= 1
total += data[0]
else:
count = k
total += data[1]
print(total)
"""
입력
5 8 3
2 4 5 4 6
출력
46
입력
5 7 2
3 4 3 4 3
출력
28
"""
✅refactored solution
반복되는 패턴을 파악하면, 효율적으로 해결할 수 있다
입력이 아래와 같을 때
5 8 3
2 4 5 4 6
6 6 6 5 를 하나의 패턴으로 볼 수 있다
n, m, k = map(int, input().split())
data = sorted(list(map(int, input().split())), reverse=True)
bundle = data[0] * k + data[1] # 패턴
bundle_num = m // (k + 1) # 패턴이 몇 번 등장하는지
rest = m % (k + 1) # 나머지
print(bundle * bundle_num + rest * data[0])
print(rest)
"""
입력
5 8 3
2 4 5 4 6
출력
46
입력
5 7 2
3 4 3 4 3
출력
28
"""