앞서 그리디 알고리즘을 공부했고, 이번엔 우선순위 큐(힙) 자료구조를 사용한 그리디 알고리즘 문제를 풀어보려 한다.
우선순위 큐(Heap)
우선순위 큐(Priority Queue)는 우선순위가 높은 요소를 먼저 처리하는 큐입니다. 기본적인 큐(Queue)는 선입선출(FIFO) 방식인데, 우선순위 큐는 우선순위가 높은 데이터부터 먼저 나오는 구조이다. 우선순위 큐는 보통 힙(Heap)을 이용해서 구현된다. 우선순위 큐는 특히 우선순위가 중요한 문제에서 많이 사용된다.
큐(queue) : 선입선출(FIFO)
스택(stack) : 후입선출(LIFO)
우선순위 큐(heap) : 우선순위
왜 힙(Heap)을 쓰는가?
우선순위 큐는 힙(Heap) 자료구조를 사용하여 효율적으로 구현된다. 힙은 이진 트리 형태의 자료구조로, 부모 노드가 자식 노드보다 크거나 작은 특징을 가진다.
- 최소 힙 (Min-Heap): 부모 노드가 자식 노드보다 작은 값을 가짐. 루트 노드는 가장 작은 값.
- 최대 힙 (Max-Heap): 부모 노드가 자식 노드보다 큰 값을 가짐. 루트 노드는 가장 큰 값.
우선순위 큐에서 최소 힙을 사용하면 우선순위가 가장 작은 요소를 먼저 꺼낼 수 있고, 최대 힙을 사용하면 가장 큰 요소를 먼저 꺼낼 수 있다. 우선순위 큐에서 최소 힙이 더 자주 사용된다.
힙은 완전 이진 트리 형태로, 트리의 높이가 항상 최소로 유지되므로 O(log N)의 시간 복잡도로 삽입 및 삭제 가능.
배열이나 링크드 리스트를 이용한 큐는 우선순위가 높은 요소를 찾아내는 데 시간이 많이 들지만, 힙을 사용하면 빠르게 우선순위가 높은 데이터를 찾아낼 수 있다.
하지만, 랜덤 액세스가 불편하다. 큐에서 임의의 위치에 있는 데이터를 바로 접근하는 것이 비효율적이다. 큐의 맨 앞의 데이터만 빠르게 꺼낼 수 있다.
우선순위 큐의 기본 동작
삽입 (Insert): 새로운 요소를 큐에 삽입한다. 이때, 힙의 특성에 맞게 위치가 결정. ex) heapq.heappush(heap, 5)
삭제 (Pop/Extract): 우선순위가 가장 높은 요소(최소 힙에서는 가장 작은 값, 최대 힙에서는 가장 큰 값)를 꺼낸다. ex) min_value = heapq.heappop(heap)
Peek: 우선순위가 가장 높은 요소를 삭제하지 않고 확인한다.
우선순위 큐 구현 예시
# 최소힙
import heapq
# 우선순위 큐 생성
heap = []
# 요소 삽입 (우선순위 큐에 값 삽입)
heapq.heappush(heap, 5) # 5 삽입
heapq.heappush(heap, 2) # 2 삽입
heapq.heappush(heap, 8) # 8 삽입
heapq.heappush(heap, 1) # 1 삽입
print("큐 상태:", heap)
# 우선순위가 가장 작은 값 추출
min_value = heapq.heappop(heap)
print("가장 작은 값:", min_value) #-> 1
# 우선순위가 가장 작은 값 확인 (삭제는 안됨)
print("가장 작은 값 확인:", heap[0]) #-> 2heapq는 기본적으로 최소 힙만 제공하지만, 최대 힙처럼 사용하려면 삽입할 때마다 값을 음수로 바꿔서 삽입하고, 꺼낼 때도 음수로 변환하면 됩니다.
#최대힙 구현
import heapq
# 최대 힙을 위한 우선순위 큐
heap = []
# 값 삽입 (음수로 바꿔서 삽입)
heapq.heappush(heap, -5) # -5 삽입
heapq.heappush(heap, -2) # -2 삽입
heapq.heappush(heap, -8) # -8 삽입
heapq.heappush(heap, -1) # -1 삽입
# 가장 큰 값 추출
max_value = -heapq.heappop(heap)
print("가장 큰 값:", max_value) #-> 8 우선순위 큐가 유용한 문제
- 다익스트라 알고리즘 (최단 경로 문제)
그래프에서 각 노드까지의 최단 거리를 구할 때, 우선순위 큐를 이용하여 현재 노드에서 가장 가까운 노드를 우선적으로 처리한다.- 크루스칼 알고리즘 (최소 신장 트리)
간선들을 가중치가 작은 것부터 차례대로 선택하면서 최소 신장 트리를 만들 때 사용한다.- 허프만 코딩 (최소 비용으로 문자열 압축)
문자들에 대해 우선순위 큐를 이용하여 가장 자주 등장하는 문자부터 압축한다.- 배낭 문제 (Knapsack Problem)과 같은 최적화 문제
여러 개의 아이템을 처리할 때 우선순위 큐로 가장 큰/작은 아이템을 선택하면서 문제를 해결할 수 있다.
그리디 문제3 (힙 사용)
모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.
핵심 전략 : 가장 낮은 두 개를 조합해야 모든 음식의 스코빌 값이 K를 넘기는 최소한의 섞기 횟수를 구할 수 있다.
import heapq
def solution(scoville, K): #mixk = lowk + 2(low2k)
answer = 0
heapq.heapify(scoville)
while scoville[0] < K:
if len(scoville) ==1 and mixk <K:
return -1
min_k1 = heapq.heappop(scoville)
min_k2 = heapq.heappop(scoville)
mixk = min_k1 + 2 * min_k2 #5, 13, 35, 80, 172
heapq.heappush(scoville, mixk)
answer += 1
if scoville[0] >= K:
return answer처음에 heapq.heapify()를 이용해 scoville 리스트를 힙으로 초기화하지 않아서 여러 개의 테스트 케이스를 통과하지 못했다. 초기화를 했음에도 테스트 케이스 하나가 계속해서 실패하다가 제한사항을 보고 K가 0일 경우를 놓친 것을 확인했다. 따라서 while문 밖에서 return 0을 추가해주었다. (음식을 섞지 않아도 K값을 넘김)
이 문제의 핵심 전략은 이미 문제 속에서도 알려주고 있었다. 작은 것들을 더해 K값을 넘기게 해야하기 때문이다.
