단조 스택: 증가형과 감소형
증가형 또는 감소형 스택을 유지해 O(n) 시간에 다음으로 큰 원소와 이전으로 작은 원소 질의를 효율적으로 처리합니다.
단조 스택: 증가형과 감소형은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
단조 스택이란 무엇인가요
단조 스택은 원소를 정렬된 순서로 유지하는 스택입니다(아래에서 위로 항상 증가하거나 항상 감소). 새 원소를 넣기 전에 단조 불변식을 위반하는 모든 원소를 꺼냅니다. 이렇게 제약된 구조를 사용하면 그렇지 않을 경우 O(n²) 중첩 반복문이 필요한 문제를 O(n)에 해결할 수 있습니다.
핵심 통찰은 원소가 각각 최대 한 번씩 들어가고 나오므로 전체 배열 순회에서 연산 횟수의 총합이 O(n)이라는 것입니다. O(n²)이 아닙니다. 원소를 꺼내는 순간, 해당 원소가 기다리던 답을 찾은 것입니다.
# Monotonic increasing stack (bottom to top: smallest to largest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] > val:
stack.pop() # maintain increasing invariant
stack.append(val)
print('Increasing stack (left-to-right):', stack) # [1, 1, 2, 6]
# Monotonic decreasing stack (bottom to top: largest to smallest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] < val:
stack.pop() # maintain decreasing invariant
stack.append(val)
print('Decreasing stack (left-to-right):', stack) # [9, 6]다음으로 큰 원소 I
다음으로 큰 원소 문제는 각 원소에 대해 오른쪽에서 처음으로 자신보다 큰 원소를 찾는 문제입니다. 무차별 대입 방식의 O(n²) 이중 반복문은 너무 느립니다. 단조 감소 스택을 사용하면 O(n)에 해결할 수 있습니다.
원소를 왼쪽에서 오른쪽으로 처리합니다. 원소 i를 넣기 전에 스택에서 nums[i]보다 작은 모든 원소를 꺼냅니다. nums[i]가 그 원소들 모두의 다음으로 큰 원소이기 때문입니다. 모든 원소를 처리한 후에도 스택에 남아 있는 항목은 오른쪽에 자신보다 큰 원소가 없는 것입니다(답 = -1).
def next_greater_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # stores indices; stack values are decreasing
for i in range(n):
# Pop elements smaller than nums[i]
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i] # nums[i] is next greater for idx
stack.append(i)
# Remaining elements in stack have no next greater => keep -1
return result
nums = [2, 1, 2, 4, 3]
print(next_greater_element(nums)) # [4, 2, 4, -1, -1]
nums2 = [1, 3, 2, 4]
print(next_greater_element(nums2)) # [3, 4, 4, -1]다음 큰 원소: 알고리즘 추적
[2, 1, 2, 4, 3]을 단계별로 추적해 보겠습니다. 아직 다음 큰 원소를 찾지 못한 인덱스들을 저장하는 감소 스택을 유지합니다.
- i=0, val=2: 스택이 비어 있으므로 0을 넣습니다. 스택: [0]
- i=1, val=1: 1 < nums[0]=2이므로 1을 넣습니다. 스택: [0,1]
- i=2, val=2: 1을 꺼냅니다(nums[1]=1 < 2). result[1]=2로 설정합니다. 이제 nums[0]=2는 2보다 작지 않으므로 2를 넣습니다. 스택: [0,2]
- i=3, val=4: 2를 꺼냅니다(result[2]=4). 0도 꺼냅니다(result[0]=4). 그런 다음 3을 넣습니다. 스택: [3]
- i=4, val=3: 3 < nums[3]=4이므로 4를 넣습니다. 스택: [3,4]
- 끝: 스택의 [3,4]는 result=-1입니다
def next_greater_trace(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(n):
print(f'i={i} val={nums[i]}: stack={[nums[s] for s in stack]}', end=' => ')
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
print(f'pop {nums[idx]}, NGE={nums[i]};', end=' ')
stack.append(i)
print(f'push {nums[i]}, stack={[nums[s] for s in stack]}')
print('Result:', result)
return result
next_greater_trace([2, 1, 2, 4, 3])이전 작은 원소
단조 스택은 이전 작은 원소(PSE) 질의에도 답할 수 있습니다. 즉, 각 원소에 대해 왼쪽에서 가장 가까이 있는 더 작은 원소를 찾습니다. 더 큰 원소를 만났을 때 꺼내는 대신, 더 크거나 같은 원소를 꺼내고 스택의 맨 위 원소를 PSE로 기록한 다음 현재 원소를 넣습니다.
처리 방향이 달라집니다. 여전히 왼쪽에서 오른쪽으로 처리하지만, 원소를 꺼낼 때 질의에 답하는 대신 넣기 직전에 답을 구합니다. 그 순간 스택의 맨 위 원소가 왼쪽에서 가장 가까운 작은 원소입니다. 스택이 비어 있다면 왼쪽에 더 작은 원소가 없는 것이므로 답은 -1 또는 특별한 표식값입니다.
def previous_smaller_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # monotonic increasing (values increase bottom to top)
for i in range(n):
# Pop elements >= current (maintain strictly increasing invariant)
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
# Top of stack is previous smaller element (if exists)
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
nums = [4, 5, 2, 10, 8]
print('PSE:', previous_smaller_element(nums)) # [-1, 4, -1, 2, 2]
nums2 = [1, 3, 2, 5, 4]
print('PSE:', previous_smaller_element(nums2)) # [-1, 1, 1, 2, 2]일일 온도: 더 따뜻한 날을 기다리기
일일 온도 문제(LeetCode 739)는 매일의 온도가 주어졌을 때, 각 원소가 더 따뜻한 온도가 나올 때까지 기다려야 하는 일수인 배열을 반환하는 문제입니다. 이는 다음 큰 원소 패턴과 정확히 같지만, 더 큰 값을 원하는 대신 일수(인덱스 차이)를 구합니다.
인덱스를 저장하는 단조 감소 스택을 사용합니다. 인덱스 i에서 더 따뜻한 온도를 찾으면, temps[j] < temps[i]를 만족하는 모든 인덱스 j를 스택에서 꺼내고 result[j] = i - j로 설정합니다. 스택에 남은 인덱스에는 앞으로 더 따뜻한 날이 없으므로 결과는 0입니다.
def daily_temperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices of unresolved days
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
j = stack.pop()
result[j] = i - j # days until warmer
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps)) # [1, 1, 4, 2, 1, 1, 0, 0]
temps2 = [30, 40, 50, 60]
print(daily_temperatures(temps2)) # [1, 1, 1, 0] (always warmer next day)
temps3 = [30, 60, 90]
print(daily_temperatures(temps3)) # [1, 1, 0]증가 스택과 감소 스택: 각각 언제 사용할까
올바른 스택 방향을 선택하는 것이 중요합니다.
- 단조 감소 스택(현재 원소가 맨 위 원소보다 크면 꺼냄): 다음 큰 원소와 이전 큰 원소 질의에 답합니다. 일일 온도, 최대 직사각형, 빗물 가두기 문제에 사용됩니다.
- 단조 증가 스택(현재 원소가 맨 위 원소보다 작으면 꺼냄): 다음 작은 원소와 이전 작은 원소 질의에 답합니다. 주가의 연속 범위를 구하거나 대기열에서 볼 수 있는 사람 수를 구하는 문제에 사용됩니다.
기억할 점은, 원소를 꺼내게 만든 원소가 꺼낸 원소의 질의에 대한 답이라는 것입니다. 유지하는 불변식에 따라 그 답은 다음 큰 원소일 수도 있고 다음 작은 원소일 수도 있습니다.
# Summary: which stack type for which query?
queries = {
'Next Greater Element': 'Decreasing stack (pop when new > top)',
'Next Smaller Element': 'Increasing stack (pop when new < top)',
'Previous Greater Element': 'Decreasing stack (answer = top before push)',
'Previous Smaller Element': 'Increasing stack (answer = top before push)',
}
for query, approach in queries.items():
print(f'{query}:\n => {approach}\n')
# Mnemonic:
# NGE/PGE => decreasing stack (we pop smaller elements, finding their next/prev larger)
# NSE/PSE => increasing stack (we pop larger elements, finding their next/prev smaller)원형 배열의 다음 큰 원소
다음 큰 원소 II(LeetCode 503)는 원형 배열(끝에서 처음으로 이어지는 배열)이 주어졌을 때 다음 큰 원소를 찾는 문제입니다. 핵심 방법은 인덱스를 두 배로 늘려 배열을 두 번 처리하는 것입니다. 0부터 2n-1까지 순회하면서 index % n을 사용해 배열을 순환합니다. 인덱스는 0부터 n-1까지인 경우에만(첫 번째 순회에서만) 넣어 중복으로 세지 않도록 합니다.
또는 두 번째 순회에서는 새로운 인덱스를 넣지 않고 꺼내기만 하도록 배열을 처리할 수도 있습니다. 이렇게 하면 배열을 실제로 복제하지 않고도 원형 배열의 앞쪽을 올바르게 살펴볼 수 있으며, 공간 복잡도는 O(n)으로 유지됩니다.
def next_greater_element_circular(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
idx = stack.pop()
result[idx] = nums[i % n]
if i < n:
stack.append(i) # only push real indices (0..n-1)
return result
print(next_greater_element_circular([1, 2, 1])) # [2, -1, 2]
print(next_greater_element_circular([1, 2, 3, 4, 3])) # [2, 3, 4, -1, 4]
print(next_greater_element_circular([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]주식 범위 문제
주식 범위 문제는 매일의 주가가 주어졌을 때 각 날짜의 범위를 계산하는 문제입니다. 여기서 범위란 오늘의 주가보다 작거나 같은 주가가 연속해서 나타난 직전 날짜의 수입니다. 이는 다른 모습으로 표현한 이전 큰 원소 문제입니다. 범위는 오늘부터 엄격하게 더 높은 주가를 가진 가장 가까운 날짜까지의 거리입니다.
단조 감소 스택을 사용합니다. i번째 날짜를 처리할 때 현재 주가보다 작거나 같은 주가를 가진 모든 날짜를 꺼냅니다. 스택이 비어 있지 않으면 범위는 i - stack[-1]이고, 비어 있으면 주가가 지금까지의 최댓값이므로 i + 1입니다. 그런 다음 i를 넣습니다.
def stock_span(prices):
spans = []
stack = [] # indices of prices forming decreasing sequence
for i, price in enumerate(prices):
while stack and prices[stack[-1]] <= price:
stack.pop()
span = i - stack[-1] if stack else i + 1
spans.append(span)
stack.append(i)
return spans
prices = [100, 80, 60, 70, 60, 75, 85]
print('Prices:', prices)
print('Spans: ', stock_span(prices)) # [1, 1, 1, 2, 1, 4, 6]
# Verification for day 5 (price=75): prev higher is day 1 (80), span = 5-1 = 4
# Day 6 (price=85): prev higher is day 0 (100), span = 6-0 = 6대기열에서 볼 수 있는 사람을 위한 단조 스택
대기열에서 볼 수 있는 사람의 수 문제에서는 사람들이 대기열에 서 있고 각 사람에게 키가 있습니다. 사람 i는 사람 j(j > i)를 볼 수 있는데, 두 사람 사이에 있는 모든 사람의 키가 두 사람보다 작아야 합니다. 이 문제에는 단조 감소 스택을 사용합니다.
오른쪽에서 왼쪽으로 처리합니다. 키를 저장하는 감소 스택을 유지합니다. 각 사람에 대해 볼 수 있는 사람의 수를 계산할 때, 키가 더 작은 사람을 모두 꺼냅니다(볼 수 있지만 그 뒤의 사람을 가립니다). 그 후 스택이 비어 있지 않다면 1을 더합니다. 스택에 남은 첫 번째 더 큰 사람도 볼 수 있기 때문입니다. 각 사람이 최대 한 번 들어가고 한 번 나오므로 전체 시간 복잡도는 O(n)입니다.
def visible_people(heights):
n = len(heights)
result = [0] * n
stack = [] # decreasing monotonic stack (heights)
for i in range(n - 1, -1, -1): # right to left
count = 0
while stack and stack[-1] < heights[i]:
stack.pop()
count += 1 # can see this shorter person
if stack:
count += 1 # can see the first person >= heights[i]
result[i] = count
stack.append(heights[i])
return result
heights = [10, 6, 8, 5, 11, 9]
print('Heights:', heights)
print('Visible:', visible_people(heights)) # [3, 1, 2, 1, 1, 0]O(n) 보장: 모든 원소가 최대 한 번씩 들어가고 나오는 이유
단조 스택 알고리즘의 O(n) 시간 보장은 간단한 상각 분석에서 나옵니다. 각 원소는 스택에 정확히 한 번 들어가고 최대 한 번 나옵니다. 어떤 원소도 두 번 이상 들어가거나 나올 수 없습니다. 따라서 전체 반복문에서 들어가기와 나오기 연산을 합한 횟수는 최대 2n이며, 중첩된 while문이 O(n²)을 암시하는 것처럼 보여도 전체 작업량은 O(n)입니다.
이 상각 분석은 면접에서 설명할 때 중요합니다. while문은 각 반복마다 n번 실행되는 것이 아닙니다. 기다리고 있던 원소를 꺼내는 데 필요한 만큼만 실행되며, 한 번 꺼낸 원소는 그 뒤에 영원히 사라집니다.
def next_greater_instrumented(nums):
result = [-1] * len(nums)
stack = []
pushes = pops = 0
for i in range(len(nums)):
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
pops += 1
stack.append(i)
pushes += 1
print(f'n={len(nums)}, pushes={pushes}, pops={pops}')
print(f'Total operations = {pushes + pops} <= 2n = {2*len(nums)}')
return result
import random
nums = random.sample(range(1000), 100)
next_greater_instrumented(nums)
# Confirm: total operations always <= 2n단조 스택 문제 알아보기
가장 가까운 큰 원소 또는 작은 원소, 주가의 범위, 한 줄에서 볼 수 있는 원소, 히스토그램 기반 넓이를 묻는 문제라면 단조 스택이 필요할 가능성이 높습니다. 다음과 같은 핵심어와 패턴을 찾아보세요. 각 원소가 한 방향(왼쪽 또는 오른쪽)에 있는 가장 가까운 관련 원소로부터 답을 찾아야 하는 경우입니다.
완전 탐색 해법이 각 원소에서 왼쪽이나 오른쪽으로 훑는 경우(O(n²)), 그 탐색을 단조 스택으로 바꿉니다. 스택은 답이 될 후보를 ‘기억’하고, 관련 없는 후보를 버리며, 답이 필요한 정확한 순간에 올바른 원소를 꺼냅니다.
# Monotonic stack problem recognition guide
patterns = [
('Next/previous greater element', 'Decreasing stack; answer found on pop'),
('Next/previous smaller element', 'Increasing stack; answer found on pop'),
('Days until warmer/colder', 'Stack of indices; answer = i - j'),
('Stock span', 'Decreasing stack; span = i - prev larger idx'),
('Largest rectangle in histogram', 'Increasing stack; area computed on pop'),
('Trapping rain water', 'Decreasing stack or two-pointer'),
('Sliding window maximum', 'Decreasing deque of indices'),
]
print('Monotonic Stack / Deque Pattern Guide:')
print('='*60)
for problem, approach in patterns:
print(f'Problem: {problem}')
print(f' Approach: {approach}')
print()빠른 확인
이 단원에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념을 이해했는지 확인해 보세요.
단원 요약
이 단원에서는 다음을 배웠습니다. 단조 스택은 불변식을 위반하는 원소를 넣기 전에 꺼내면서 증가 또는 감소 순서를 유지합니다. 감소 스택은 다음 또는 이전 큰 원소를 찾고, 증가 스택은 다음 또는 이전 작은 원소를 찾습니다. 또한 각 원소가 최대 한 번씩 들어가고 나오므로 전체 시간은 O(n)이며 O(n²)이 아닙니다. 다음으로 단조 스택을 사용해 히스토그램에서 가장 큰 직사각형을 찾아보겠습니다.
자주 묻는 질문
“단조 스택: 증가형과 감소형” 강의는 무료인가요?
네 — “단조 스택: 증가형과 감소형” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“단조 스택: 증가형과 감소형”에서 뭘 배우나요?
증가형 또는 감소형 스택을 유지해 O(n) 시간에 다음으로 큰 원소와 이전으로 작은 원소 질의를 효율적으로 처리합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“단조 스택: 증가형과 감소형” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 단조 스택: 증가형과 감소형
- 히스토그램에서 가장 큰 직사각형
- 단조 덱을 사용한 슬라이딩 윈도우 최댓값
- 빗물 받기: 스택과 투 포인터