통합 요약노트
Ch.4 스택과 큐
LIFO와 FIFO — 괄호 검증, Monotonic Stack, 우선순위 큐
이 챕터의 내용
스택 — 접시 쌓기 (LIFO)
함수 호출, Undo 기능, 괄호 검증 — 모두 스택 덕분에 작동합니다.
접시를 쌓아 올리면 맨 위 접시를 먼저 꺼내게 됩니다
LIFO = Last In, First Out 마지막에 들어간 것이 가장 먼저 나옵니다
스택의 핵심 연산은 두 가지뿐입니다 push(넣기)와 pop(빼기)
- 스택 = LIFO (후입선출) 자료구조
- 핵심 연산: push, pop, peek 모두 O(1)
- Python list의 append/pop으로 간단히 구현
괄호 검증 — 스택의 킬러 앱
스택에 열린 괄호를 넣고, 닫힌 괄호가 오면 꺼내서 비교 — 이것이 핵심 패턴입니다.
"( )" "{ }" "[ ]" 세 종류의 괄호가 올바르게 짝을 이루는지 확인하세요
핵심 규칙: 가장 최근에 열린 괄호가 가장 먼저 닫혀야 합니다 — LIFO!
알고리즘은 간단합니다 열린 괄호 → push, 닫힌 괄호 → pop 후 비교
- 열린 괄호 → push, 닫힌 괄호 → pop 후 비교
- 시간 O(n), 공간 O(n)
- 엣지 케이스: 빈 문자열, 여는 괄호만, 닫는 괄호 먼저
Monotonic Stack — 다음 큰 수 찾기
스택에 '아직 답을 못 찾은 원소'를 쌓아두는 것 — 이것이 Monotonic Stack의 비밀입니다.
온도 배열이 주어질 때 각 날로부터 며칠 뒤에 더 따뜻해지는지 구하세요
브루트포스는 O(n²) 각 날마다 뒤를 전부 탐색해야 합니다
Monotonic Stack = 단조 스택 스택 안의 값이 항상 정렬된 상태를 유지합니다
- Monotonic Stack = 정렬 상태를 유지하는 스택
- O(n²) 문제를 O(n)으로 변환하는 핵심 테크닉
- Daily Temperatures, Next Greater Element에 적용
큐와 덱 (FIFO)
list.pop(0)은 O(n) — collections.deque가 해답입니다.
큐(Queue) = 줄 서기 먼저 들어간 것이 먼저 나옵니다
큐의 핵심 연산 enqueue(넣기)와 dequeue(빼기)
* list.pop(0)은 O(n)! deque.popleft()는 O(1)입니다
- 큐 = FIFO, 덱 = 양방향 큐
- collections.deque로 O(1) 큐 구현
- list.pop(0)은 O(n) — 절대 큐로 쓰지 말 것!
우선순위 큐(Heap)
이진 힙(Binary Heap)은 '부모 ≤ 자식' 규칙으로 최솟값을 항상 루트에 유지합니다.
힙(Heap) = 완전 이진 트리 + 부모 ≤ 자식 (Min Heap)
Python의 heapq 모듈은 Min Heap을 제공합니다
heapq는 Min Heap만 지원 Max Heap은 부호를 뒤집어 구현합니다
- 힙 = 부모 ≤ 자식인 완전 이진 트리
- heapq: push/pop O(log n), heapify O(n)
- Max Heap은 -1 곱하기 트릭으로 구현
면접 실전: 스택/큐 핵심 문제
보조 스택, Monotonic Stack, Monotonic Deque — 세 가지 패턴이면 충분합니다.
push, pop, top에 더해 getMin()도 O(1)인 스택을 설계하세요
아이디어: 보조 스택에 각 시점의 최솟값을 함께 기록합니다
앞서 배운 Monotonic Stack 패턴의 대표 문제를 다시 정리합니다
- Min Stack — 보조 스택 패턴
- Daily Temperatures — Monotonic Stack 패턴
- Sliding Window Max — Monotonic Deque 패턴
챕터 4 종합 퀴즈
상황에 맞는 자료구조 선택이 면접의 핵심입니다. 퀴즈로 점검해봅시다.
LIFO 방식의 자료구조는?
큐에서 원소를 넣는 연산은 enqueue, 빼는 연산은?
큐에서 빼기 = ___
- 스택(LIFO), 큐(FIFO), 덱, 힙 — 4대 자료구조
- Monotonic Stack/Deque로 O(n) 문제 풀이
- Min Stack, Kth Largest 등 면접 핵심 패턴
핵심 용어 모음
스택(Stack)
후입선출(LIFO) 방식의 자료구조
LIFO
Last In, First Out — 마지막에 넣은 것이 먼저 나옴
push(x)
스택 맨 위에 x를 추가 — O(1)
pop()
스택 맨 위 요소를 제거하고 반환 — O(1)
peek/top
맨 위 요소를 제거하지 않고 확인 — O(1)
is_empty()
스택이 비었는지 확인 — O(1)
열린 괄호
stack에 push
닫힌 괄호
stack에서 pop 후 짝이 맞는지 확인
끝났을 때
stack이 비어있으면 True
빈 문자열 ""
True — 닫아야 할 것이 없음
여는 괄호만 "(("
False — stack이 남아 있음
닫는 괄호 먼저 ")"
False — stack이 비어있는데 pop 시도
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 코스 시작하기