thenullpage.com
1. 먼저 들어온 것을 먼저 꺼내는 구조
큐(queue)는 한쪽 끝으로 값을 넣고 반대쪽 끝으로 값을 빼는 자료구조입니다. 매표소 앞에 늘어선 줄과 같습니다. 새로 온 사람은 맨 뒤에 서고 표를 받는 사람은 항상 맨 앞 사람입니다.
먼저 들어온 값이 먼저 나가는 이 규칙을 선입선출(FIFO)이라고 부릅니다. 넣는 동작은 enqueue, 빼는 동작은 dequeue라고 합니다. 스택이 마지막에 넣은 값부터 꺼내는 구조라면 큐는 정확히 반대편에 있습니다.
순서를 지켜야 하는 일에는 거의 예외 없이 큐가 들어갑니다. 프린터에 보낸 문서, 서버에 도착한 요청, 게임 대기열은 모두 도착한 차례대로 처리됩니다.
2. 리스트로 큐를 만들면 느려집니다
파이썬 리스트에도 맨 앞 값을 빼는 방법이 있습니다. pop(0)입니다. 동작은 하지만 값이 많아지면 눈에 띄게 느려집니다.
import time
queue = list(range(100000))
start = time.time()
while queue:
queue.pop(0)
print(round(time.time() - start, 3))
1.199
값 십만 개를 빼는 데 1초가 넘게 걸렸습니다. 리스트는 값들이 메모리에 나란히 붙어 있는 구조라서 맨 앞을 빼면 뒤에 남은 값 전부를 한 칸씩 앞으로 당겨야 합니다. pop(0) 한 번이 O(n)이고 그것을 n번 반복하니 전체가 O(n^2)이 됩니다. 큐가 필요한 문제에서 시간 초과가 나는 가장 흔한 원인입니다.
3. 큐가 필요하면 deque를 씁니다
표준 라이브러리에 양쪽 끝을 모두 O(1)로 다루는 자료구조가 들어 있습니다. collections 모듈의 deque입니다. 값을 밀어내지 않고 끝의 연결만 바꾸는 방식이라 앞에서 빼도 빠릅니다.
import time
from collections import deque
queue = deque(range(100000))
start = time.time()
while queue:
queue.popleft()
print(round(time.time() - start, 4))
0.0112
같은 일인데 백 배 넘게 빨라졌습니다. 바뀐 것은 자료구조 이름과 메서드 이름뿐입니다. 사용법도 리스트와 크게 다르지 않습니다.
q = deque([1, 2, 3])
q.append(4)
print(q)
print(q.popleft())
print(q)
deque([1, 2, 3, 4])
1
deque([2, 3, 4])
append로 뒤에 넣고 popleft로 앞에서 뺍니다. 이 두 가지만 쓰면 그것이 곧 큐입니다. 비어 있는 상태에서 popleft를 부르면 IndexError가 나니 while q처럼 값이 남았는지 확인하고 꺼냅니다.
4. 덱은 앞뒤 어느 쪽이든 씁니다
deque라는 이름은 덱(double ended queue)에서 왔습니다. 양쪽 끝에서 넣고 빼는 것이 전부 가능하다는 뜻입니다.
q = deque([2, 3, 4])
q.appendleft(0)
print(q)
print(q.pop())
print(q)
deque([0, 2, 3, 4])
4
deque([0, 2, 3])
앞에 넣는 appendleft와 뒤에서 빼는 pop까지 네 가지 동작이 모두 O(1)입니다. 대신 q[0]과 q[-1]은 빠르지만 q[500]처럼 가운데 위치를 읽으면 끝에서부터 따라가야 해서 O(n)입니다. 앞뒤로만 드나든다면 덱, 인덱스로 자주 뒤진다면 리스트라고 나눠 두면 됩니다.
5. 미로의 최단 거리를 큐로 구합니다
큐가 가장 많이 등장하는 자리는 너비 우선 탐색(BFS)입니다. 출발 칸에서 한 칸 거리인 칸들을 먼저 전부 보고, 그다음 두 칸 거리를 보는 식으로 가까운 곳부터 퍼져 나갑니다. 먼저 넣은 칸을 먼저 꺼내면 이 순서가 저절로 지켜집니다. 아래에서 0은 지날 수 있는 칸, 1은 벽입니다.
from collections import deque
grid = [[0, 0, 0, 1],
[1, 1, 0, 1],
[0, 0, 0, 0]]
def bfs(grid):
n, m = len(grid), len(grid[0])
dist = [[-1] * m for _ in range(n)]
dist[0][0] = 0
q = deque([(0, 0)])
while q:
y, x = q.popleft()
for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
ny, nx = y + dy, x + dx
if 0 <= ny < n and 0 <= nx < m:
if grid[ny][nx] == 0 and dist[ny][nx] == -1:
dist[ny][nx] = dist[y][x] + 1
q.append((ny, nx))
return dist[n - 1][m - 1]
print(bfs(grid))
5
dist는 출발점에서 몇 칸 걸렸는지 적어두는 표이고 -1은 아직 가*** 않은 칸이라는 뜻입니다. 방문 여부를 담는 배열을 따로 두지 않고 dist가 -1인지로 판단하니 표 하나가 두 가지 일을 합니다.
가장 자주 나는 실수는 거리를 적는 시점입니다. 큐에서 꺼낼 때 적으면 같은 칸이 큐에 여러 번 들어가 시간과 메모리가 함께 늘어납니다. 위 코드처럼 큐에 넣는 그 자리에서 바로 채워야 합니다.
6. 창을 밀면서 최댓값을 구하는 단조 덱
길이 k짜리 구간을 한 칸씩 옮기며 각 구간의 최댓값을 구하는 문제가 있습니다. 구간마다 max를 부르면 O(nk)입니다. 덱에 위치를 담되 쓸모없어진 값을 뒤에서 버리면 한 번 훑는 것으로 끝납니다.
from collections import deque
def max_window(nums, k):
q = deque()
answer = []
for i, num in enumerate(nums):
while q and nums[q[-1]] <= num:
q.pop()
q.append(i)
if q[0] <= i - k:
q.popleft()
if i >= k - 1:
answer.append(nums[q[0]])
return answer
print(max_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
[3, 3, 5, 5, 6, 7]
새 값보다 작은 값들은 뒤쪽에서 버립니다. 더 큰 값이 나중에 들어온 이상 그 값이 최댓값이 될 일은 없기 때문입니다. 앞쪽에서는 구간 밖으로 밀려난 위치를 떼어냅니다. 그러면 q[0]이 언제나 현재 구간의 최댓값 위치가 됩니다. 양쪽 끝을 다 써야 하므로 여기서는 큐가 아니라 덱이 필요하고, 남아 있는 값이 큰 것부터 줄지어 있어 단조 덱이라고 부릅니다. 모든 위치가 한 번 들어갔다 한 번 나오므로 전체는 O(n)입니다.
7. 큐를 떠올려야 하는 상황
큐는 도착한 순서를 그대로 지켜야 할 때, 덱은 앞뒤 양쪽에서 드나들어야 할 때 꺼내는 도구입니다. 대기열 시뮬레이션, 요청 처리, 가중치가 없는 격자나 그래프의 최단 거리 탐색이 전부 여기에 속합니다.
챙길 것은 세 가지입니다. 큐가 필요하면 리스트 대신 deque를 쓴다는 것, pop(0)은 O(n)이라 반복문 안에 들어가면 시간 초과의 원인이 된다는 것, 너비 우선 탐색에서 방문 표시는 큐에 넣는 순간에 한다는 것입니다.