큐
- 큐는 데이터를 선입선출(FIFO)로 관리하는 자료구조이다. 파이썬에서 collections 패키지를 이용해 구현할 수 있다.
from collections import deque
q = deque([])
q.append(2)
q.popleft()
- 이렇게 구현하면 deque에서 앞에서 나오고 뒤로 들어가는 구조라고 생각할 수 있다.
우선순위 큐
- 우선순위 큐는 어떤 요소를 제거할 때, 즉 pop할 때 특정한 우선순위를 갖고 pop하는 자료구조이다.
- 예를 들어 pop할 때는 가장 작은 값을 제거하는 등의 특징을 구현할 수 있다.
이 경우 queue 패키지를 이용해 구현할 수 있다.
form queue import PriorityQueue
q = PriorityQueue(maxsize = 10)
- 우선순위 큐 생성 및 초기화 방법
maxsize를 지정하지 않으면 크기는 무한대가 된다.
q.put(5)
q.put(3)
print(q.get()) # 3
print(q.get()) # 5- 우선순위 큐에서는
put으로 push연산을,get으로 pop연산을 수행한다. - put(), get() 함수는 O(logn)의 시간이 걸린다.
우선순위 큐에서의 정렬
- 기본적으로 가장 작은 원소를 pop하도록 설정되어 있다. (heapq로 구현되어 있음)
- 정렬 순서를 바꾸기 위해서는 heaqp를 사용할 때처럼 튜플을 이용하면 된다.
- 튜플의 첫 번째 원소에 우선순위를, 두 번째 원소에 자료를 넣으면 된다.
q.put((-5, 5))
q.put((-3, 3))
print(q.get()[1]) # 5
print(q.get()[1]) # 3문제
1715 : 카드 정렬하기 (G4)
https://www.acmicpc.net/problem/1715
import sys
from queue import PriorityQueue
input = sys.stdin.readline
n = int(input())
q = PriorityQueue()
for _ in range(n):
q.put(int(input()))
result = 0
if n != 1:
while not q.empty():
q1 = q.get()
q2 = q.get()
s = q1 + q2
result += (s)
if q.empty():
break
q.put(s)
print(result)- 현재 순간순간에서 큐에서 가장 작은 숫자 두개를 합하여 큐에 다시 넣는다.
- 연산을 할 때마다 result에 누적해준다.
- 현재 순간에서의 최적해를 찾다보면 결과적으로 최적해를 찾게되므로, 그리디 알고리즘
- 매번 정렬하는 것이 아니라 최솟값 2개만 찾으면 되므로 우선순위 큐를 이용한다.
11000: 강의실 배정 (G5)
https://www.acmicpc.net/problem/11000
import sys
import heapq
input = sys.stdin.readline
q = []
room = []
n = int(input())
for _ in range(n):
heapq.heappush(q, (list(map(int, input().split())))) # 시작 시간, 끝 시간
heapq.heappush(room, heapq.heappop(q)[1])
for i in range(1, n):
v = heapq.heappop(q)
if room[0] <= v[0]:
heapq.heappop(room)
heapq.heappush(room, v[1])
else:
heapq.heappush(room, v[1])
print(len(room))- heapq로 우선순위 큐를 구현했다.
- room이라는 heapq(우선순위큐)에는
각 강의실 별로 강의가 끝나는 시간이 담겨있다. - 모든 강의의 시작시간을 기준으로 반복문을 돌면서, 만약 이전 수업이 끝나서 이어서 수업할 수 있는 강의실이 있다면 heappop후 heappush한다.
- 만약 모든 강의실이 수업중이라면, 즉 강의 시작 시간이 모든 수업들의 강의 끝나는 시간보다 큰 경우 heappush해서 새로운 강의실을 만든다.
