파이썬 자료구조 :: 그리디 알고리즘 (Greedy)

 

그리디(Greedy) 알고리즘

탐욕법이라고 하며, 현재 상황에서 지금 당장 좋은 것만 고르는 알고리즘

뒷 날, 미래, 큰그림은 생각안하고

현재 지금 now 눈앞의 것 중에서 젤 좋아보이는 걸 고르는 것이다.

(설명 및 문제는 '이것이 코딩테스트다' 책 참고함)

루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶습니다.

 

Q. 최적의 해는 무엇인가요?

애초에 노드의 수가 별로 없어서 눈으로 봐도 최적의 해를 알 수 있습니다.

5 > 7 > 9 이 순서로 이동하게 되면 노드 값의 합이 21로 가장 큰 경우의 수가 되는 것을 알 수 있습니다.

 

 

Q. 단순히 매 상황에서 가장 큰 값만 고른다면 어떻게 될까요?

해당 경우에는 총 합 19 임을 알 수 있으며, 최적의 합인 21보다 낮은 값입니다.

즉, 그리디 알고리즘은 이처럼 단순히 매상황에서 가장 큰 값만 고르는 방식임을 알 수 있습니다.

 

일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많습니다.

하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕 법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됩니다.

 

[문제] 큰 수의 법칙 

큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 m번 더하여 가장 큰 수를 만드는 법칙이다. 이 때, 배열의 특정한 인덱스에 해당하는 수가 연속해서 k번을 초과하여 더해질 수는 없다.

예를 들어, m이 8, k가 3이고, 배열 arr가 [2, 4, 5, 4, 6]이라고 할 때, 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5로, 46이 된다.

이 때, 다른 인덱스에 있는 값이 같은 경우에도 이는 서로 다른 것으로 간주한다. 따라서 arr가 [3, 4, 3, 4, 3]일 때, 두번째 4와 네번째 4는 서로 다른 것이므로 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4가 가능하다.

import sys
input = sys.stdin.readline

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

arr.sort()
first = arr[n-1]
second = arr[n-2]

count = int(m / (k+1)) * k
count += m % (k + 1)

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

print(ans)

[문제] 숫자 카드 게임

N * M 형태로 카드가 놓여 있을 때, 각 행의 가장 작은 수들을 선택한다. 이 때, 선택한 수들 중 가장 큰 수를 출력한다

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
result = 0

for i in range(n):
	card = list(map(int, input().split()))
	min_value = min(card)
	result = max(min_value, result)

print(result)

[문제] 1이 될 때까지

n이 1이 될 때까지 아래의 과정 중 하나를 반복적으로 선택하여 수행한다.

1. n에서 1을 뺀다.

2. n을 k로 나눈다.

이 때, 2번 연산은 n이 k로 나누어떨어질 경우에만 실행가능하다.

n, k = map(int, input().split())
cnt = 0

while True:
	# n이 k로 나누어떨어질 때까지 1 빼기
	target = (n // k) * k
	cnt += n - target
	n = target

	# 더 이상 n을 k로 나눌 수 없으면 반복문 탈출
	if n < k:
		break

	# n을 k로 나누기
	cnt += 1
	n //= k

# 남은 수에 1씩 빼기
cnt += n - 1

print(cnt)

[문제] 볼링공 고르기

볼링공이 총 n개가 있고, 공의 무게는 1부터 m까지의 자연수 형태로 존재한다. 

이 때, 같은 무게의 볼링공이 있을 수 있지만, 이들은 서로 다른 공으로 간주한다. 

두 사람이 무게가 서로 다른 볼링공을 고르고자 할 때, 가능한 경우의 수를 요구한다.

import sys
input = sys.stdin.readline

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

result = [0] * (m+1)
cnt = 0

for weight in balls:
	result[weight] += 1 

for i in range(1, m+1):
	n -= result[i]
	cnt += n * result[i]

print(cnt)