그리디 알고리즘이란?
- 현재 상황에서 지금 당장 좋은 것만 고르는 알고리즘 설계 기법
- 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음.
- 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형
- 주로 정렬과 짝을 이뤄 출제
- '가장 큰 순서대로', '가장 작은 순서대로'등의 기준을 알게 모르게 제시한다.
- 부분의 최적해들의 집합이 곧 전체문제의 해답일 경우 사용
대표적인 예시
- 거스름돈, 최소 신장 트리, 다익스트라, 허프만, 크리스컬....
거스름돈 문제
말 그대로, 돈을 거슬러 주는 문제인데, 가지고 있는 잔돈의 종류를 탐욕적으로 이용하여 가장 적은 잔돈의 종류를 내 주어야 한다.
거스름돈으로 사용할 동전의 종류
- 500원, 100원, 50원, 10원 (동전의 양은 무한하다고 가정)
1) 2340원을 받았다고 가정했을 때
- 500원 4개 -> 현재 동전 : 4 / 남은 돈 : 340
- 100원 3개 -> 현재 동전 : 7 / 남은 돈 : 40
- 10원 4개 -> 현재 동전 : 11 / 남은 돈 : 0
이므로 최적의 동전 개수는 11개이다.
2) 1260원을 받았다고 가정했을 때
- 500원 2개 -> 현재 동전 : 2 / 남은 돈 : 260
- 100원 2개 -> 현재 동전 : 4 / 남은 돈 : 60
- 50원 1개 -> 현재 동전 : 5 / 남은 돈 : 10
- 10원 1개 -> 현재 동전 : 6 / 남은 돈 : 0
이므로 최적의 동전 개수는 6개이다.
cost = int(input()
coins = [500, 100, 50, 10]
count = 0
for coin in coins:
count += n
n %= coin
print(count)
거스름 돈 알고리즘 코드
예시문제 1. 큰 수의 법칙 (2019 국가 교육기관 코딩 테스트 문제)
해당 문제에서 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.
예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 4라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5인 46이 된다.
(서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.)
배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 결과를 출력하시오.
<입력 예시>
5 8 3
2 4 5 4 6
<출력 예시>
46
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
data.sort(reverse = True)
target = 0
result = 0
count = 0
while count < m:
if target == 0:
for j in range(k):
result += data[target]
count += 1
target = 1
else:
result += data[target]
target = 0
count += 1
print(result)
이는 M의 숫자가 커지면 시간 초과가 될 수도 있는 코드이다.
주어진 배열의 1, 2 번째로 큰 수만을 사용하여 일정한 규칙을 나타내기 때문에
이를 일반항으로 도출하여 풀어낼수도 있지만, 시작의 장이기에 넘어가도록 하겠다.
다익스트라 알고리즘 (추가 예정)
