큐란
큐는 FIFO(First In, First Out) 원칙으로 동작하는 자료구조다. 먼저 넣은 것이 먼저 나온다.
실생활 비유는 줄서기다. 먼저 줄 선 사람이 먼저 서비스를 받는다. 프린터 대기열도 마찬가지다. 먼저 인쇄 요청한 문서가 먼저 출력된다.
enqueue → front [A, B, C] rear ← enqueue
dequeue ← front [B, C] ← D 추가 후: [B, C, D]Python에서 큐 구현하기
collections.deque로 구현
코딩 테스트에서 큐는 collections.deque를 사용하는 것이 표준이다.
from collections import deque
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
front = queue.popleft()
print(front)
print(queue)출력:
1
deque([2, 3])append()로 뒤에 넣고, popleft()로 앞에서 꺼낸다. deque의 popleft()는 O(1)이다.
리스트의 pop(0)을 사용하면 안 되는 이유가 있다. pop(0)은 첫 번째 요소를 꺼내고 나머지 요소를 전부 한 칸씩 앞으로 당겨야 하기 때문에 O(n)이 된다. 요소가 10만 개인 큐에서 pop(0)을 10만 번 반복하면 O(n²)이 되어 시간 초과가 난다.
queue.Queue (스레드 안전)
Python 표준 라이브러리에는 queue.Queue도 있다.
import queue
q = queue.Queue()
q.put(1)
q.put(2)
item = q.get()
print(item)내부적으로 락(Lock)을 사용해 멀티스레드 환경에서 안전하게 사용할 수 있다. 코딩 테스트에서는 싱글스레드 환경이라 deque가 더 가볍고 빠르다.
클래스로 직접 구현 (연결 리스트 기반)
class Node:
def __init__(self, value):
self.value = value
self.next = None
class Queue:
def __init__(self):
self.front = None
self.rear = None
self.size = 0
def enqueue(self, value):
new_node = Node(value)
if self.rear:
self.rear.next = new_node
self.rear = new_node
if self.front is None:
self.front = new_node
self.size += 1
def dequeue(self):
if self.is_empty():
raise IndexError("큐가 비어 있습니다")
value = self.front.value
self.front = self.front.next
if self.front is None:
self.rear = None
self.size -= 1
return value
def is_empty(self):
return self.front is Nonefront에서 꺼내고 rear에 넣는다. 큐가 비었을 때 마지막 요소를 꺼내면 front와 rear 모두 None으로 초기화해야 한다.
큐의 주요 연산과 시간 복잡도
| 연산 | 설명 | 시간 복잡도 |
|---|---|---|
| enqueue | 뒤에 삽입 | O(1) |
| dequeue | 앞에서 제거 및 반환 | O(1) |
| peek | 앞 요소 조회 (제거 안 함) | O(1) |
| is_empty | 비어 있는지 확인 | O(1) |
| 탐색 | 특정 값 찾기 | O(n) |
큐의 삽입과 삭제는 양쪽 끝에서만 일어나기 때문에 O(1)이다. deque를 사용하면 enqueue(append)와 dequeue(popleft) 모두 O(1)이 보장된다. 리스트의 pop(0)으로 dequeue를 구현하면 O(n)이 되어 위 복잡도를 만족하지 못한다.
큐의 변형
원형 큐 (Circular Queue)
고정 크기 배열로 큐를 구현할 때 사용한다. front와 rear 포인터를 배열 크기로 나눈 나머지(모듈로 연산)로 관리해서 배열 끝에 도달하면 앞으로 돌아온다.
class CircularQueue:
def __init__(self, capacity):
self.capacity = capacity + 1
self.data = [None] * self.capacity
self.front = 0
self.rear = 0
def is_empty(self):
return self.front == self.rear
def is_full(self):
return (self.rear + 1) % self.capacity == self.front
def enqueue(self, value):
if self.is_full():
raise OverflowError("큐가 가득 찼습니다")
self.data[self.rear] = value
self.rear = (self.rear + 1) % self.capacity
def dequeue(self):
if self.is_empty():
raise IndexError("큐가 비어 있습니다")
value = self.data[self.front]
self.front = (self.front + 1) % self.capacity
return valuecapacity + 1 크기의 배열을 사용하는 것은, front == rear를 빈 상태로, (rear + 1) % capacity == front를 가득 찬 상태로 구분하기 위해서다. 슬롯 하나를 비워두지 않으면 두 상태를 구분할 수 없다.
우선순위 큐 (heapq)
일반 큐는 삽입 순서대로 꺼내지만, 우선순위 큐는 우선순위가 높은 것을 먼저 꺼낸다. Python에서는 heapq 모듈로 구현한다.
힙은 완전 이진 트리 구조로, 부모 노드가 항상 자식보다 작거나 같은 성질(최소 힙)을 유지한다. 배열로 표현할 때 인덱스 i의 부모는 i // 2, 왼쪽 자식은 2*i + 1, 오른쪽 자식은 2*i + 2다. heappush는 배열 끝에 추가한 뒤 부모와 비교하며 위로 올라가고(sift up), heappop은 루트를 꺼낸 뒤 맨 끝 요소를 루트로 올리고 아래로 내려보낸다(sift down). 두 연산 모두 트리 높이만큼만 이동하므로 O(log n)이다.
import heapq
pq = []
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 4)
heapq.heappush(pq, 1)
heapq.heappush(pq, 5)
while pq:
print(heapq.heappop(pq), end=' ')출력:
1 1 3 4 5heapq는 최소 힙으로 구현되어 있어서 가장 작은 값이 먼저 나온다. 최대 힙이 필요하면 값에 -를 붙여 넣고 꺼낼 때 다시 -를 붙이면 된다.
heapq.heappush(pq, -value)
max_value = -heapq.heappop(pq)덱 (Deque)
deque는 앞뒤 양쪽에서 모두 삽입과 삭제가 가능한 자료구조다.
from collections import deque
dq = deque([1, 2, 3])
dq.appendleft(0)
dq.append(4)
print(dq)
dq.popleft()
dq.pop()
print(dq)출력:
deque([0, 1, 2, 3, 4])
deque([1, 2, 3])스택과 큐 기능을 모두 가진다. 슬라이딩 윈도우 문제에서 특정 범위의 최댓값/최솟값을 O(n)에 구하는 단조 덱 패턴에도 자주 사용된다.
큐 활용 패턴
BFS (너비 우선 탐색)
BFS는 큐의 가장 대표적인 활용이다. 시작 노드에서 거리가 1인 노드를 모두 방문하고, 그다음 거리 2인 노드를 방문하는 방식으로 층위별로 탐색한다. 최단 거리 문제에서 사용한다.
FIFO 특성이 층위별 탐색을 구조적으로 보장한다. 현재 층위의 노드들을 큐에서 꺼내며 이웃을 추가하면, 이웃들은 모두 큐의 뒤에 쌓인다. FIFO 특성상 현재 층위의 노드를 전부 꺼낸 뒤에야 다음 층위 노드가 앞으로 나온다. 만약 큐 대신 스택(LIFO)을 사용하면, 방금 추가한 이웃 노드가 바로 다음에 처리되어 깊이 방향으로 탐색하는 DFS가 된다.
그래프 탐색은 노드와 간선으로 연결된 구조에서 모든 노드를 방문하는 것이다. BFS는 시작점에서 거리가 같은 모든 노드를 먼저 방문하고 나서 더 멀리 떨어진 노드로 나아간다. 연못에 돌을 던졌을 때 물결이 동심원으로 퍼지는 것과 같은 방식이다.
코드에서 visited가 필요한 이유는 무한 루프를 막기 위해서다. 그래프에 순환이 있으면 A → B → C → A처럼 같은 노드로 계속 돌아올 수 있다. 방문한 노드를 visited에 기록해두면 두 번 방문하지 않는다.
visited = set([start])로 시작하는 것은 시작 노드를 큐에 넣는 순간 방문 처리하기 위해서다. 큐에서 꺼낼 때 방문 처리하면, 같은 노드가 여러 경로를 통해 큐에 여러 번 들어가는 경우가 생길 수 있다.
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order2D 미로에서 BFS로 최단 경로를 구하는 패턴은 다음과 같다.
2D 미로는 그래프로 바꿀 수 있다. 각 칸을 노드로, 이동 가능한 인접 칸 사이의 연결을 간선으로 보면 된다. 상하좌우 네 방향 이동이 가능하므로 하나의 칸에서 최대 네 개의 이웃이 생긴다.
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]는 오른쪽, 왼쪽, 아래, 위 방향의 행·열 변화량이다. for 루프 한 번으로 네 방향을 모두 탐색할 수 있다.
distance를 큐에 함께 넣는 이유는 각 칸까지의 거리를 따로 계산하지 않아도 되도록 하기 위해서다. 큐에 들어갈 때 이전 칸의 거리에 1을 더해서 저장하면, 꺼낼 때 바로 사용할 수 있다.
BFS가 최단 거리를 보장하는 이유는 층위별 탐색 때문이다. 거리 1인 칸을 모두 방문한 뒤에 거리 2인 칸을 방문한다. 목적지에 처음 도달했을 때의 거리가 최단 거리다.
from collections import deque
def bfs_maze(maze, start, end):
rows, cols = len(maze), len(maze[0])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
visited = [[False] * cols for _ in range(rows)]
queue = deque([(start[0], start[1], 1)])
visited[start[0]][start[1]] = True
while queue:
row, col, distance = queue.popleft()
if (row, col) == end:
return distance
for dr, dc in directions:
nr, nc = row + dr, col + dc
if 0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc] and maze[nr][nc] == 1:
visited[nr][nc] = True
queue.append((nr, nc, distance + 1))
return -1시작점에서 끝점까지의 최단 거리를 반환한다. maze[nr][nc] == 1이 통과 가능한 칸이다.
시뮬레이션 문제
큐는 순서가 있는 처리 과정을 시뮬레이션할 때도 많이 사용한다. 프린터 우선순위 문제가 대표적이다.
시뮬레이션 문제는 실제 상황의 규칙을 그대로 코드로 옮기는 유형이다. 순서대로 처리해야 하는 규칙이 있을 때 큐가 자연스럽게 맞는다.
프린터 큐 문제의 규칙은 다음과 같다. 대기열 맨 앞 문서를 꺼낸다. 뒤에 현재 문서보다 우선순위가 높은 문서가 있으면 현재 문서를 맨 뒤로 보낸다. 그렇지 않으면 인쇄한다.
enumerate(priorities)는 각 문서에 원래 위치(인덱스)를 붙이는 작업이다. 인덱스를 함께 저장해두어야 나중에 "내가 찾는 문서가 몇 번째로 인쇄됐는지" 확인할 수 있다.
any(p > priority for _, p in queue)는 큐에 현재 문서보다 우선순위가 높은 것이 하나라도 있는지 확인한다. 있으면 현재 문서를 맨 뒤로 보내고, 없으면 인쇄한다.
from collections import deque
def printer_queue(priorities, target):
queue = deque(enumerate(priorities))
print_order = 0
while queue:
idx, priority = queue.popleft()
if any(p > priority for _, p in queue):
queue.append((idx, priority))
else:
print_order += 1
if idx == target:
return print_order현재 문서보다 우선순위가 높은 문서가 뒤에 있으면 다시 큐 뒤로 보낸다. 그렇지 않으면 인쇄하고 카운터를 올린다.
연습 문제
초급
| 번호 | 문제 | 난이도 | 링크 | 핵심 접근 |
|---|---|---|---|---|
| 10845 | 큐 | 브론즈 2 | https://www.acmicpc.net/problem/10845 | deque로 front/back/size/empty 명령 구현 |
| 2164 | 카드2 | 실버 4 | https://www.acmicpc.net/problem/2164 | 맨 위 카드를 버리고 그다음 카드를 맨 아래로 이동 |
| 11866 | 요세푸스 문제 0 | 실버 5 | https://www.acmicpc.net/problem/11866 | deque로 k번 회전 후 popleft |
중급
| 번호 | 문제 | 난이도 | 링크 | 핵심 접근 |
|---|---|---|---|---|
| 1966 | 프린터 큐 | 실버 3 | https://www.acmicpc.net/problem/1966 | 우선순위 비교 후 뒤로 보내거나 출력 |
| 2178 | 미로 탐색 | 실버 1 | https://www.acmicpc.net/problem/2178 | BFS로 시작점에서 도착점까지 최단 거리 |
| 1697 | 숨바꼭질 | 실버 1 | https://www.acmicpc.net/problem/1697 | BFS로 수빈이 위치에서 동생 위치까지 최소 시간 |
'CodingTest > 자료구조-알고리즘' 카테고리의 다른 글
| [DFS & BFS] (0) | 2026.03.31 |
|---|---|
| [재귀 & 완전 탐색] & [백트래킹] (0) | 2026.03.24 |
| 해시 (Hash) (1) | 2026.03.17 |
| 스택 (Stack) (0) | 2026.03.17 |
| 연결 리스트 (Linked List) (0) | 2026.03.16 |