doi

doing something

4 minute read


  • 그리디 알고리즘: 매 순간 가장 좋은 선택지를 고르는 방법. 현재의 선택이 나중에 미칠 영향은 고려하지 않는다.

  • 그리디 알고리즘의 문제 유형은 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높다. 이는 곧 단순 암기로 모든 문제에 대처하기 어렵다는 것을 의미하기도 하며, 다시 말해 문제 해결을 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 가지고 있는지 판단하는 유형이다. 또 문제를 만났을 때, 이것이 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지 판단할 수 있어야 한다.
  • 반면 정렬, 최단 경로 등의 알고리즘 유형은 사용 방법을 정확히 알고 있어야 문제를 풀 수 있는 확률이 높다.

  • 다익스트라 알고리즘은 그리디 알고리즘이면서 최단 경로 알고리즘이기 때문에, 그리디 알고리즘이지만 암기가 필요한 특이 케이스이다.

  • 그리디 알고리즘은 ‘기준‘에 따라 좋은 것을 선택하는 알고리즘이므로, 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로‘와 같은 기준을 알게 모르게 제시해 준다. 이 기준은 대부분 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로, 그리디 알고리즘과 정렬 알고리즘은 자주 짝을 이뤄 출제된다.


거스름돈 문제

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원의 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 주어야 할 돈이 N원일 때, 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 주어야 할 돈 N은 항상 10의 배수이다.
  • 이 문제에서 중요한 아이디어는, ‘가장 큰 화폐 단위부터’ 돈을 거슬러 주는 것이다. 가장 먼저 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)
  • 화폐의 종류만큼 반복해야 하므로, 화폐의 종류가 K라고 할 때 위 소스코드의 시간 복잡도는 O(K)이다.


그리디 알고리즘의 정당성

  • 그리디 알고리즘은 매 순간 가장 좋은 선택을 내리고 해당 선택이 다음 결과에 미치는 영향은 고려하지 않는다. 따라서 그리디 알고리즘을 이용한 해가 ‘최적의 해’라는 보장은 없다. 그러나 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있다면, 그리디 알고리즘은 효과적이고 직관적이다.
  • 그리디 알고리즘을 이용할 때는 그 해법이 정당한지 검토해야 한다. 만약 위의 거스름돈 문제에서 동전이 [500원, 100원, 50원, 10원]이 아닌 [500원, 400원, 100원]이라면, n = 800에 대해 그리디 알고리즘으로 도출해 낸 해(4개, 500원 + 100원 + 100원 + 100원)는 최적의 해(2개, 400원 + 400원)와 다르다. 위의 문제에서는 큰 단위가 작은 단위의 배수 형태였기 때문에 ‘큰 단위부터 차례대로 거슬러 준다는 아이디어’가 성립될 수 있었다.
  • 오랜 시간 고민해도 그리디 알고리즘으로는 해결할 수 없다면, 다이나믹 프로그래밍이나 그래프 알고리즘이 문제 해결에 도움이 될 수 있다.
  • 문제를 처음 만났을 때는 이것저것 다양한 아이디어를 고려해야 한다. 위의 문제에서 동전의 단위가 서로 배수 형태가 아닌 무작위 형태였다면, 그리디 알고리즘으로는 해결할 수 없다.


예제 1: 큰 수의 법칙

문제 개요

 '큰 수의 법칙'은 일반적으로 통계 분야에서 다루어지는 내용이지만 동빈이는 본인만의 방식으로 다르게 사용하고 있다. 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 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보다 작거나 같다.

입력 예시

5 8 3
2 4 5 4 6

문제 해설

입력값 중 가장 큰 수와 두 번째로 큰 수만 저장한다. ‘가장 큰 수를 K번 더하고, 두 번째로 큰 수를 한 번 더하는 연산‘을 반복한다.

n, m, k = map(int, input().split())
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:
			break
		result += first
		m -= 1 # 더할 때마다 - 1
	if m == 0:
		break
	result += second # 두 번째로 큰 수 한 번 더하기
	m -= 1 # 더할 때마다 - 1

print(result)

그러나 위의 코드는, M의 크기가 100억 이상과 같이 커진다면 시간 초과 판정을 받게 된다. 수학적 아이디어를 통해 더 효율적으로 문제를 해결할 수 있다.

이 문제는 가장 큰 수와 두 번째로 큰 수가 더해질 때 특정 수열 형태로 일정하게 반복되며 더해진다는 특징이 있다. 이때 반복되는 수열의 길이는 (K + 1)이다. 따라서, M을 (K + 1)로 나눈 몫이 수열이 반복되는 횟수이다. 여기에 다시 K를 곱해 주면 가장 큰 수가 등장하는 횟수가 된다. M이 (K + 1)로 나누어 떨어지지 않는 경우, 나눈 나머지만큼 가장 큰 수가 추가로 더해지므로 이를 고려해 주어야 한다. 즉, ‘가장 큰 수가 더해지는 횟수’를 식으로 작성하면 int(M / (K + 1)) * K + M % (K + 1)과 같다.

아래는 위 내용을 반영해 개선한 코드이다.

n, m, k = map(int, input().split())
data = list(map(int, input().split()))

data.sort() # 오름차순 정렬
first = data[n - 1] # 가장 큰 수
second = data[n - 2] # 두 번째로 큰 수

result = 0

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

result = 0
result += (count) * first
result += (m - count) * second

print(result)

You may also enjoy