본 내용은 "이것이 코딩 테스트다" 교재를 바탕으로 작성하였습니다.

그리디(Greedy)

'탐욕법'이라 소개되기도 하고, 현재 상황에서 가장 좋아 보이는것만을 선택하는 알고리즘이다. 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서 고려하지 않는다.
그리디 알고리즘 유형의 문제는 매우 다양하여 많은 유형을 접해봐야 한다.

기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 아래와 같이 기준을 알게 모르게 제시하는 경우도 있다.

• '가장 큰 순서대로'
• '가장 작은 순서대로'

1. 당장 좋은 것만 선택하는 그리디

거스름돈

카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다.
손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하여라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

📍 문제 해설

그리디 알고리즘을 이용해 풀 수 있는 대표문제이다.
동전을 최소로 건네주기위해서는 어떻게 해야 할까?
의외로 문제의 순서는 간단하다.
화폐의 가장 큰 단위부터 거슬러 주는 것이다.
500원 → 100원 → 50원 → 10원 순으로 거슬러 준다면 동전을 최소로 사용할 수 있다.

예를 들어본다.
input → 1260

Step1

1260에서 500원을 최고로 사용할 수 있는 개수는 2개이다.
1260 - 500*2 = 260

Step2

이제 남은 돈은 260원이다. 다음 가장 큰 단위인 100원을 최고로 사용해보자. 260에서 사용가능한 100원의 수는 2개이다.
260 - 100*2 = 60

Step3

위와 같이 스텝을 이어가면 다음은 50원이다.
60 - 50*1 = 10

이렇게 1260원의 거스름돈은 500원 2개 100원 2개 50원 1개 10원 1개로 최소 구성을 마친다. 따라서 손님이 받을 최소 개수는 6개이다.

exgreedy1.py

n = 1260
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count = count + n // coin
    n %= coin

print(count)

화폐의 종류만큼 반복을 수행해야한다.
따라서 화폐의 종류가 K개라고 할 때 코드의 시간복잡도는 O(K) 이다.
즉, 이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야하는 금액의 크기와는 무관하다는 것을 알 수 있다.

2. 큰 수의 법칙

이 책의 저자는 큰 수의 법칙을 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙으로 정의했다.
(단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징.)

예를 들어서 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있다.
M은 8이고, K는 3이라 가정한다.
이 경우 특정한 인덱스의 수가 연속해서 3번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5인 46이 된다.

• 가장 큰 수는 6이며 연속으로는 3번까지만 가능.
• 다음은 5. 가장 큰 수를 제한까지 최대로 사용하고 다음 큰 수를 사용

단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주하는데 예를 들어 순서대로 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)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다.
  단, 각각의 자연수는 1이상 10,000 이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다.

출력 조건

• 첫째 줄에 큰 수의 법칙에 따라 더해진 닶을 출력한다.

입력 예시

5 8 3
2 4 5 4 6

출력 예시

46

문제 해설

전형적인 그리디 알고리즘 문제이다.
이 문제를 해결하려면 우선 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장하면 된다.
연속으로 더할 수 있는 횟수는 최대 K번이므로 '가장 큰 수를 K번 더하고 두번 째로 큰 수를 한번 더하는 연산'을 반복하면 된다.

단순하게 푸는 답안 예시

# N, M, K를 공백으로 구분하여 입력하기
n, m, k = map(int, input().split())
# N개의 수를 공백으로 구분하여 입력받기
data = list(map(int, input().split))

data.sort() # 입력받은 수를 정렬한다.
first = data[n - 1] 	# 가장 큰 수
second = data[n - 2] 	# 두 번째로 큰 수

result = 0

while True:
	for i in range(k): 	# 가장 큰 수를 K번 더하기
    	if m == 0:		# m이 0이라면 반복문 탈출
        	break
        result += first
        m -= 1 			# 더할 때 마다 -1
    if m == 0:			# m이 0이라면 반복문 탈출
    	break
    result += second 	# 두 번째로 큰 수를 한 번 더하기
    m -= 1 				# 더할 때 마다 1씩 빼기

print(result)

M이 10,000 이하이므로 이 방식으로 문제를 해결할 수 있지만, M의 크기가 100억 이상처럼 커지는 경우에는 시간 초과 판정을 받게 될 것이다.
간단한 수학적 아이디어를 적용해 효율적으로 문제를 해결할 수 있다.

예를 들어 N이 5이고 입력값이 다음과 같다.

5 8 3
2 4 5 4 6

이 때 가장 큰 수와 두 번째로 큰 수를 선택하면 다음과 같다.

• 가장 큰 수: 6
• 두 번째로 큰 수: 5

이 문제를 풀기 위해서 가장 먼저 반복되는 수열 에 대해서 파악해야한다. 위의 예시에서는 [6, 6, 6, 5]가 반복된다.
반복되는 수열의 길이는 어떻게 될까?
(K+1)로 4가 된다. 따라서 M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수가 된다. 다시 여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수가 된다.
이 때 M이 (K+1)로 나누어 떨어지지 않는 경우도 고려해야 한다. 그럴 때는 M을 (K+1)로 나눈 나머지 만큼 가장 큰 수가 추가로 더해지므로 이를 고려해주어야 한다.
즉, '가장 큰 수가 더해지는 횟수'는 아래와 같다.

int(M/(K+1)) * K + M % (K + 1)

exgreedy2.py

# N, M, K를 공백으로 구분하여 입력하기
n, m, k = map(int, input().split())
# N개의 수를 공백으로 구분하여 입력받기
data = list(map(int, input().split()))

data.sort() # 입력받은 수를 정렬한다.
first = data[n - 1] 	# 가장 큰 수
second = data[n - 2] 	# 두 번째로 큰 수

# 가장 큰 수가 더해지는 회수 계산
count = int(m / (k + 1)) * k
count += m % (k+1)

result = 0
result += (count) * first # 가장 큰 수 더하기
result += (m - count) * second # 두 번째 큰 수 더하기

print(result)