코딩 테스트 합격자 되기 | 07 큐 학습 기록
이번 글은 박경록 저자의 「코딩 테스트 합격자 되기 - 파이썬 편」에서 큐로 구성된 범위만 정리한 기록이다. 큐의 개념과 ADT, 문제 15 요세푸스 문제, 문제 16 기능 개발, 문제 17 카드 뭉치를 순서대로 정리했다. 첨부한 큐 PDF의 17쪽 대화에 나온 기능 개발 코드, max_day 질문, 카드 뭉치의 인덱스 범위 오류와 deque 풀이 질문도 모두 반영했다.
07 큐: 이번 글의 범위
| 구성 | 이번 글에서 다루는 내용 | PDF 대화 반영 |
|---|---|---|
| 07-1 큐의 개념 | FIFO, front, rear, enqueue, dequeue, deque | 큐 개념의 기초 문법으로 정리 |
| 07-2 몸풀기 | 문제 15 요세푸스 문제 | 큐 회전, 탈락, 마지막 생존자 반환을 포함 |
| 07-3 모의 테스트 | 문제 16 기능 개발, 문제 17 카드 뭉치 | 내 코드, 오류, 질문, 인덱스·deque 풀이 모두 반영 |
1. 큐의 개념
큐는 먼저 들어온 데이터를 먼저 꺼내는 자료구조다. 이를 FIFO, First In First Out이라고 한다. 줄을 서서 먼저 도착한 사람이 먼저 처리되는 흐름을 떠올리면 된다. 데이터는 뒤쪽인 rear에 넣고, 앞쪽인 front에서 꺼낸다.
큐에서 데이터가 이동하는 과정
빈 큐에 A, B, C를 차례로 넣으면 front - [A, B, C] - rear가 된다. dequeue를 한 번 하면 A가 빠지고 front - [B, C] - rear만 남는다. 다음에 D를 넣으면 front - [B, C, D] - rear가 된다. 앞에서 꺼내고 뒤에 넣는 방향이 바뀌지 않는다는 점이 핵심이다.
큐의 특성을 활용하는 경우
먼저 들어온 요청부터 처리하는 대기열, 프린터 작업 순서, 선착순 예약, BFS 탐색처럼 처리 순서가 중요한 상황에서 큐를 쓴다. 이번 범위의 요세푸스 문제는 앞사람을 뒤로 보내며 원형 순서를 만들고, 기능 개발은 앞 기능이 뒤 기능의 배포를 막는 순서를 이용하며, 카드 뭉치는 맨 앞 카드만 꺼낼 수 있다는 규칙을 사용한다.
enqueue: rear에 데이터를 넣는 동작
dequeue: front에서 데이터를 꺼내는 동작
front 또는 peek: 꺼내지 않고 가장 앞 데이터를 확인하는 동작
is_empty: 큐가 비어 있는지 확인하는 동작
큐 ADT를 Python으로 읽기
from collections import deque
queue = deque()
queue.append("A")
queue.append("B")
front = queue[0]
removed = queue.popleft()
is_empty = not queueADT는 자료구조가 제공해야 할 동작을 정리한 약속이다. 큐에서는 보통 빈 큐 생성, 뒤에 넣기, 앞에서 꺼내기, 앞값 확인, 비었는지 확인이 핵심이다. Python에서는 collections.deque가 이 동작을 자연스럽게 제공한다.
큐는 요청을 접수한 순서대로 처리할 때, 대기 작업을 순서대로 실행할 때, 사람이나 작업을 원형으로 돌리며 처리할 때 잘 맞는다. 문제에서 “먼저 들어온 순서”, “맨 앞에서 꺼낸다”, “차례대로 처리한다”가 보이면 큐를 후보로 생각할 수 있다.
파이썬에서는 deque를 사용한다
from collections import deque
queue = deque()
queue.append("first") # rear에 넣기: enqueue
queue.append("second")
front = queue[0] # front 확인, 꺼내지는 않음
first = queue.popleft() # front에서 꺼내기: dequeue
if not queue:
print("큐가 비어 있습니다.")파이썬 리스트에서도 맨 뒤에 넣는 append()는 빠르다. 하지만 맨 앞을 pop(0)으로 꺼내면 뒤의 모든 원소를 한 칸씩 당겨야 해서 O(N)이 된다. deque의 append()와 popleft()는 양 끝에서 O(1)로 동작하므로 큐를 구현할 때 적합하다.
queue[0]이나 queue.popleft()를 하기 전에는 큐가 비었는지 확인해야 한다. 빈 deque의 popleft()는 IndexError를 발생시킨다.
2. 문제 15 - 요세푸스 문제
원형으로 앉은 사람들 가운데 매번 K번째 사람을 탈락시키고, 마지막까지 남은 한 사람의 번호를 반환하는 문제다. 앞에서 K번째를 꺼낸 뒤 남은 사람들을 같은 순서로 계속 이어 가야 하므로 큐를 회전시키는 방식이 자연스럽다.
문제를 큐 동작으로 바꾸기
1. 1번부터 N번까지 사람을 큐에 순서대로 넣는다.
2. K번째 사람이 front에 오도록 앞의 K - 1명을 꺼내 rear로 다시 넣는다.
3. front의 K번째 사람을 꺼내 탈락시킨다.
4. 한 명만 남을 때까지 반복한 뒤, 남은 front 값을 반환한다.
내 풀이: K - 1명은 뒤로 보내고 마지막 생존자 확인
from collections import deque
def solution(n, k):
queue = deque(range(1, n + 1))
while len(queue) > 1:
for _ in range(k - 1):
queue.append(queue.popleft())
queue.popleft()
return queue[0]예를 들어 n = 5, k = 3이면 처음 큐는 [1, 2, 3, 4, 5]다. 1과 2를 뒤로 보내면 [3, 4, 5, 1, 2]가 되고, 이제 맨 앞 3이 탈락한다. 한 명이 남으면 반복을 멈추고 그 사람을 반환한다.
검산: solution(5, 3)의 반환값은 4다.
다른 풀이: deque.rotate()로 회전 표현하기
from collections import deque
def solution(n, k):
queue = deque(range(1, n + 1))
while len(queue) > 1:
queue.rotate(-(k - 1))
queue.popleft()
return queue[0]rotate(-2)는 큐를 왼쪽으로 두 칸 회전한다. 즉 앞의 두 사람을 뒤로 보내는 동작과 같다. 짧게 쓸 수 있지만, 큐를 처음 공부할 때는 첫 번째 풀이처럼 popleft()와 append()가 어떻게 반복되는지 먼저 이해하는 편이 좋다.
3. 문제 16 - 기능 개발
기능은 순서대로 배포해야 한다. 뒤 기능이 먼저 완성되어도 앞 기능이 완료될 때까지 배포할 수 없고, 앞 기능이 배포되는 날 함께 배포된다. 각 배포일에 몇 개의 기능이 묶이는지 반환하는 문제다.
PDF에 있던 처음 코드와 수정해야 할 부분
초기 작성 과정에서 확인한 오류
progresss처럼 매개변수 progresses의 철자가 달라지면 NameError가 난다.
math_ceil이 아니라 모듈과 함수 사이에 점을 쓰는 math.ceil을 사용한다.
각 기능의 완료일을 한꺼번에 만들 때는 [ ... for i in range(n) ]처럼 리스트 컴프리헨션 전체를 대괄호로 감싼다. 대괄호가 없으면 여러 값을 담은 리스트가 만들어지지 않는다.
import math
def solution(progresses, speeds):
answer = []
n = len(progresses)
days_left = [math.ceil((100 - progresses[i]) / speeds) for i in range(n)]
count = 0
max_day = days_left[0]
for i in range(n):
if days_left[i] <= max_day:
count += 1
else:
answer.append(count)
count = 1
max_day = days_left[i]
answer.append(count)
return answer전체 흐름은 맞았다. 다만 speeds는 리스트 전체이므로 나눗셈에 그대로 쓸 수 없다. 현재 기능 i의 속도를 꺼내는 speeds[i]가 필요하다. 즉, (100 - progresses[i]) / speeds[i]로 써야 한다.
math.ceil()은 올림이다. 예를 들어 남은 진도가 5이고 하루 속도가 4라면 계산값은 1.25일이다. 하루 끝에만 배포할 수 있으므로 1일이 아니라 2일이 필요하며, 이때 ceil이 2를 만든다.
기본 풀이: 남은 일수와 max_day로 배포 그룹 만들기
import math
def solution(progresses, speeds):
days_left = [
math.ceil((100 - progresses[i]) / speeds[i])
for i in range(len(progresses))
]
answer = []
count = 0
max_day = days_left[0]
for day in days_left:
if day <= max_day:
count += 1
else:
answer.append(count)
count = 1
max_day = day
answer.append(count)
return answerdays_left에는 각 기능이 혼자라면 완료되는 데 걸릴 일수가 들어간다. max_day는 현재 배포 그룹을 막고 있는 앞 기능의 완료일이다. 처음 그룹에서는 첫 기능이 앞을 막고 있으므로 days_left[0]이 기준이 된다.
현재 기능의 day가 max_day보다 작거나 같으면, 앞 기능이 배포되는 날까지 이미 완료되어 있으므로 같은 그룹에 들어간다. day가 더 크면 현재 그룹에 들어갈 수 없으므로 지금까지 센 count를 answer에 넣고, 현재 기능으로 새 그룹을 시작한다. 반복문이 끝난 뒤 마지막 그룹은 아직 answer에 넣지 않았으므로 answer.append(count)가 한 번 더 필요하다.
왜 max_day는 처음에 days_left[0]인가
첫 번째 기능보다 뒤에 있는 기능은 아무리 빨리 끝나도 첫 번째 기능이 배포되기 전에는 나갈 수 없다. 따라서 첫 번째 기능의 완료일이 첫 그룹의 배포일을 결정한다. 이것이 max_day = days_left[0]의 의미다.
남은 일수가 [1, 3, 2]라면 첫 기능의 기준일은 1이다. 첫 1은 첫 그룹에 들어가지만, 다음 3은 1일째에 함께 배포할 수 없다. 그래서 첫 그룹은 1개다. 이후 3이 새 기준일이 되고, 뒤의 2는 3일째까지 기다렸다가 함께 배포되므로 반환값은 [1, 2]다. 남은 일수 배열과 반환값 배열은 같은 것이 아니라는 점을 구분해야 한다.
PDF 예시: progresses [95, 90, 99, 99, 80, 99]
모든 speeds가 1이라면 남은 일수는 [5, 10, 1, 1, 20, 1]이다.
| 현재 day | 기준 max_day | 처리 | 결과 상태 |
|---|---|---|---|
| 5 | 5 | 첫 그룹에 포함 | count = 1 |
| 10 | 5 | 더 늦게 끝남, 첫 그룹 종료 | answer = [1], 새 기준 10 |
| 1, 1 | 10 | 10일째까지 기다렸다가 함께 배포 | count = 3 |
| 20 | 10 | 더 늦게 끝남, 두 번째 그룹 종료 | answer = [1, 3], 새 기준 20 |
| 1 | 20 | 20일째까지 기다렸다가 함께 배포 | 마지막 그룹 2개 추가 |
따라서 최종 반환값은 [1, 3, 2]다. 5일째 1개, 10일째 3개, 20일째 2개가 배포된다.
큐 관점의 deque 풀이
from collections import deque
import math
def solution(progresses, speeds):
days_left = deque(
math.ceil((100 - progress) / speed)
for progress, speed in zip(progresses, speeds)
)
answer = []
while days_left:
release_day = days_left.popleft()
count = 1
while days_left and days_left[0] <= release_day:
days_left.popleft()
count += 1
answer.append(count)
return answer이 풀이는 맨 앞 기능의 완료일을 release_day로 꺼낸 뒤, 그 날짜까지 완료되는 뒤 기능을 큐 앞에서 연속으로 꺼낸다. days_left[0]은 아직 배포하지 않은 기능 중 가장 앞 기능이고, 이 값이 release_day보다 작거나 같을 때만 같은 그룹에 넣을 수 있다.
zip(progresses, speeds)는 같은 위치의 진행도와 속도를 한 쌍씩 꺼낸다. 인덱스 i를 직접 쓰지 않는 버전이라 speeds[i]를 빼먹는 실수를 줄일 수 있다.
4. 문제 17 - 카드 뭉치
cards1과 cards2의 맨 앞 카드만 사용할 수 있다. 한 카드를 사용하면 그 카드 뭉치의 다음 카드가 맨 앞으로 오며, 중간 카드를 건너뛰거나 카드 순서를 바꿀 수 없다. goal의 단어를 앞에서부터 하나씩 만들 수 있으면 Yes, 만들 수 없으면 No를 반환한다.
PDF에서 처음 잡은 아이디어: 인덱스 두 개
처음에는 cards1을 어디까지 사용했는지 기록하는 idx1, cards2를 어디까지 사용했는지 기록하는 idx2를 두는 방식으로 접근했다. 카드를 실제로 삭제하지 않고 ‘다음에 볼 위치’만 하나씩 옮기는 방식이다.
Def solution(cards1, cards2, goal):
idx1 = 0
idx2 = 0
for word in goal:
if word == cards1[idx1]:
idx1 += 1
elif word == cards2[idx2]:
idx2 += 1
return "Yes"
else:
return "No"이 코드에는 PDF에서 질문했던 오류가 여러 개 있다. 함수 선언은 대문자 Def가 아니라 소문자 def다. 그리고 return "Yes"가 반복문 안에 있으면 첫 단어만 확인한 뒤 바로 함수가 끝난다. goal 전체를 다 확인한 뒤에만 Yes를 반환해야 한다.
또 cards1이나 cards2를 모두 사용한 뒤에도 cards1[idx1] 또는 cards2[idx2]에 접근하면 IndexError가 난다. 인덱스가 범위 안인지 먼저 확인한 뒤에만 카드를 비교해야 한다.
왜 idx가 카드 개수를 넘을 수 있는가
예를 들어 cards1 = ["a"], goal = ["a", "b"]라고 하자. 첫 번째 a가 맞으면 idx1은 1이 된다. 하지만 cards1의 길이는 1이고 유효한 인덱스는 0뿐이다. 다음 b를 검사할 때 cards1[1]을 읽으려 하면 존재하지 않는 위치라 IndexError가 난다.
따라서 ‘카드가 남아 있는지’를 먼저 검사해야 한다. idx1 < len(cards1)일 때만 cards1[idx1]을 읽을 수 있다. 이때 부등호는 <=가 아니라 <다. 길이가 1인 리스트의 마지막 유효 인덱스는 1이 아니라 0이기 때문이다.
and 조건에서 범위 검사를 앞에 써야 하는 이유
# 잘못된 순서: 왼쪽에서 먼저 cards1[idx1]을 읽으므로 위험함
if word == cards1[idx1] and idx1 < len(cards1):
...
# 올바른 순서: 범위가 안전할 때만 오른쪽 비교를 실행함
if idx1 < len(cards1) and word == cards1[idx1]:
...파이썬의 and는 왼쪽부터 검사한다. 왼쪽 조건이 False면 오른쪽은 실행하지 않는다. 이것을 단락 평가라고 한다. 따라서 범위 검사 조건을 왼쪽에 써야, idx1이 이미 끝에 도달한 경우 오른쪽의 cards1[idx1] 접근을 막을 수 있다.
기본 수정 풀이: 인덱스로 다음 카드 위치만 이동
def solution(cards1, cards2, goal):
idx1 = 0
idx2 = 0
for word in goal:
if idx1 < len(cards1) and word == cards1[idx1]:
idx1 += 1
elif idx2 < len(cards2) and word == cards2[idx2]:
idx2 += 1
else:
return "No"
return "Yes"goal의 단어 하나를 처리할 때, 먼저 cards1의 아직 사용하지 않은 맨 앞 카드가 같은지 본다. 맞으면 idx1을 늘려 그 카드를 사용한 것으로 표시한다. 아니라면 cards2도 같은 방식으로 확인한다. 두 뭉치 어느 쪽의 맨 앞에도 현재 word가 없다면 규칙상 더 진행할 수 없으므로 즉시 No를 반환한다.
반복문이 break나 return 없이 끝까지 실행됐다면 goal의 모든 단어를 순서대로 만들었다는 뜻이다. 그래서 idx1 + idx2 == len(goal)을 마지막에 따로 비교하지 않아도 return "Yes"만으로 충분하다.
큐 관점의 deque 풀이: 실제로 맨 앞 카드를 꺼내기
from collections import deque
def solution(cards1, cards2, goal):
cards1 = deque(cards1)
cards2 = deque(cards2)
goal = deque(goal)
while goal:
if cards1 and cards1[0] == goal[0]:
cards1.popleft()
goal.popleft()
elif cards2 and cards2[0] == goal[0]:
cards2.popleft()
goal.popleft()
else:
return "No"
return "Yes"이 버전은 PDF에서 요청했던 deque 풀이이다. cards1, cards2, goal을 모두 큐로 바꾸고, goal의 맨 앞 단어를 만들 수 있을 때 해당 카드와 goal을 동시에 popleft()한다. cards1 and ...은 cards1이 비어 있지 않을 때만 cards1[0]을 읽도록 하는 안전장치다.
카드를 실제로 앞에서 제거한다는 문제 상황을 그대로 코드에 표현하고 싶다면 deque 풀이가 직관적이다. 반대로 원본 리스트를 바꾸지 않고 다음 위치만 기록하고 싶다면 인덱스 풀이가 간결하다. 이 문제의 입력 크기에서는 둘 다 충분하지만, 일반 리스트에서 pop(0)으로 앞 카드를 제거하는 방식은 O(N)이므로 큐 구현으로는 피하는 편이 좋다.
검산
| cards1 | cards2 | goal | 결과 |
|---|---|---|---|
| ["i", "drink", "water"] | ["want", "to"] | ["i", "want", "to", "drink", "water"] | "Yes" |
| ["i", "water", "drink"] | ["want", "to"] | ["i", "want", "to", "drink", "water"] | "No" |
두 번째 예시는 cards1에서 i를 사용한 뒤 cards2의 want, to까지는 만들 수 있다. 하지만 cards1의 다음 카드는 water라서, goal이 요구하는 drink를 먼저 꺼낼 수 없다. 카드를 건너뛸 수 없으므로 No다.
5. 큐 단원 실수 방지 체크
큐의 앞에서 반복해서 꺼내야 하면 리스트의 pop(0) 대신 deque.popleft()를 쓴다.
빈 큐에서 queue[0]이나 popleft()를 하지 않도록 먼저 if queue:를 확인한다.
기능 개발에서는 속도 리스트 전체가 아니라 현재 기능의 speeds[i]를 사용한다.
기능 개발의 마지막 배포 그룹은 반복문 밖에서 answer에 한 번 더 추가한다.
카드 뭉치 인덱스 풀이는 idx < len(cards)을 먼저 검사한 뒤 cards[idx]를 비교한다.
goal 전체를 확인하기 전에는 Yes를 반환하지 않는다. 중간에 만들 수 없는 단어를 만나면 즉시 No, 반복문이 끝난 뒤 Yes를 반환한다.
6. 마무리
큐는 앞에서 꺼내고 뒤에 넣는 순서가 문제의 규칙과 맞을 때 가장 읽기 쉬운 풀이가 된다. 요세푸스 문제에서는 사람을 앞에서 꺼내 뒤로 보내며 순환을 만들고, 기능 개발에서는 앞 기능이 배포를 막는 순서를 따라 그룹을 만들며, 카드 뭉치에서는 맨 앞 카드만 사용할 수 있다는 규칙을 그대로 표현한다.