큐와 collections.deque
양쪽 끝에서 빠르게 넣고 뺍니다
큐와 collections.deque은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
선입선출
큐는 가게 앞의 줄처럼 도착한 순서대로 항목을 처리합니다. 먼저 들어온 항목이 먼저 나갑니다.
리스트를 사용하면 안 되는 이유
리스트에서도 앞에서 꺼낼 수 있지만, pop(0)은 다른 모든 항목이 왼쪽으로 이동해야 하므로 O(n)입니다. 입력이 크면 너무 느립니다.
q = []
q.pop(0) # O(n), avoid thiscollections.deque 사용하기
collections의 deque는 양쪽 끝에서 O(1)에 항목을 추가하고 제거할 수 있는 양방향 큐입니다. 대회에서 가장 먼저 고려할 자료 구조입니다.
from collections import deque
q = deque()뒤에 넣기
리스트와 똑같이 append를 사용해 오른쪽 끝에 새 항목을 추가합니다. 이곳이 큐의 뒤쪽입니다.
q.append(1)
q.append(2)앞에서 꺼내기
popleft를 사용해 왼쪽에서 가장 오래된 항목을 제거합니다. 이 연산은 상수 시간에 실행되며 진정한 FIFO 동작을 제공합니다.
first = q.popleft() # returns 1양쪽 끝 모두 사용하기
덱은 appendleft와 오른쪽에서의 pop도 지원합니다. 이러한 유연성 덕분에 하나의 자료 구조를 스택이나 큐로 사용할 수 있습니다.
q.appendleft(0)
last = q.pop()꺼내기 전에 확인하기
빈 덱에서 제거하면 오류가 발생하므로, 순회를 안전하게 유지하려면 반복문에서 while q로 확인해야 합니다.
while q:
x = q.popleft()큐로 BFS 구현하기
대회에서 가장 흔히 사용하는 경우는 BFS입니다. 시작 노드를 큐에 넣고, 앞에서 계속 꺼내면서 이웃 노드를 넣습니다.
간단한 BFS 뼈대
이 반복문은 노드를 계층별로 방문합니다. 각 이웃 노드는 append되고 나중에 도착한 순서대로 처리됩니다.
while q:
node = q.popleft()
for nb in graph[node]:
q.append(nb)덱 크기 제한하기
maxlen을 지정하면 덱이 가득 찼을 때 가장 오래된 항목을 버립니다. 슬라이딩 윈도우와 최근 기록 추적에 적합합니다.
window = deque(maxlen=3)하나의 자료 구조, 다양한 역할
덱은 양쪽 끝에서 빠르다는 점을 기억해 두십시오. 큐, 스택 또는 슬라이딩 버퍼가 필요할 때마다 덱을 사용하면 됩니다.
확인 문제
큐에서 앞쪽 항목을 빠르게 제거해야 합니다. 어떤 선택이 올바를까요?
복습: 덱은 빠른 큐입니다
collections.deque를 배웠습니다. append와 popleft로 O(1) FIFO를 구현하고, 양쪽 끝을 사용할 수 있으며, 윈도우에는 maxlen을 사용할 수 있습니다. BFS의 핵심 자료 구조입니다. 🎯
자주 묻는 질문
“큐와 collections.deque” 강의는 무료인가요?
네 — “큐와 collections.deque” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“큐와 collections.deque”에서 뭘 배우나요?
양쪽 끝에서 빠르게 넣고 뺍니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“큐와 collections.deque” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 괄호 짝 맞추기를 위한 스택
- 단조 스택: 다음으로 큰 원소
- 큐와 collections.deque
- 덱으로 슬라이딩 윈도 최댓값 구하기