그리디 알고리즘

탐욕법으로 소개되는 이 알고리즘은 어떠한 문제가 있을 때 단순하게 탐욕적으로 문제를 푸는 알고리즘이다. 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 매 순간 가장 좋아 보이는 것을 선택하며 현재의 선택이 나중에 미칠 영향은 고려하지 않는다.

기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 가장 큰 순서대로, 가장 작은 순서대로와 같은 기준을 제시해준다. 이 기준은 정렬 알고리즘을 사용하면 만족시킬 수 있다.

✏️ 예제

백준 2839

5가 최대일 경우 전체 횟수가 최적의 해를 갖게 되므로 5를 기준으로 나눴다.

# 나의 풀이
N = int(input())
lst = []
r = N // 5

for i in range(r, -1, -1):
    a = N - i * 5
    b = a % 3
    if b == 0:
      print(i + a//3)
      break
    if i == 0:
      print(-1)

# gpt 풀이
N = int(input())

# 5kg 봉지를 최대한 사용
bags = 0
while N >= 0:
    # N이 5의 배수라면 (최대한 5kg 봉지를 사용)
    if N % 5 == 0:
        bags += N // 5
        print(bags)
        break
    # 그렇지 않다면 3kg 봉지 하나 사용
    N -= 3
    bags += 1
else:
    # 정확히 N kg을 만들 수 없는 경우
    print(-1)

N이 5의 배수인지 아닌지를 한 번 더 나눠주고 while을 사용한 풀이이다.

정리

이 문제는 국소 최적해가 전체 최적해를 보장하는 문제의 특성 때문에 그리디 알고리즘으로 해결 가능하다. "큰 봉지(5kg)를 가능한 많이 사용" 하는 것이 최선의 선택임을 보장하고 있기 때문이다.

백준 11399

무조건 시간이 적게 걸리는 사람부터 돈을 인출하면 된다. 자신이 인출하는데 걸린 시간 * (뒷사람 수 +1) 해주면 된다. 반복문을 돌리는데 리스트의 인덱스 번호와 사람수가 반대로 가서 정렬을 걸리는 시간이 큰 순서대로 해주었다.

# 나의 풀이
N = int(input())
time = sorted(list(map(int, input().split())), reverse=True)
sum = 0

for i in range(N):
  sum += time[i] * (i+1)

print(sum)

정리

이 문제는 그리디 알고리즘과 정렬 알고리즘을 사용한 문제이다. 최적의 해를 구하기 위해선 각 사람이 돈을 인출하는 시간을 오름차순으로 정렬하는 것이 핵심이다.

백준 1715

크기 순서대로 정렬해서 하나씩 더해주면 된다고 생각했다. 만약 2개의 합이 다음 카드보다 크다면 큰 카드가 작은 카드보다 한 번 더 더해지는 것이므로 재정렬해줘야 한다. pop, deque 2가지를 사용해서 코드를 짜봤지만 N이 매우 커서 시간초과가 생겼다.

📌 우선순위 heapq

heapq.heappush(heap, item) : item을 heap 에 추가
원소가 작은 순서대로 정렬된다

import heapq

heap_list = []
heapq.heappush(heap_list, 2)
heapq.heappush(heap_list, 1)
heapq.heappush(heap_list, 5)
heapq.heappush(heap_list, 3)

print(heap_list) # [1, 2, 3, 5]

heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴
비어있는 경우 IndexError 호출

print(heapq.heappop(heap_list))  # 1
print(heap_list)  # [2, 3, 5] 
a = heapq.heappop(heap_list)
print(a)  # 2

풀이
1. heapq를 사용하여 카드 중에서 가장 작은 묶음 2개를 뽑는다.
2. 두 원소를 더하고, 새로 만들어진 묶음을 다시 카드에 넣는다.
3. 카드에서 또 다시 제일 작은 묶음을 구하고 더한다.

import heapq

n = int(input())
cards = []

for _ in range(n):
  heapq.heappush(cards, int(input()))

result = 0
while len(cards) > 1:
  # 가장 작은 카드 뽑기
  a = heapq.heappop(cards)
  b = heapq.heappop(cards)
  sum_value = a + b

  result += sum_value
  heapq.heappush(cards, sum_value)
  

print(result)

정리

우선순위 큐를 활용하여 최적의 해를 구하는 그리디 알고리즘이다.