그리디 알고리즘, 현재 상황에서 당장 좋은 것만 고르는 방법.
거스름돈 문제
거슬러 줘야 할 돈 N원,
500, 100, 50, 10원 종류중에서 거슬러 줄 때 동전의 최소 갯수
N = 1260
count = 0
coin_types = [500,100,50,10]
for coin in coin_types:
count += N // coin # 동전 개수는 돈에서 동전 종류 나눈 것 추가
N %= coin # 돈은 동전 종류로 나눈 나머지가됨
print(count)- 당장 당장 그리디하게 답을 찾을 때가 정확한 답을 찾을 수 있다는 보장이 있을 때 사용
반례(그리디가 터지는 케이스)
800원을 거슬러 줘야 하고,
500,400,100원 종류라면
위 그리디 알고리즘을 사용할 경우
500, 100 , 100, 100 => 4가 되는데
400, 400 => 2 라는 더 최적의 해가 존재함.
위는 500,100,50,10인, 큰 단위가 작은 단위의 배수의 형태이기에 가능했던 그리디 알고리즘이었음.
코테에서 바로 문제 유형을 파악하기 어려울 때, 먼저 그리디 알고리즘을 의심해보기.
그리고 그리디로 안될 것 같다고 판단된다면 DP or 그래프 알고리즘 등등 찾아나가보기
그리디 문제 - 큰 수의 법칙
문제
철수의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다.
단, 배열의 특정 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.
예를 들어 순서대로 2,4,5,4,6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자.
이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는
6+6+6+5+6+6+6+5 인 46이 된다.
단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.
예를 들어 순서대로 3,4,3,4,3으로 이루어진 배열이 있을 때 M이 7이고, K가 2라고 가정하자.
이 경우 두 번째 원소에 해당하는 4와 네 번째 원소에 해당하는 4를 번갈아 두 번씩 더하는 것이 가능하다.
결과적으로 4+4+4+4+4+4+4 인 28이 도출된다.
배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 철수의 큰 수의 법칙에 따른 결과를 출력하시오.
입력 조건
- 첫째 줄에 N(2 ≤ N ≤ 1,000), M(1≤M≤10,000), K(1≤K≤10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
- 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.
- 입력으로 주어지는 K는 항상 M보다 작거나 같다.
출력 조건
- 첫째 줄에 철수의 큰 수의 법칙에 따라 더해진 답을 출력한다.
해답 및 풀이
1) 반복문(시뮬레이션) 풀이
- 정렬해서 가장 큰 수(first), 두 번째 큰 수(second)를 잡아둔다.
- 연속 제한 때문에:
- first를 K번 answer에 더하고
- 그 다음 한번 second를 더하는 것을 반복한다.
- M번 다 더하면 끝.
import sys
input = sys.stdin.readline
import time
N, M, K = map(int,input().split())
arr = list(map(int,input().split()))
start_time = time.time()
arr.sort()
first = arr[-1] # 6
second = arr[-2]
answer = 0
while True:
for _ in range(K):
if M == 0:
break
answer += first
M -= 1
if M == 0:
break
answer += second
M -= 1
end_time = time.time()
print(answer)
print("time : ", end_time-start_time)연속해서 K번 answer에 더하고, 그다음 한번 두번째로 큰 수 더하는 것을 반복하는 반복문 구현이 생각보다 까다로웠다.
time 라이브러리는 시간복잡도를 계산해보기 위해 넣은 코드인데
백준이나 프로그래머스 문제가 아니기에 vsc에서 바로 시간복잡도를 확인하고자 넣었다.
예시 입력(5, 8, 3 / 2 4 5 4 6)을 넣었을 때는
0.024ms 정도라고 나온다.
그러나 착각하면 안된다.
5, 8, 3 을 넣었기에 저렇게 짧게 나온거지,
10,000을 넣으면 더 클 것이다.
정렬에 while, for 반복문은 O(N log N + M) 이게 나올것인데
만약 M이 100억이라면 시간초과가 날 것이다.
2) 수학식(패턴) 풀이: 반복을 줄이기
문제를 다시 봤을 때,
가장 큰 수가 K번 그리고 두번째 큰 수가 1번 반복되어
K+1번씩 반복된다.
만약 나누어 떨어지지 않은 경우에는
M을 (K+1)번 나눈 나머지만큼 가장 큰 수를 더해주면 된다.
first(가장 큰 수)가 더해지는 횟수(count)를 식으로 나타내면 다음과 같다.
count = (M //(K+1)) * K + (M % (K+1))
import sys
input = sys.stdin.readline
import time
N, M, K = map(int,input().split())
arr = list(map(int,input().split()))
start_time = time.time()
arr.sort()
first = arr[-1]
second = arr[-2]
count = (M //(K+1)) * K + (M % (K+1))
answer = 0
answer += (count) * first + (M-count) * second
end_time = time.time()
print(answer)
print("time: ", end_time - start_time)정리하면, 반복문으로 M번 더하지 않고
“몇 번 더해지는지”를 먼저 계산해서 곱으로 처리하는 방식이다.
이렇게 풀 경우 시간도 반정도로 줄은 것을 볼 수 있다.
조금 더 보기 좋게 바꾼 코드
import sys
import time
input = sys.stdin.readline
N, M, K = map(int, input().split())
nums = list(map(int, input().split()))
start = time.time()
nums.sort()
max1 = nums[-1] # 가장 큰 수
max2 = nums[-2] # 두 번째로 큰 수
# (max1을 K번 + max2를 1번) = 한 묶음의 길이
block_len = K + 1
# 묶음이 몇 번 반복되는지, 남는 횟수는 얼마인지
full_blocks = M // block_len
remainder = M % block_len
# max1이 더해지는 총 횟수 = (묶음당 K번 * 묶음 수) + (남는 횟수만큼)
max1_count = full_blocks * K + remainder
max2_count = M - max1_count
answer = max1 * max1_count + max2 * max2_count
end = time.time()
print(answer)
print("time:", end - start)