큐 구현과 덱
Python의 deque로 큐를 만들고 원형 큐를 구현하며, 단조 덱을 사용해 슬라이딩 윈도우 최댓값을 구합니다.
큐 구현과 덱은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
Queue 자료 구조
큐는 선입선출(FIFO) 자료 구조입니다. 먼저 enqueue한 요소가 먼저 dequeue됩니다. 매장의 계산대 줄과 같습니다. 핵심 연산은 enqueue(뒤쪽에 추가)와 dequeue(앞쪽에서 제거)입니다. 큐가 효율적이려면 두 연산 모두 O(1)이어야 합니다.
파이썬 리스트를 큐로 사용하는 것은 쉬워 보이지만 잘못된 방법입니다. list.pop(0)은 모든 요소를 이동시키므로 O(n)이 걸립니다. 올바른 도구는 collections.deque이며, O(1)의 appendleft, append, popleft, pop을 제공합니다.
from collections import deque
queue = deque()
# Enqueue (add to rear)
queue.append(10)
queue.append(20)
queue.append(30)
print('Queue:', queue) # deque([10, 20, 30])
# Peek front
print('Front:', queue[0]) # 10
# Dequeue (remove from front)
print('Dequeued:', queue.popleft()) # 10
print('Queue after:', queue) # deque([20, 30])덱을 사용하는 Queue 클래스
면접관이 기대하는 형태에 맞추기 위해 명확한 연산 이름을 사용하도록 deque를 Queue 클래스로 감쌉니다. 내부적으로 enqueue는 append를 호출하고 dequeue는 popleft를 호출합니다. peek 연산은 제거하지 않고 queue[0]을 읽습니다.
from collections import deque
class Queue:
def __init__(self):
self._data = deque()
def enqueue(self, val):
self._data.append(val)
def dequeue(self):
if self.is_empty():
raise IndexError('dequeue from empty queue')
return self._data.popleft()
def peek(self):
if self.is_empty():
raise IndexError('peek at empty queue')
return self._data[0]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
q = Queue()
q.enqueue(1); q.enqueue(2); q.enqueue(3)
print(q.peek()) # 1
print(q.dequeue()) # 1
print(len(q)) # 2큐를 사용하는 BFS
큐의 대표적인 활용 사례는 너비 우선 탐색(BFS)입니다. 루트를 enqueue하고, 큐가 비어 있지 않은 동안 노드를 dequeue하여 처리한 다음 방문하지 않은 이웃 노드를 enqueue합니다. 노드를 레벨별로 처리하므로 BFS는 가중치가 없는 그래프에서 최단 경로를 자연스럽게 찾습니다. 큐에는 항상 인접한 두 레벨 이하의 노드만 들어 있습니다.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
return order
graph = {0:[1,2], 1:[0,3,4], 2:[0,5], 3:[1], 4:[1], 5:[2]}
print(bfs(graph, 0)) # [0, 1, 2, 3, 4, 5]원형 Queue(LeetCode 622)
LeetCode 622 '원형 큐 설계': 고정된 용량으로 순환하는 큐를 구현합니다. 크기가 k인 배열과 두 포인터 head와 tail을 사용합니다. tail에서 enqueue하고 head에서 dequeue하며, 위치는 k로 나눈 나머지를 사용해 계산합니다. count 변수는 큐가 가득 찬 상태와 빈 상태를 구분합니다. 그렇지 않으면 두 상태 모두 k로 나눈 나머지 기준으로 head와 tail이 같기 때문입니다.
class MyCircularQueue:
def __init__(self, k):
self.data = [0] * k
self.head = 0
self.tail = 0
self.count = 0
self.k = k
def enQueue(self, value):
if self.isFull(): return False
self.data[self.tail] = value
self.tail = (self.tail + 1) % self.k
self.count += 1
return True
def deQueue(self):
if self.isEmpty(): return False
self.head = (self.head + 1) % self.k
self.count -= 1
return True
def Front(self):
return -1 if self.isEmpty() else self.data[self.head]
def Rear(self):
return -1 if self.isEmpty() else self.data[(self.tail - 1) % self.k]
def isEmpty(self): return self.count == 0
def isFull(self): return self.count == self.k
cq = MyCircularQueue(3)
print(cq.enQueue(1), cq.enQueue(2), cq.enQueue(3)) # True True True
print(cq.enQueue(4)) # False (full)
print(cq.Rear()) # 3
print(cq.isFull()) # True
print(cq.deQueue()) # True
print(cq.enQueue(4)) # True단조 덱을 사용하는 슬라이딩 윈도우 최댓값
LeetCode 239 '슬라이딩 윈도우 최댓값': 크기가 k인 각 윈도우에서 최댓값을 찾습니다. 무차별 대입 방법은 O(n*k)입니다. O(n) 방법은 인덱스를 저장하는 단조 감소 덱을 사용합니다. 새 요소마다 다음을 수행합니다. 윈도우 밖에 있는 인덱스를 앞에서 제거하고, 더 작은 값을 가진 인덱스를 뒤에서 제거합니다. 그런 인덱스는 앞으로 어떤 윈도우에서도 최댓값이 될 수 없기 때문입니다. 덱의 앞에는 항상 최댓값이 있습니다.
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove smaller elements from back
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]큐에 리스트 대신 덱을 사용하는 이유
파이썬의 list.pop(0)은 남아 있는 모든 요소를 왼쪽으로 한 칸씩 이동해야 하므로 첫 요소를 제거하는 데 O(n)이 걸립니다. n번 삽입하고 n번 삭제하면 총 O(n²)이 됩니다. collections.deque는 고정 크기 블록으로 이루어진 이중 연결 리스트이며, popleft는 포인터 하나만 조정하므로 O(1)입니다. 노드가 10^5개인 그래프에서 BFS를 수행할 때 O(n)과 O(n²)의 차이는 100ms와 100초의 차이입니다.
import timeit
n = 10000
# Using list (O(n) per popleft)
list_time = timeit.timeit(
stmt='q = list(range(n)); [q.pop(0) for _ in range(n)]',
globals={'n': n}, number=10
)
# Using deque (O(1) per popleft)
from collections import deque
deque_time = timeit.timeit(
stmt='q = deque(range(n)); [q.popleft() for _ in range(n)]',
globals={'n': n, 'deque': deque}, number=10
)
print(f'List: {list_time:.4f}s')
print(f'Deque: {deque_time:.4f}s')
print(f'Speedup: {list_time / deque_time:.1f}x')이진 트리 레벨 순회(LeetCode 102)
LeetCode 102 '이진 트리 레벨 순회': 모든 노드 값을 레벨별로 반환합니다. 큐를 사용하고, 각 레벨이 시작될 때 큐의 크기를 기록합니다. 이 값이 현재 레벨의 노드 수입니다. 정확히 그 수만큼 노드를 dequeue하면서 값을 수집하고 자식 노드를 enqueue합니다. 큐가 빌 때까지 반복합니다.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(levelOrder(root)) # [[3], [9, 20], [15, 7]]heapq를 사용하는 우선순위 큐
Python의 heapq 모듈은 최소 힙(우선순위 큐)을 제공합니다. 따라서 가장 작은 요소가 항상 먼저 큐에서 제거됩니다. heapq.heappush(h, item)은 O(log n)에 요소를 추가하고, heapq.heappop(h)은 O(log n)에 최솟값을 제거합니다. 다익스트라 알고리즘이나 상위 k개 문제와 같은 작업에서는 heapq가 단순 큐를 대신합니다.
import heapq
pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
heapq.heappush(pq, 2)
print('Min:', heapq.heappop(pq)) # 1
print('Min:', heapq.heappop(pq)) # 2
print('Min:', heapq.heappop(pq)) # 3
# Tasks with priorities
tasks = [(2, 'send email'), (1, 'fix bug'), (3, 'write docs')]
heapq.heapify(tasks)
while tasks:
priority, task = heapq.heappop(tasks)
print(f'Priority {priority}: {task}')배경화면 패턴: 단어 사다리를 위한 큐
LeetCode 127 ‘단어 사다리’: 사전의 단어만 사용하여 한 단어를 다른 단어로 변환할 때 필요한 최소 문자 하나 치환 횟수를 구합니다. 한 문자만 다른 단어들을 간선으로 연결하는 그래프로 모델링할 수 있습니다. 이 그래프에 BFS를 적용하면 O(n * L²)에 최단 경로(최소 단계 수)를 찾을 수 있습니다. 여기서 n은 사전의 크기이고 L은 단어의 길이입니다.
from collections import deque
def ladderLength(beginWord, endWord, wordList):
word_set = set(wordList)
if endWord not in word_set:
return 0
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
for ch in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + ch + word[i+1:]
if new_word == endWord:
return steps + 1
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, steps + 1))
return 0
print(ladderLength('hit', 'cog', ['hot','dot','dog','lot','log','cog'])) # 5양방향 큐로서의 deque
collections.deque는 양방향 큐(덱)입니다. 양쪽 끝에서 효율적으로 요소를 추가하고 제거할 수 있습니다. 메서드로 앞쪽에는 appendleft와 popleft를 사용하고, 뒤쪽에는 append와 pop을 사용합니다. 따라서 덱은 FIFO 큐(오른쪽에 추가 + popleft)와 LIFO 스택(append + pop)으로 모두 사용할 수 있습니다. 슬라이딩 윈도 최댓값 문제에서는 양쪽 끝을 모두 사용합니다. 왼쪽에서는 오래된 인덱스를 제거하고, 오른쪽에서는 더 작은 값을 제거합니다.
from collections import deque
dq = deque([3, 4, 5])
dq.appendleft(2) # add to front: [2,3,4,5]
dq.appendleft(1) # add to front: [1,2,3,4,5]
dq.append(6) # add to rear: [1,2,3,4,5,6]
print(dq.popleft()) # 1 (from front)
print(dq.pop()) # 6 (from rear)
print(list(dq)) # [2, 3, 4, 5]요약: 큐와 덱과 힙 비교
문제에 맞는 도구를 선택하십시오. FIFO 처리와 BFS에는 단순 큐(deque)를 사용하십시오. 슬라이딩 윈도의 최댓값이나 최솟값이 필요할 때는 단조 덱을 사용하십시오. 단조 덱은 지배되는 요소를 제거하여 정렬 불변식을 유지합니다. 순서와 관계없이 전체 최솟값이나 최댓값이 필요할 때, 예를 들어 다익스트라 알고리즘이나 상위 k개 문제에서는 우선순위 큐(heapq)를 사용하십시오. 어떤 도구를 언제, 왜 선택해야 하는지 아는 것은 면접관이 평가하는 핵심 역량입니다.
빠른 확인
이번 학습에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념을 얼마나 이해했는지 확인해 보십시오.
학습 내용 복습
이번 학습에서 다음을 배웠습니다. collections.deque는 큐에 넣고 빼는 연산을 O(1)에 제공하므로 Python에서 올바른 큐 구현입니다. BFS는 큐를 사용하여 노드를 레벨별로 처리하고, 가중치가 없는 그래프에서 최단 경로를 찾습니다. 또한 단조 감소 덱은 지배되는 인덱스를 제거하여 O(n)에 슬라이딩 윈도 최댓값을 구합니다. 다음에는 단조 스택 패턴을 자세히 살펴봅니다.
자주 묻는 질문
“큐 구현과 덱” 강의는 무료인가요?
네 — “큐 구현과 덱” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“큐 구현과 덱”에서 뭘 배우나요?
Python의 deque로 큐를 만들고 원형 큐를 구현하며, 단조 덱을 사용해 슬라이딩 윈도우 최댓값을 구합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“큐 구현과 덱” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.