지난 학습 요약
- 약점 집중 연습 2회차에서 원본 보존 패턴, 순환 순회 범위 모두 정착 판정
- 주요 약점 전부 해소 → 실력 강화 기간으로 전환 결정
- 아직 안 다룬 유형: 스택/큐, 그리디, BFS/DFS, 이진 탐색, DP 등
오늘 수업 계획
COS Pro 출제 범위 중 미학습 유형인 스택과 큐를 집중 학습한다. 개념 설명 후 빈칸/디버깅/함수 작성 6문제를 풀며 핵심 패턴을 익힌다.
학습 내용 정리
1. 스택 (Stack) — LIFO
마지막에 넣은 걸 먼저 꺼내는 구조. Java에서는 Stack 클래스를 쓰지만, Python에서는 그냥 리스트로 스택을 구현한다.
| Java | Python | 설명 |
|---|---|---|
push() | append() | 넣기 |
pop() | pop() | 꺼내기 (마지막 원소) |
peek() | [-1] | 맨 위 보기 (꺼내지 않음) |
isEmpty() | not stack | 비어있는지 확인 |
2. 큐 (Queue) — FIFO
먼저 넣은 걸 먼저 꺼내는 구조. 리스트의 pop(0)은 O(n)이라 느리므로, collections.deque를 사용한다.
from collections import deque
queue = deque()
queue.append(1) # 뒤에 넣기
front = queue.popleft() # 앞에서 꺼내기 — O(1)| 연산 | 리스트 | deque |
|---|---|---|
| 뒤에 넣기 | append() — O(1) | append() — O(1) |
| 앞에서 꺼내기 | pop(0) — O(n) | popleft() — O(1) |
COS Pro 포인트: 큐 문제가 나오면 deque를 import하는 게 정석이다.
3. 빈 컨테이너 체크 — not 활용
수업 중 질문: "stack이 리스트니까
not list도 되는 거야? dict이나 튜플 같은 다른 자료구조는?"
Python의 모든 컨테이너에 동일하게 적용된다:
not [] # True (빈 리스트)
not {} # True (빈 딕셔너리)
not () # True (빈 튜플)
not set() # True (빈 집합)
not deque() # True (빈 덱)
not "" # True (빈 문자열)Java의 isEmpty()를 모든 자료구조에 통일해서 쓸 수 있는 셈. COS Pro 빈칸에서 not 변수명이 나오면 "비어있는지 확인"이라고 읽으면 된다.
# 이 둘은 같은 의미
if len(stack) == 0: # 명시적
if not stack: # Pythonic — 시험에서 자주 나오는 형태4. 괄호 매칭 — 스택의 대표 패턴
단일 괄호 검사
여는 괄호를 만나면 push, 닫는 괄호를 만나면 스택이 비어있는지 확인 후 pop.
def is_valid_parentheses(s):
stack = []
for char in s:
if char == '(':
stack.append(char)
elif char == ')':
if not stack: # 짝이 없다
return False
stack.pop()
return not stack # 남은 괄호 없으면 True다중 괄호 검사 ((), {}, [])
딕셔너리로 여는/닫는 괄호의 짝을 매핑한다:
def is_valid_brackets(s):
stack = []
brackets = {"[": "]", "(": ")", "{": "}"}
for char in s:
if char in brackets: # .keys() 생략 가능!
stack.append(char)
elif char in brackets.values():
if not stack or brackets[stack[-1]] != char:
return False
stack.pop()
return not stack딕셔너리 팁: "[" in brackets는 기본적으로 key에서 검색한다. .keys() 안 붙여도 된다.
5. 브라우저 뒤로가기 — 스택 활용
수업 중 질문: "visit과 back 개수가 같으면 '홈'으로 돌아가는 조건이 따로 필요한 거 아니야?"
"홈"도 visit할 때 스택에 들어가기 때문에 별도 조건 없이 자동으로 복귀된다.
def browser_history(actions):
history = []
current = "홈"
for action, value in actions:
if action == "visit":
history.append(current) # ← 새 페이지가 아니라 "지금 페이지"를 저장!
current = value
elif action == "back":
if history:
current = history.pop()
return current핵심 포인트: 스택에 저장하는 건 "어디로 가는지(value)"가 아니라 "어디서 왔는지(current)". 뒤로 가기니까!
6. 요세푸스 문제 — 큐로 원형 순환
N명이 원형으로 앉아있고 K번째 사람을 순서대로 제거하는 문제. 큐로 원형을 표현하는 트릭: 앞에서 빼서 뒤로 보내면 원형처럼 동작한다.
from collections import deque
def josephus(n, k):
queue = deque(range(1, n + 1)) # deque는 range를 직접 받을 수 있다
result = []
while queue:
for _ in range(k - 1): # k-1명 건너뛰기
queue.append(queue.popleft()) # 앞에서 빼서 뒤로
result.append(queue.popleft()) # k번째 사람 제거
return result7. 프린터 우선순위 — 큐 + 튜플 추적
우선순위가 높은 문서가 먼저 인쇄되는 프린터. 내 문서가 몇 번째로 인쇄되는지 구하는 문제.
수업 중 질문: "'deque mutated during iteration' 에러는 뭐야?"
deque를 for로 순회하는 도중에 내용을 변경하면 발생하는 에러. while로 바꿔서 해결한다.
from collections import deque
def print_order(priorities, target):
queue = deque((p, idx) for idx, p in enumerate(priorities))
count = 0
while queue:
p, idx = queue.popleft()
if queue and p < max(p for p, _ in queue):
queue.append((p, idx)) # 우선순위 낮으면 뒤로
else:
count += 1
if idx == target: # 내 문서면 바로 반환
return count핵심: 큐에 (우선순위, 원래 인덱스) 튜플을 넣어서 내 문서를 추적한다. 인쇄 즉시 카운터로 반환하면 불필요한 순회를 줄일 수 있다.
오늘의 결과
- 스택/큐 개념 + 6문제 풀이 (1차 정답 3문제, 최종 전부 정답)
- 핵심 패턴 정리: 괄호 매칭, 원형 순환, 우선순위 큐
- 다음 학습: 그리디 알고리즘 개념 및 문제 풀이
