파이썬으로 큐(Queue) 문제를 풀 때는 리스트(list)를 사용하기보다 표준 라이브러리인 collections.deque를 사용하는 것이 핵심입니다.
리스트의 pop(0)은 시간 복잡도가 $O(N)$이라 효율성 테스트에서 탈락하기 쉽지만, deque의 popleft()는 **$O(1)$**로 매우 빠르기 때문입니다.
1. 큐의 기본 연산 (Enqueue, Dequeue)
collections.deque를 활용한 표준적인 큐 구현 방식입니다.
from collections import deque
# 1. 큐 생성
queue = deque()
# 2. 데이터 추가 (Enqueue)
queue.append(1)
queue.append(2)
queue.append(3)
# 3. 데이터 꺼내기 (Dequeue) - 왼쪽에서 제거 및 반환
first_element = queue.popleft() # 1이 제거됨
# 4. 맨 앞 데이터 확인 (Peek)
if queue:
front = queue[0]
# 5. 큐가 비었는지 확인
if not queue:
print("큐가 비어있습니다.")
2. 우선순위와 함께 데이터 관리하기
프로그래머스 "프로세스(구 프린터)" 문제처럼 (데이터, 우선순위)를 묶어서 처리해야 할 때 자주 쓰이는 패턴입니다.
from collections import deque
def process_example(priorities, location):
# (우선순위, 원래 인덱스) 형태의 튜플로 큐 생성
queue = deque([(p, i) for i, p in enumerate(priorities)])
print(f"초기 큐 상태: {queue}")
# 예시: 하나씩 꺼내며 조건 확인
while queue:
current = queue.popleft()
# 큐에 더 높은 우선순위가 있는지 확인하는 로직 등...
# if any(current[0] < q[0] for q in queue):
# queue.append(current)
이 코드는 보통 코딩 테스트에서 **"프린터"**나 "프로세스 스케줄링" 문제로 자주 등장하는 로직의 기초 단계입니다. 핵심은 우선순위가 높은 것을 먼저 처리하되, 원래의 위치(index)를 기억해야 한다는 점입니다.
1. 코드 핵심 포인트
① enumerate와 튜플 사용
queue = deque([(p, i) for i, p in enumerate(priorities)])
단순히 우선순위 값만 큐에 넣으면, 나중에 값이 같은 것들끼리 섞였을 때 "내가 찾던 그 작업"이 무엇인지 알 수 없게 됩니다. 그래서 **(우선순위, 원래 인덱스)**를 한 쌍으로 묶어서 저장하는 것입니다.
- 예: priorities = [2, 1, 3] → queue = [(2, 0), (1, 1), (3, 2)]
② deque.popleft()의 활용
일반적인 리스트의 pop(0)은 시간 복잡도가 $O(n)$이지만, collections.deque의 popleft()는 **$O(1)$**입니다. 큐(Queue)의 FIFO(First-In-First-Out) 원칙을 가장 효율적으로 구현한 방식입니다.
2. 주석 처리된 로직의 의미 (중요)
주석으로 처리된 부분은 이 알고리즘의 결정적인 규칙을 담고 있습니다.
if any(current[0] < q[0] for q in queue):
queue.append(current)
- any(...): "큐 안에 지금 내가 꺼낸 것보다 우선순위가 높은 게 하나라도 있니?"라고 묻는 것입니다.
- append: 만약 더 높은 게 있다면, 지금 꺼낸 것을 다시 맨 뒤로 보냅니다. (순서가 밀리는 것이죠.)
- 처리 완료: 만약 내가 꺼낸 게 가장 높은 우선순위라면, 다시 넣지 않고 그대로 종료(인쇄/처리)합니다.
3. 전체 흐름 예시
만약 priorities = [1, 2, 3], location = 0(첫 번째 1이 언제 나가는지 궁금함) 이라면:
- 초기: [(1, 0), (2, 1), (3, 2)]
- 1회전: (1, 0)을 꺼냈는데, 뒤에 2, 3이 있으므로 다시 뒤로 보냄 → [(2, 1), (3, 2), (1, 0)]
- 2회전: (2, 1)을 꺼냈는데, 뒤에 3이 있으므로 다시 뒤로 보냄 → [(3, 2), (1, 0), (2, 1)]
- 3회전: (3, 2)를 꺼냄. 뒤에 더 큰 게 없으므로 처리 완료! (1번째로 나감)
- 4회전: (1, 0)을 꺼냄. 뒤에 2가 있으므로 다시 뒤로 보냄... (반복)
4. 이 코드가 쓰이는 곳
- 운영체제(OS)의 스케줄링: 우선순위가 높은 프로세스를 먼저 처리해야 할 때.
- 프린터 대기열: 문서의 중요도에 따라 인쇄 순서를 바꿀 때.
3. 원형 큐 (Circular Queue) 느낌 구현하기
큐의 맨 앞 원소를 꺼내서 다시 맨 뒤로 보내는 작업은 **"요세푸스 문제"**나 "카드 게임" 유형에서 매우 자주 나옵니다.
from collections import deque
cards = deque([1, 2, 3, 4, 5])
# 맨 앞 장을 버리고, 그다음 장을 맨 뒤로 보내는 예시
while len(cards) > 1:
cards.popleft() # 1 버림
moved = cards.popleft() # 2 꺼냄
cards.append(moved) # 2를 뒤로 보냄
print(f"마지막 남은 카드: {cards[0]}")
이 코드는 카드 게임이나 특정 규칙에 따라 데이터를 조작할 때 자주 사용되는 "카드 섞기/버리기" 로직입니다. 백준(BOJ)의 '카드2'와 같은 문제의 핵심 풀이법이기도 합니다.
이 알고리즘의 핵심은 **deque를 이용한 원형 회전(Rotation)**입니다.
1. 코드의 동작 단계
카드가 한 장 남을 때까지 다음 두 단계를 반복합니다.
- cards.popleft(): 큐의 가장 앞에 있는 카드를 완전히 제거합니다. (카드를 바닥에 버리는 동작)
- moved = cards.popleft() 후 cards.append(moved): 그다음 장을 꺼내서 맨 뒤로 다시 집어넣습니다. (카드를 아래로 옮기는 동작)
2. 시뮬레이션 (cards = [1, 2, 3, 4, 5])
과정을 한 단계씩 따라가 보면 왜 특정 숫자가 남는지 이해하기 쉽습니다.
| 단계 | 현재 큐 상태 | 동작 설명 | 남은 상태 |
| 시작 | [1, 2, 3, 4, 5] | 초기 상태 | - |
| 1회전 | [1, 2, 3, 4, 5] | 1 버리고, 2를 뒤로 보냄 | [3, 4, 5, 2] |
| 2회전 | [3, 4, 5, 2] | 3 버리고, 4를 뒤로 보냄 | [5, 2, 4] |
| 3회전 | [5, 2, 4] | 5 버리고, 2를 뒤로 보냄 | [4, 2] |
| 4회전 | [4, 2] | 4 버리고, 2를 뒤로 보냄 | [2] |
| 종료 | [2] | 길이가 1이 되어 중단 | 결과: 2 |
3. 왜 deque를 사용하나요?
리스트(list)를 사용해서 list.pop(0)을 하면, 첫 번째 요소를 뺀 뒤 뒤에 있는 모든 요소를 한 칸씩 앞으로 당겨야 하므로 시간이 오래 걸립니다($O(n)$).
반면, collections.deque는 양쪽 끝에서의 추가와 삭제가 즉시($O(1)$) 이루어지도록 설계되어 있어, 카드가 수만 장인 경우에도 매우 빠르게 동작합니다.
4. 핵심 정리
- 패턴: 버리고 -> 옮기고 -> 버리고 -> 옮기고...
- 종료 조건: 큐의 길이가 1이 될 때까지.
- 활용: 요셉푸스(Josephus) 문제와 같이 순환 구조를 가진 문제를 풀 때 유용합니다.
4. BFS (너비 우선 탐색) 기초 스킬
큐는 그래프 탐색 알고리즘인 BFS의 핵심 도구입니다. 최단 거리를 구할 때 아래와 같은 템플릿을 사용합니다.
from collections import deque
def bfs(graph, start_node):
visited = []
queue = deque([start_node])
while queue:
node = queue.popleft()
if node not in visited:
visited.append(node)
# 인접 노드들을 큐에 추가
queue.extend(graph[node])
return visited이 코드는 그래프 탐색의 가장 기본이 되는 BFS(Breadth-First Search, 너비 우선 탐색) 알고리즘을 구현한 것입니다.
BFS는 시작 지점에서 가까운 지점부터 차례대로 멀어지며 탐색하는 방식입니다. 마치 잔잔한 호수에 돌을 던졌을 때 파동이 사방으로 퍼져나가는 모습과 비슷합니다.
1. 코드의 주요 구성 요소
- visited (방문 목록): 이미 방문한 노드를 기록하여 **무한 루프(재방문)**에 빠지는 것을 방지합니다.
- queue (대기열): 다음에 방문할 노드들을 순서대로 저장합니다. 먼저 들어온 노드를 먼저 처리하기 위해 deque를 사용합니다.
- graph (인접 리스트): 각 노드가 어떤 노드들과 연결되어 있는지를 나타내는 딕셔너리 형태의 데이터 구조입니다.
2. BFS의 작동 원리 (진행 단계)
- 시작: start_node를 큐에 넣고 시작합니다.
- 추출: 큐의 맨 앞 노드를 꺼냅니다(popleft).
- 검사: 꺼낸 노드가 이미 방문한 곳인지 확인합니다.
- 방문 처리: 방문하지 않았다면 visited에 추가하고, 그 노드와 직접 연결된 모든 이웃 노드를 큐의 뒤에 추가합니다(extend).
- 반복: 큐가 빌 때까지 2~4번 과정을 반복합니다.
3. 쉬운 비유: SNS 친구 찾기
BFS는 내 인맥을 넓혀가는 과정과 똑같습니다.
- 나(시작 노드)를 큐에 넣습니다.
- 나를 꺼내고, 나의 **직접적인 친구들(1촌)**을 모두 큐에 넣습니다.
- 그다음, 1촌 친구들을 한 명씩 꺼내어 그들의 친구들(나에겐 2촌)을 큐에 넣습니다.
- 결과적으로 나 -> 1촌들 -> 2촌들 -> 3촌들 순서로 탐색하게 됩니다.
4. 이 코드의 특징과 주의점
- 최단 경로: BFS는 가중치가 없는 그래프에서 시작점에서 특정 노드까지의 최단 거리를 구할 때 주로 사용됩니다. (가까운 곳부터 먼저 가기 때문입니다.)
- 효율성: 코드 내의 if node not in visited 부분은 리스트에서 검색하므로 데이터가 많아지면 느려질 수 있습니다. 성능을 높이려면 visited를 set 자료형으로 쓰는 것이 좋습니다.
5. 한눈에 보는 실행 예시
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['E'], 'D': [], 'E': []} 일 때:
- queue: [A]
- A 꺼냄 -> visited: [A], queue: [B, C]
- B 꺼냄 -> visited: [A, B], queue: [C, D]
- C 꺼냄 -> visited: [A, B, C], queue: [D, E]
- D, E 차례로 꺼내며 종료.
결과: [A, B, C, D, E] (층별로 탐색 완료)
5. 큐 활용 팁 & 주의사항
- list.pop(0)은 절대 금지: 데이터 개수가 많아지면 연산 속도가 기하급수적으로 느려집니다. 반드시 from collections import deque를 외우세요.
- rotate() 메소드 활용: deque에는 queue.rotate(-1) 같은 함수가 있어, 큐를 왼쪽이나 오른쪽으로 회전시킬 때 매우 유용합니다. (맨 앞을 뒤로 보낼 때 popleft 후 append 대신 사용 가능)
- 최대 길이 제한: deque(maxlen=3)처럼 최대 길이를 정해두면, 꽉 찼을 때 새 데이터를 넣으면 자동으로 가장 오래된 데이터가 삭제됩니다. (슬라이딩 윈도우 유형에 유용)
6. 실전 연습 문제 추천 (프로그래머스)
- Level 2: 프로세스 (가장 전형적인 큐 문제)
- Level 2: 다리를 지나는 트럭 (큐를 이용한 구현/시뮬레이션)
- Level 2: 기능개발 (작업 완료 순서 계산)
- Level 1: 카드 뭉치 (기초적인 큐 원리 활용)
큐는 스택보다 "시뮬레이션" 성격의 문제에 많이 쓰이므로, 문제를 읽고 **"선입선출(First In, First Out)"**이 필요한지 판단하는 연습이 중요합니다!
'프로그래머스 > 스택,큐' 카테고리의 다른 글
| 주식 가격 (1) | 2026.03.16 |
|---|---|
| 스택 문제 풀이 기술 (0) | 2026.01.07 |