06 — 큐

람다와 제네릭이 편의점 계산대 앞에 줄을 서서 "먼저 온 사람이 먼저 계산하네?"라고 발견하고, 돌핀쌤이 "그게 바로 큐예요!"라며 안내하는 도입 장면

🙋‍♀️ 람다: "편의점 계산대에 줄을 서니까, 먼저 온 사람이 먼저 계산하고 나가네요. 새로 온 손님은 맨 뒤에 서고요."

🐬 돌핀쌤: "두 친구가 오늘 배울 걸 미리 발견했어요. 이렇게 먼저 들어온 것이 먼저 나가는 자료구조를 큐(Queue) 라고 해요. 어제 배운 스택과는 정반대죠!"

🎯 오늘 완성할 코드는?

오늘 우리가 만들 건 큐예요. 파이썬의 deque로 줄 서기처럼 맨 뒤에 넣고(append) 맨 앞에서 꺼내는(popleft) 코드예요.

먼저 완성된 모습부터 볼게요. 지금은 이해 안 돼도 괜찮아요. 아래에서 한 줄씩 천천히 뜯어볼 거예요.

from collections import deque
queue = deque()
queue.append("홍길동")           # enqueue — 맨 뒤에 추가
queue.append("김철수")
queue.append("이영희")
print(queue)        # deque(['홍길동', '김철수', '이영희'])
print(queue[0])     # 홍길동  (맨 앞 확인)
person = queue.popleft()         # dequeue — 맨 앞에서 꺼냄
print(person)       # 홍길동
print(queue)        # deque(['김철수', '이영희'])
person = queue.popleft()
print(person)       # 김철수
print(queue)        # deque(['이영희'])
print(len(queue) == 0)   # False

실행하면 이렇게 나와요.

deque(['홍길동', '김철수', '이영희'])
홍길동
홍길동
deque(['김철수', '이영희'])
김철수
deque(['이영희'])
False

넣은 순서 홍길동 → 김철수 → 이영희 그대로, 꺼낼 때도 맨 앞 홍길동부터 나왔죠?

🐬 돌핀쌤: "짧은 코드지만 큐의 핵심이 다 들어 있어요. 넣기(append), 꺼내기(popleft), 맨 앞 보기(queue[0]). 지금부터 이 코드가 왜 줄 서기처럼 동작하는지 한 줄씩 풀어볼게요."

💡 어떻게 풀까? — 편의점 줄 서기

편의점 계산대 앞에 줄을 서 본 적 있으시죠?

계산대
  ↓
[민수] [지우] [하은] [준서]  ← 새로 온 손님
  ↑
먼저 온 사람이 먼저 계산함

민수가 가장 먼저 왔으니 가장 먼저 계산하고, 새 손님은 항상 맨 뒤에 서요. 줄의 맨 앞을 front, 맨 뒤를 rear 라고 불러요.

큐의 규칙은 딱 하나예요.

먼저 들어온 것이 먼저 나간다. First In, First Out — FIFO

어제 배운 스택과 비교하면 방향이 정반대예요.

비교 항목	스택(Stack)	큐(Queue)
규칙	LIFO (나중에 넣은 게 먼저)	FIFO (먼저 넣은 게 먼저)
현실 비유	접시 쌓기	편의점 계산대 줄
넣는 위치	맨 위(top)	맨 뒤(rear)
꺼내는 위치	맨 위(top)	맨 앞(front)

🙋‍♂️ 제네릭: "스택은 넣고 꺼내는 곳이 둘 다 맨 위였는데, 큐는 넣는 곳(뒤)과 꺼내는 곳(앞)이 다르네요!"

줄 서는 사람 대신 이름 글자가 들어와도 똑같아요. 맨 위 코드의 홍길동 → 김철수 → 이영희 도 이 규칙 그대로 줄을 서고 빠져나가요.

🔍 코드 한 줄씩 뜯어보기

이제 맨 위에서 본 완성 코드를 한 줄씩 볼게요.

① 큐를 준비해요

from collections import deque
queue = deque()

큐는 파이썬의 deque(덱)로 만들어요. from collections import deque 한 줄이면 준비 끝이에요.

💡 왜 그냥 list가 아니라 deque일까요? 리스트는 맨 앞에서 꺼낼 때(pop(0)) 뒤 원소를 전부 한 칸씩 당겨야 해서 느려요(O(n)). deque는 앞 포인터만 옮기면 끝이라 즉시 꺼내요(O(1)). 큐는 항상 deque 라고 외워 두세요.

② 맨 뒤에 넣어요 — enqueue

queue.append("홍길동")           # enqueue — 맨 뒤에 추가
queue.append("김철수")
queue.append("이영희")

append 는 줄의 맨 뒤(rear) 에 새 손님을 세우는 동작이에요. 이걸 enqueue 라고 불러요.

queue.append("홍길동")  →  [홍길동]
queue.append("김철수")  →  [홍길동][김철수]
queue.append("이영희")  →  [홍길동][김철수][이영희]
                                              ↑ 항상 맨 뒤에 추가

③ 맨 앞을 살짝 봐요

print(queue[0])     # 홍길동  (맨 앞 확인)

queue[0] 은 줄 맨 앞(front) 에 누가 있는지 꺼내지 않고 보기만 하는 거예요. 가장 먼저 온 홍길동 이 보여요.

④ 맨 앞에서 꺼내요 — dequeue

person = queue.popleft()         # dequeue — 맨 앞에서 꺼냄

popleft 는 줄 맨 앞(front) 손님을 꺼내서 돌려줘요. 이걸 dequeue 라고 불러요. 가장 먼저 줄 선 홍길동 이 가장 먼저 빠져나가요. 한 번 더 꺼내면 그 다음인 김철수 가 나와요.

popleft()  →  꺼냄: 홍길동,  남은 큐: [김철수][이영희]
popleft()  →  꺼냄: 김철수,  남은 큐: [이영희]

💡 pop() 과 헷갈리지 마세요! queue.pop() 은 맨 뒤에서 꺼내요(스택 방식, LIFO). 큐는 맨 앞에서 꺼내는 queue.popleft() 를 써야 FIFO가 돼요.

⑤ 비어 있는지 확인해요

print(len(queue) == 0)   # False

len(queue) 는 큐에 남은 사람 수예요. == 0 이면 큐가 빈 거예요. 지금은 이영희 가 남아 있으니 False 가 나와요.

🙋‍♀️ 람다: "넣을 땐 홍길동→김철수→이영희, 꺼낼 때도 홍길동→김철수 순서 그대로네요. 스택은 순서가 뒤집혔는데 큐는 그대로 유지돼요!"

🐬 돌핀쌤: "정확해요. 스택은 순서를 뒤집고, 큐는 순서를 그대로 지켜요. 이 차이가 두 자료구조를 구분해서 쓰는 이유예요."

✍️ 직접 완성해보기

이제 빈칸을 채워 직접 완성해봐요. 위에서 본 그대로예요.

from collections import deque
queue = deque()
queue.___("홍길동")          # enqueue — 맨 뒤에 추가
queue.append("김철수")
queue.append("이영희")
print(queue)
print(queue[___])            # 맨 앞(front) 확인 (인덱스 0)
person = queue.___()         # dequeue — 맨 앞에서 꺼냄
print(person)
print(queue)
person = queue.popleft()
print(person)
print(queue)
print(len(queue) == ___)     # 비어있는지 확인 → False

🐬 돌핀쌤: "막히면 위 '코드 한 줄씩 뜯어보기'로 다시 올라가서 확인해요. 다 채웠으면 맨 위 🎯 완성 코드와 비교해보세요. 정답을 외우는 게 아니라 왜 그런지 떠올리는 게 진짜 공부예요."

📌 오늘 배운 것

개념	설명
큐(Queue)	맨 뒤에서 넣고 맨 앞에서 빼는, 먼저 넣은 게 먼저 나오는 자료구조
FIFO	First In, First Out — 먼저 넣은 게 먼저 나옴 (스택의 LIFO와 정반대)
enqueue / dequeue	넣기 `queue.append(값)` / 꺼내기 `queue.popleft()`
맨 앞 확인	`queue[0]` — front 값 보기 (꺼내지 않음)
deque	`from collections import deque` — 큐는 항상 `deque`로, `popleft()`는 O(1)

🐬 돌핀쌤: "넣기(append), 맨 앞 꺼내기(popleft), front 보기(queue[0])! 이 세 박자면 어떤 줄 서기든 큐로 만들 수 있어요. 스택과 큐를 둘 다 알게 됐으니 정말 잘했어요! 👏"

▸ 더 해보기 — 여기서부터는 선택!

여기까지가 오늘의 필수 내용이에요. 아래는 여유 있을 때 도전하는 내용이고, 예제 문제로 직접 풀어볼 수 있어요. 외울 필요는 없어요.

큐로 줄 서기 끝까지 처리하기 — while len(queue) > 0: 로 큐가 빌 때까지 한 명씩 popleft() 하면, 손님을 줄 선 순서대로 모두 처리할 수 있어요. (while queue: 로 짧게 써도 같은 뜻이에요.) → 예제로 연습
빈 큐 꺼내기 막기 — 빈 큐에서 popleft() 하면 IndexError 가 나요. 꺼내기 전에 if len(queue) > 0: 으로 먼저 확인하는 습관을 들여요. → 예제로 연습
pop() 과 popleft() 구분 — pop() 은 맨 뒤(스택 LIFO), popleft() 는 맨 앞(큐 FIFO)이에요. 큐를 만들 땐 꼭 popleft() 를 써야 해요. → 예제로 연습

🐬 돌핀쌤: "다음에 그래프를 배울 때 나오는 너비 우선 탐색(BFS) 도 큐로 만들어요. 오늘 배운 큐가 그때 아주 큰 힘이 될 거예요. 기본을 완벽히 익힌 다음 도전하세요!"

06 — 큐

📃 해결할 문제

💻 예제 입력 1

🖨️ 예제 출력 1