Ch.4 스택과 큐
챕터 4 종합 퀴즈
챕터 4를 마무리하며 실력을 점검해봅시다
스택의 LIFO, 큐의 FIFO, 덱의 양방향 연산, 힙의 우선순위 — 이 모든 개념을 종합적으로 확인합니다.
비슷해 보이는 자료구조들, 언제 어떤 것을 써야 할까?
상황에 맞는 자료구조 선택이 면접의 핵심입니다. 퀴즈로 점검해봅시다.
핵심 내용
LIFO 방식의 자료구조는?
큐에서 원소를 넣는 연산은 enqueue, 빼는 연산은?
큐에서 빼기 = ___
Python list.pop(0)의 시간복잡도는?
heapq.heapify()의 시간복잡도는?
Monotonic Stack으로 Daily Temperatures를 풀면 시간복잡도는 O(n log n)이다
다음 코드의 출력은? stack = [1,2,3] stack.pop() stack.append(4) print(stack)
다음 코드의 출력은? from collections import deque d = deque([1,2,3]) d.appendleft(0) d.pop() print(d)
괄호 검증 문제에 가장 적합한 자료구조는?
K번째로 큰 원소를 찾는 데 가장 효율적인 자료구조는?
Sliding Window Maximum에서 deque가 필요한 이유는?
스택의 push, pop, peek은 모두 O(1)이다
Python heapq는 Max Heap을 기본 지원한다
Min Stack의 공간복잡도는 O(1)이다
스택은 ___IO 방식이고 큐는 ___IO 방식이다
스택 = ___IO
Kth Largest를 힙으로 풀 때 크기 ___의 Min Heap을 유지한다
Min Heap 크기 = ___
스택 & 큐 챕터 정복!
정리 노트
챕터 4 종합 — 스택 & 큐
자료구조 비교
- 스택
- LIFO / push, pop O(1) / list 사용
- 큐
- FIFO / enqueue, dequeue O(1) / deque 사용
- 덱
- 양방향 / 양쪽 O(1) / deque 사용
- 힙
- 우선순위 / push, pop O(log n) / heapq 사용
면접 필수 패턴
- 괄호 검증
- 스택 — 열린 괄호 push, 닫힌 괄호 pop 후 비교
- Monotonic Stack
- 다음 큰 수 / Daily Temperatures
- Min Stack
- 보조 스택으로 O(1) 최솟값 조회
- Sliding Window
- Monotonic Deque로 O(n) 최댓값
- Kth Largest
- 크기 k의 Min Heap → O(n log k)
면접에서 자료구조 선택 이유를 '시간복잡도'로 설명하는 습관을 들이세요!
핵심 정리
- 1스택(LIFO), 큐(FIFO), 덱, 힙 — 4대 자료구조
- 2Monotonic Stack/Deque로 O(n) 문제 풀이
- 3Min Stack, Kth Largest 등 면접 핵심 패턴
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작