Ch.4 스택과 큐
Monotonic Stack — 다음 큰 수 찾기
O(n²)을 O(n)으로 바꾸는 마법의 스택
배열에서 각 원소의 '다음 큰 수'를 찾는 문제를 브루트포스로 풀면 O(n²)입니다. Monotonic Stack 하나면 O(n)으로 끝납니다.
어떻게 스택만으로 '다음에 나올 더 큰 수'를 알 수 있을까?
스택에 '아직 답을 못 찾은 원소'를 쌓아두는 것 — 이것이 Monotonic Stack의 비밀입니다.
핵심 내용
온도 배열이 주어질 때 각 날로부터 며칠 뒤에 더 따뜻해지는지 구하세요
입력: [73, 74, 75, 71, 69, 72, 76, 73] 출력: [1, 1, 4, 2, 1, 1, 0, 0] 73°→ 1일 뒤 74° / 75°→ 4일 뒤 76° / 76°→ 없음(0)
브루트포스는 O(n²) 각 날마다 뒤를 전부 탐색해야 합니다
Monotonic Stack = 단조 스택 스택 안의 값이 항상 정렬된 상태를 유지합니다
핵심: 새 원소가 스택 top보다 크면 pop하면서 답을 채운다
인덱스를 스택에 쌓고 더 큰 온도를 만나면 pop하며 답을 기록합니다
def dailyTemperatures(temps):
n = len(temps)
answer = [0] * n
stack = [] # 인덱스를 저장
for i in range(n):
while stack and temps[i] > temps[stack[-1]]:
prev = stack.pop()
answer[prev] = i - prev
stack.append(i)
return answer
print(dailyTemperatures([73,74,75,71,69,72,76,73]))
# [1, 1, 4, 2, 1, 1, 0, 0]왜 O(n)인가? 각 원소는 최대 1번 push, 1번 pop → 전체 push + pop 횟수 ≤ 2n → O(n)
같은 패턴으로 Next Greater Element 문제도 풀 수 있습니다
def nextGreaterElement(nums):
result = [-1] * len(nums)
stack = []
for i in range(len(nums)):
while stack and nums[i] > nums[stack[-1]]:
idx = stack.pop()
result[idx] = nums[i]
stack.append(i)
return result
print(nextGreaterElement([2, 1, 2, 4, 3]))
# [4, 2, 4, -1, -1]Daily Temperatures는 인덱스 차이를 기록 Next Greater는 값 자체를 기록 패턴은 동일합니다!
Monotonic Stack을 사용한 Daily Temperatures의 시간복잡도는?
Monotonic Stack에서 스택에 저장하는 것은 보통 값이 아니라 ___이다
스택에 저장: ___
Monotonic Stack 정복!
핵심 용어
단조 감소 스택
위에서 아래로 감소 — Next Greater 풀이
단조 증가 스택
위에서 아래로 증가 — Next Smaller 풀이
정리 노트
Monotonic Stack — 다음 큰 수 찾기
패턴 요약
- 아이디어
- 아직 답을 못 찾은 원소의 인덱스를 스택에 보관
- pop 조건
- 새 원소가 stack top보다 클 때 pop하며 답 기록
- 시간복잡도
- O(n) — 각 원소 최대 1회 push + 1회 pop
대표 문제
- Daily Temperatures
- answer[prev] = i - prev (인덱스 차이)
- Next Greater Element
- result[idx] = nums[i] (값 자체)
면접에서 while loop 안의 pop이 전체 O(n)인 이유를 설명할 수 있어야 합니다!
시각 자료
핵심 정리
- 1Monotonic Stack = 정렬 상태를 유지하는 스택
- 2O(n²) 문제를 O(n)으로 변환하는 핵심 테크닉
- 3Daily Temperatures, Next Greater Element에 적용
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작