파이썬 자료구조 :: 그리디 알고리즘 (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)
댓글
댓글 쓰기