이미지 로딩 중...
AI Generated
2025. 11. 7. · 4 Views
단조 스택으로 히스토그램 문제 완벽 정복
스택을 활용한 히스토그램 최대 직사각형 찾기 알고리즘을 실무 관점에서 깊이 있게 다룹니다. O(n) 시간 복잡도로 효율적으로 문제를 해결하는 단조 스택 패턴과 실전 응용법을 배웁니다.
목차
- 단조 스택의 개념과 히스토그램 문제 소개
- 단조 스택을 유지하는 핵심 로직
- 너비 계산의 정확한 이해
- 스택에 남은 요소 처리하기
- 시간 복잡도 O(n) 증명
- 실전 구현 시 주의사항
- 단조 스택의 다양한 응용 문제
- 테스트 케이스와 디버깅 전략
1. 단조 스택의 개념과 히스토그램 문제 소개
시작하며
여러분이 건물의 스카이라인을 보면서 가장 큰 직사각형 영역을 찾아야 하는 상황을 생각해보세요. 각 건물의 높이가 주어졌을 때, 인접한 건물들로 만들 수 있는 가장 큰 직사각형의 넓이를 구해야 합니다.
이것이 바로 히스토그램 최대 직사각형 문제입니다. 처음에는 모든 가능한 조합을 확인하는 브루트포스 방법을 떠올리실 겁니다.
하지만 이 방법은 O(n²) 또는 O(n³)의 시간이 걸려서, 데이터가 많아지면 실용적이지 않습니다. 실제 코딩 인터뷰나 실무에서는 더 효율적인 해법이 필요합니다.
여기서 등장하는 것이 바로 단조 스택(Monotonic Stack)입니다. 단조 스택을 사용하면 O(n) 시간에 이 문제를 해결할 수 있습니다.
스택에 저장된 요소들이 항상 특정 순서(증가 또는 감소)를 유지하도록 관리하는 것이 핵심입니다.
개요
간단히 말해서, 단조 스택은 스택 내부의 요소들이 항상 단조 증가하거나 단조 감소하는 순서를 유지하는 자료구조입니다. 히스토그램 문제에서 단조 증가 스택을 사용하는 이유는, 각 막대(bar)에 대해 "왼쪽과 오른쪽으로 어디까지 이 높이를 유지할 수 있는지"를 효율적으로 찾기 위함입니다.
예를 들어, 주식 가격 분석에서 특정 가격대가 유지되는 구간을 찾거나, 빌딩 뷰 문제에서 보이는 건물을 찾는 경우에도 동일한 패턴이 적용됩니다. 기존의 중첩 반복문 방식에서는 각 막대마다 좌우를 모두 탐색해야 했다면, 단조 스택을 사용하면 각 요소를 정확히 한 번씩만 push하고 pop하면 됩니다.
단조 스택의 핵심 특징은 세 가지입니다: (1) 요소를 추가할 때 순서를 유지하기 위해 기존 요소를 제거할 수 있고, (2) 제거되는 시점에서 중요한 정보를 계산할 수 있으며, (3) 스택에 남아있는 요소는 아직 경계를 찾지 못한 미해결 상태입니다. 이러한 특징들이 히스토그램 문제를 선형 시간에 해결할 수 있게 만듭니다.
코드 예제
def largestRectangleArea(heights):
# 단조 증가 스택: 인덱스를 저장
stack = []
max_area = 0
for i, h in enumerate(heights):
# 현재 높이가 스택 top보다 작으면
# 스택에서 요소를 꺼내며 면적 계산
while stack and heights[stack[-1]] > h:
height_index = stack.pop()
height = heights[height_index]
# 너비 계산: 현재 위치 - 스택 top - 1
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
# 스택에 남은 요소 처리
while stack:
height_index = stack.pop()
height = heights[height_index]
width = len(heights) if not stack else len(heights) - stack[-1] - 1
max_area = max(max_area, height * width)
return max_area
설명
이 알고리즘이 하는 일: 히스토그램의 각 막대를 순회하면서, 각 막대를 높이로 하는 최대 직사각형의 넓이를 계산합니다. 단조 증가 스택을 유지함으로써, 각 막대가 확장될 수 있는 왼쪽과 오른쪽 경계를 효율적으로 찾아냅니다.
첫 번째 단계로, 히스토그램을 왼쪽부터 순회하면서 각 막대의 인덱스를 스택에 추가합니다. 이때 중요한 규칙이 있습니다: 현재 막대의 높이가 스택 top에 있는 막대보다 낮다면, 스택 top의 막대는 더 이상 오른쪽으로 확장할 수 없다는 의미입니다.
왜냐하면 더 낮은 막대를 만났기 때문이죠. 이것이 바로 면적을 계산할 시점입니다.
두 번째 단계에서, 스택에서 pop된 막대의 높이로 만들 수 있는 최대 직사각형을 계산합니다. 너비는 어떻게 구할까요?
현재 위치(i)가 오른쪽 경계이고, 스택의 새로운 top(pop 후)이 왼쪽 경계입니다. 정확히는 i - stack[-1] - 1이 너비가 됩니다.
만약 스택이 비어있다면, pop된 막대가 왼쪽 끝까지 확장 가능하다는 뜻이므로 너비는 i가 됩니다. 세 번째 단계로, 모든 막대를 순회한 후에도 스택에 남아있는 막대들을 처리합니다.
이 막대들은 히스토그램의 끝까지 확장 가능한 막대들입니다. 각각에 대해 동일한 방식으로 면적을 계산하되, 오른쪽 경계는 히스토그램의 끝(len(heights))이 됩니다.
여러분이 이 알고리즘을 사용하면 O(n) 시간 복잡도로 문제를 해결할 수 있습니다. 각 요소는 정확히 한 번 push되고 한 번 pop되므로, 전체 연산은 선형 시간에 완료됩니다.
공간 복잡도도 O(n)으로 효율적이며, 실무에서 대용량 데이터를 처리할 때도 안정적으로 동작합니다. 이 패턴은 주식 차트 분석, 빌딩 실루엣 문제, 빗물 가두기 문제 등 다양한 영역에 응용할 수 있습니다.
실전 팁
💡 스택에는 높이 값이 아닌 인덱스를 저장하세요. 인덱스를 저장해야 너비 계산이 가능합니다. 높이는 필요할 때 heights[index]로 접근하면 됩니다.
💡 너비 계산 공식을 명확히 이해하세요. i - stack[-1] - 1에서 -1을 빼는 이유는 스택 top과 현재 위치 사이의 실제 거리를 구하기 위함입니다. 경계는 포함하지 않습니다.
💡 스택이 비어있을 때의 예외 처리를 잊지 마세요. 스택이 비어있다면 pop된 막대가 왼쪽 끝(0)부터 확장 가능하다는 의미입니다.
💡 마지막 while문을 빠뜨리지 마세요. 순회가 끝난 후 스택에 남은 요소들은 모두 히스토그램 끝까지 확장 가능한 막대들이므로 반드시 처리해야 합니다.
💡 디버깅 시에는 각 단계에서 스택의 상태와 계산된 면적을 출력해보세요. 어느 막대에서 최대 면적이 계산되는지 추적하면 알고리즘의 동작을 명확히 이해할 수 있습니다.
2. 단조 스택을 유지하는 핵심 로직
시작하며
여러분이 스택 기반 알고리즘을 구현할 때 가장 헷갈리는 부분은 "언제 스택에서 요소를 빼야 하는가"입니다. 일반 스택이라면 단순히 push와 pop을 순서대로 하면 되지만, 단조 스택은 특정 조건을 만족해야만 요소를 유지합니다.
단조 증가 스택의 경우, 새로운 요소가 스택 top보다 작으면 스택의 단조성이 깨집니다. 이때 어떻게 해야 할까요?
새 요소를 거부할 수는 없습니다. 모든 요소를 처리해야 하니까요.
대신 스택의 기존 요소들을 제거해서 단조성을 복구합니다. 바로 이 "제거하는 순간"이 핵심 계산을 수행하는 타이밍입니다.
pop되는 요소는 더 이상 확장할 수 없는 시점에 도달했다는 신호이며, 이때가 바로 그 요소를 중심으로 한 결과를 계산할 최적의 순간입니다.
개요
간단히 말해서, 단조 스택의 핵심은 "새 요소를 추가하기 전에 순서를 위반하는 기존 요소를 모두 제거한다"는 규칙입니다. 이 패턴이 필요한 이유는 스택의 상태가 곧 "아직 해결되지 않은 문제들의 목록"이기 때문입니다.
예를 들어, 히스토그램에서 스택에 남아있는 막대들은 "아직 오른쪽 경계를 찾지 못한 막대들"입니다. 새로 더 낮은 막대를 만나면, 스택에 있던 더 높은 막대들은 이제 오른쪽 경계를 찾은 것이므로 제거하면서 계산을 완료합니다.
전통적인 스택에서는 LIFO 순서만 지키면 됐다면, 단조 스택에서는 LIFO에 더해 단조성이라는 추가 조건을 만족해야 합니다. 단조 스택의 핵심 특징: (1) while 루프로 조건을 위반하는 모든 요소를 제거합니다, (2) 제거될 때마다 그 요소에 대한 계산을 수행합니다, (3) 제거 후에는 단조성이 복구되어 새 요소를 안전하게 추가할 수 있습니다.
이 과정이 각 요소당 최대 한 번씩만 일어나므로 전체 시간 복잡도가 O(n)으로 유지됩니다.
코드 예제
def maintainMonotonicStack(heights):
stack = [] # 단조 증가 스택
result = []
for i, current_height in enumerate(heights):
# 핵심: 단조성을 위반하는 요소를 모두 제거
while stack and heights[stack[-1]] > current_height:
# pop되는 순간이 계산 시점
popped_index = stack.pop()
popped_height = heights[popped_index]
# 이 막대의 오른쪽 경계를 찾았음
right_boundary = i
# 왼쪽 경계는 스택의 새로운 top
left_boundary = stack[-1] if stack else -1
width = right_boundary - left_boundary - 1
result.append({
'index': popped_index,
'height': popped_height,
'width': width,
'area': popped_height * width
})
# 단조성이 복구되었으므로 새 요소 추가
stack.append(i)
return result, stack
설명
이 로직이 하는 일: 새로운 막대를 처리할 때마다 스택의 단조 증가 속성을 유지하면서, 동시에 경계가 확정된 막대들의 면적을 계산합니다. 이것이 바로 단조 스택 패턴의 핵심 메커니즘입니다.
첫 번째로, for 루프에서 각 막대를 순회하며 현재 막대의 높이를 확인합니다. 이때 스택이 비어있지 않고, 스택 top의 막대 높이가 현재 막대보다 크다면 단조성이 깨진 상태입니다.
이 조건이 while 루프의 시작점이며, 이 조건을 만족하는 동안 계속 요소를 pop합니다. 왜 하나만 빼지 않고 while로 여러 개를 빼느냐면, 현재 막대보다 높은 막대가 여러 개일 수 있기 때문입니다.
두 번째로, while 루프 안에서 pop된 막대에 대한 계산을 수행합니다. 이 막대는 방금 오른쪽 경계를 찾았습니다(현재 위치 i).
왼쪽 경계는 어디일까요? pop 후 스택에 남아있는 top이 바로 왼쪽 경계입니다.
왜냐하면 그 막대보다 pop된 막대가 더 높았다는 뜻이기 때문이죠. 만약 스택이 비었다면 pop된 막대는 왼쪽 끝까지 확장 가능합니다.
이렇게 계산한 너비와 높이를 곱하면 그 막대를 높이로 하는 최대 직사각형의 넓이가 나옵니다. 세 번째로, while 루프가 끝나면 스택의 단조성이 복구된 상태입니다.
이제 현재 막대의 인덱스를 안전하게 push할 수 있습니다. 현재 막대는 스택의 모든 요소보다 높거나 같으므로 단조 증가 속성이 유지됩니다.
여러분이 이 패턴을 마스터하면 "각 요소의 이전/다음 작은(큰) 요소 찾기" 류의 모든 문제를 O(n)에 해결할 수 있습니다. Next Greater Element, 빗물 가두기(Trapping Rain Water), 주식 가격 스팬 등 다양한 문제가 이 패턴의 변형입니다.
실무에서는 시계열 데이터 분석, 이벤트 처리, 범위 쿼리 최적화 등에 응용됩니다.
실전 팁
💡 while 조건을 정확히 설정하세요. stack and heights[stack[-1]] > current_height에서 and 순서가 중요합니다. 스택이 비어있는지 먼저 확인해야 IndexError를 방지할 수 있습니다.
💡 단조 증가 vs 단조 감소를 문제에 맞게 선택하세요. "다음 큰 요소"를 찾으려면 단조 감소 스택, "다음 작은 요소"를 찾으려면 단조 증가 스택을 사용합니다.
💡 pop하면서 계산하는 패턴을 기억하세요. pop된 요소는 "경계가 확정된" 상태이므로 최종 계산을 수행하기에 완벽한 시점입니다. push할 때가 아닙니다.
💡 디버깅 시 스택의 높이 배열을 출력해보세요. [heights[i] for i in stack]를 출력하면 스택이 정말 단조 증가하는지 시각적으로 확인할 수 있습니다.
💡 등호 처리에 주의하세요. >=를 쓸지 >를 쓸지는 문제의 요구사항에 따라 다릅니다. 히스토그램 문제에서는 같은 높이도 연속된 것으로 처리해야 하므로 >를 사용합니다.
3. 너비 계산의 정확한 이해
시작하며
여러분이 히스토그램 알고리즘을 구현하다가 가장 많이 마주치는 버그는 "너비를 잘못 계산해서 면적이 틀리는 것"입니다. 특히 i - stack[-1] - 1 같은 공식을 보면서 "왜 -1을 빼지?"라고 의문을 가지신 적 있을 겁니다.
인덱스 기반 너비 계산은 off-by-one 에러가 발생하기 쉬운 부분입니다. 예를 들어, 인덱스 2에서 5 사이의 막대 개수는 몇 개일까요?
직관적으로 "5 - 2 = 3개"라고 생각하기 쉽지만, 실제로는 인덱스 2, 3, 4, 5로 4개입니다. 이런 혼동이 버그의 원인이 됩니다.
더 복잡한 것은 스택에 저장된 인덱스가 "경계"를 나타낸다는 점입니다. pop된 막대의 실제 확장 범위는 경계 사이의 공간이지, 경계 자체를 포함하지 않습니다.
이 개념을 정확히 이해해야 올바른 너비 계산이 가능합니다.
개요
간단히 말해서, 너비는 "오른쪽 경계 인덱스 - 왼쪽 경계 인덱스 - 1"로 계산되며, 여기서 경계는 pop된 막대가 확장할 수 없는 지점을 의미합니다. 왜 이렇게 계산하는지 구체적으로 이해해봅시다.
pop된 막대의 높이를 h라고 하면, 이 높이로 만들 수 있는 직사각형은 h보다 낮지 않은 연속된 막대들로만 구성됩니다. 왼쪽 경계는 "h보다 낮은 첫 번째 막대"이고, 오른쪽 경계도 마찬가지입니다.
경계 자체는 포함되지 않으므로 그 사이의 거리에서 1을 빼야 합니다. 전통적인 방법으로 너비를 구하려면 pop된 막대 위치에서 양방향으로 탐색해야 했습니다.
하지만 단조 스택을 사용하면 경계 정보가 이미 스택에 저장되어 있어서 O(1)에 계산할 수 있습니다. 너비 계산의 핵심 케이스는 세 가지입니다: (1) 양쪽에 경계가 있는 경우: right - left - 1, (2) 왼쪽 경계가 없는 경우(스택이 빔): 막대가 배열의 시작부터 확장 가능하므로 right, (3) 오른쪽 경계가 없는 경우: 막대가 배열의 끝까지 확장 가능하므로 len(heights) - left - 1.
이 세 가지를 정확히 구분해야 모든 경우를 올바르게 처리할 수 있습니다.
코드 예제
def calculateWidth(heights):
"""너비 계산의 다양한 케이스를 보여주는 예제"""
stack = []
width_examples = []
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height_idx = stack.pop()
# 케이스 1: 스택이 비어있음 (왼쪽 경계 없음)
if not stack:
width = i # 0부터 i-1까지
left_boundary = -1
# 케이스 2: 양쪽 경계 존재
else:
left_boundary = stack[-1]
width = i - left_boundary - 1
width_examples.append({
'bar_index': height_idx,
'height': heights[height_idx],
'left_boundary': left_boundary,
'right_boundary': i,
'width': width,
'calculation': f"{i} - {left_boundary} - 1 = {width}" if stack else f"{i}"
})
stack.append(i)
# 케이스 3: 스택에 남은 요소 (오른쪽 경계 없음)
n = len(heights)
while stack:
height_idx = stack.pop()
left_boundary = stack[-1] if stack else -1
width = n - left_boundary - 1 if stack else n
width_examples.append({
'bar_index': height_idx,
'height': heights[height_idx],
'left_boundary': left_boundary,
'right_boundary': n,
'width': width,
'calculation': f"{n} - {left_boundary} - 1 = {width}"
})
return width_examples
설명
너비 계산이 하는 일: pop된 막대가 자신의 높이를 유지하면서 좌우로 확장할 수 있는 최대 범위를 계산합니다. 이 범위가 바로 그 높이로 만들 수 있는 직사각형의 너비입니다.
첫 번째로, 오른쪽 경계부터 이해해봅시다. 막대가 스택에서 pop되는 이유는 현재 위치 i의 막대가 더 낮기 때문입니다.
즉, pop된 막대는 인덱스 i까지는 확장할 수 없고, i-1까지만 확장 가능합니다. 따라서 i가 오른쪽 경계(첫 번째로 확장 불가능한 위치)가 됩니다.
경계는 포함되지 않는다는 점이 중요합니다. 두 번째로, 왼쪽 경계를 봅시다.
pop 후 스택에 남아있는 top의 인덱스를 left라고 하면, left 위치의 막대는 pop된 막대보다 낮습니다(그래서 pop되지 않고 스택에 남아있었죠). 따라서 pop된 막대는 left+1부터 시작해서 확장할 수 있습니다.
left 자체는 경계이므로 포함되지 않습니다. 만약 스택이 비었다면 왼쪽에 더 낮은 막대가 없다는 뜻이므로, pop된 막대는 인덱스 0부터 확장 가능합니다.
세 번째로, 실제 너비를 계산합니다. pop된 막대는 (left+1)부터 (i-1)까지 확장 가능하므로, 막대의 개수는 (i-1) - (left+1) + 1입니다.
이를 정리하면 i - left - 1이 됩니다. 예를 들어, left=2, i=6이면 막대는 인덱스 3, 4, 5에 걸쳐 있으므로 너비는 3입니다.
계산해보면 6 - 2 - 1 = 3으로 정확합니다. 스택이 비어있는 경우에는 left=-1로 간주하면 i - (-1) - 1 = i가 되어 0부터 i-1까지의 너비를 올바르게 계산합니다.
여러분이 이 계산 방식을 정확히 이해하면 인덱스 기반 범위 계산에서 발생하는 대부분의 버그를 예방할 수 있습니다. 실무에서 슬라이딩 윈도우, 부분 배열 처리, 범위 쿼리 등을 구현할 때도 동일한 원리가 적용됩니다.
특히 "경계는 포함하지 않는다"는 개념을 명확히 하면 off-by-one 에러를 크게 줄일 수 있습니다.
실전 팁
💡 구체적인 예제로 손으로 계산해보세요. heights = [2, 1, 5, 6, 2, 3]에서 각 막대가 pop될 때 left, right, width를 직접 계산하면 공식이 명확해집니다.
💡 경계의 의미를 항상 기억하세요. 경계는 "확장할 수 없는 첫 번째 위치"이지 "마지막으로 포함되는 위치"가 아닙니다. 이 차이가 -1의 유무를 결정합니다.
💡 스택이 빈 경우를 별도로 처리하는 대신, 가상의 -1 경계를 사용하면 코드를 단순화할 수 있습니다. left = stack[-1] if stack else -1로 통일하면 이후 계산이 일관됩니다.
💡 단위 테스트를 작성할 때 극단적인 케이스를 포함하세요: 길이 1인 배열, 모두 같은 높이, 단조 증가/감소 배열 등에서 너비가 올바르게 계산되는지 확인하세요.
💡 시각화 도구를 활용하세요. 히스토그램을 그리고 각 막대의 확장 범위를 색칠해보면 너비 계산 로직이 직관적으로 이해됩니다.
4. 스택에 남은 요소 처리하기
시작하며
여러분이 히스토그램 알고리즘을 처음 구현하면서 자주 놓치는 부분이 있습니다. 바로 "모든 막대를 순회한 후에도 스택에 남아있는 요소들"입니다.
코드를 작성하고 테스트해보면 답이 항상 실제보다 작게 나오는 경우가 있는데, 대부분 이 부분을 처리하지 않아서입니다. 왜 스택에 요소가 남을까요?
단조 스택에서 요소가 pop되는 조건은 "더 낮은 막대를 만날 때"입니다. 그런데 히스토그램의 끝에 도달했을 때, 스택에 남은 막대들은 끝까지 더 낮은 막대를 만나지 못한 것들입니다.
이들도 당연히 직사각형을 만들 수 있으므로 면적을 계산해야 합니다. 특히 히스토그램이 단조 증가하는 경우(예: [1, 2, 3, 4, 5])에는 어떤 막대도 순회 중에 pop되지 않습니다.
모든 계산이 마지막 처리 단계에서 이루어지죠. 이 부분을 빠뜨리면 답이 0이 나오는 치명적인 버그가 발생합니다.
개요
간단히 말해서, 메인 루프가 끝난 후 스택에 남은 요소들은 "히스토그램의 끝까지 확장 가능한 막대들"이므로, 각각에 대해 면적을 계산해야 합니다. 이 처리가 필요한 이유는 알고리즘의 완결성 때문입니다.
메인 루프에서는 "더 낮은 막대를 만날 때" pop하면서 계산했지만, 끝까지 더 낮은 막대를 만나지 못한 막대들은 별도로 처리해야 합니다. 예를 들어, [2, 1, 5, 6, 2, 3]에서 마지막 두 막대(2, 3)는 메인 루프에서 pop되지 않고 스택에 남습니다.
기존 메인 루프에서는 현재 위치가 오른쪽 경계였다면, 스택 처리 단계에서는 히스토그램의 길이(len(heights))가 오른쪽 경계가 됩니다. 스택 처리의 핵심 특징: (1) 오른쪽 경계가 배열의 끝으로 고정됩니다, (2) 왼쪽 경계 계산은 메인 루프와 동일합니다, (3) 스택의 모든 요소를 pop할 때까지 반복합니다.
이 단계를 빠뜨리면 알고리즘이 불완전하며, 특정 입력에서 틀린 답을 반환하게 됩니다.
코드 예제
def handleRemainingStack(heights):
"""스택에 남은 요소 처리 로직을 상세히 보여주는 예제"""
stack = []
max_area = 0
results = []
# 메인 루프
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
idx = stack.pop()
height = heights[idx]
width = i if not stack else i - stack[-1] - 1
area = height * width
max_area = max(max_area, area)
results.append(f"Main loop: bar {idx}, h={height}, w={width}, area={area}")
stack.append(i)
# 중요: 스택에 남은 요소 처리
n = len(heights)
while stack:
idx = stack.pop()
height = heights[idx]
# 오른쪽 경계는 배열의 끝
# 왼쪽 경계는 여전히 스택의 top
width = n if not stack else n - stack[-1] - 1
area = height * width
max_area = max(max_area, area)
results.append(f"Final stack: bar {idx}, h={height}, w={width}, area={area}")
return max_area, results
# 테스트: 단조 증가 케이스
heights = [1, 2, 3, 4, 5]
area, steps = handleRemainingStack(heights)
# 모든 계산이 "Final stack" 단계에서 이루어짐
설명
스택 처리가 하는 일: 히스토그램 순회가 끝났지만 아직 오른쪽 경계를 찾지 못한 막대들에 대해, 배열의 끝을 오른쪽 경계로 간주하여 최종 면적을 계산합니다. 첫 번째로, 왜 스택에 요소가 남는지 이해해야 합니다.
메인 루프에서 막대가 pop되는 조건은 heights[stack[-1]] > current_height입니다. 즉, 현재 막대보다 높은 막대만 pop됩니다.
현재 막대보다 낮거나 같은 막대들은 스택에 남게 되고, 이들은 아직 "더 낮은 막대"를 만나지 못했다는 의미입니다. 히스토그램의 끝에 도달했으므로, 이제 이들의 오른쪽 경계는 배열의 끝이 됩니다.
두 번째로, 스택 처리 로직은 메인 루프와 거의 동일하지만 한 가지 차이가 있습니다. 메인 루프에서 오른쪽 경계는 현재 인덱스 i였지만, 스택 처리에서는 len(heights)가 오른쪽 경계입니다.
왼쪽 경계 계산은 동일합니다: pop 후 스택의 top이 왼쪽 경계이고, 스택이 비면 왼쪽 끝부터 확장 가능합니다. 너비 공식도 동일하게 n - stack[-1] - 1 또는 n을 사용합니다.
세 번째로, while 루프로 스택이 빌 때까지 모든 요소를 처리합니다. 스택에 남은 막대들은 단조 증가 순서로 정렬되어 있으므로(단조 스택이니까요), 위에서부터 pop하면 높은 막대부터 처리됩니다.
각 막대는 이전에 pop된 막대의 위치가 왼쪽 경계가 되므로, 올바른 너비를 계산할 수 있습니다. 여러분이 이 단계를 정확히 구현하면 모든 케이스에서 올바른 답을 얻을 수 있습니다.
특히 단조 증가/감소 배열, 모두 같은 높이의 배열 등 극단적인 케이스에서도 안정적으로 동작합니다. 실무에서는 이런 "마무리 처리" 로직이 알고리즘의 정확성을 보장하는 중요한 부분이므로, 테스트 케이스에 반드시 포함해야 합니다.
실전 팁
💡 스택 처리 로직을 메인 루프와 별도 함수로 분리하지 마세요. 거의 동일한 코드를 중복하게 되고, 수정 시 실수할 가능성이 높아집니다. 변수만 다르게 설정하세요.
💡 단조 증가 배열로 테스트하세요. [1, 2, 3, 4, 5] 같은 입력에서 메인 루프는 아무것도 계산하지 않고, 모든 계산이 스택 처리 단계에서 이루어집니다. 이 케이스가 통과하지 않으면 버그가 있는 것입니다.
💡 스택 처리 전에 스택이 비어있는지 확인할 필요는 없습니다. while 조건이 자동으로 처리해줍니다. 빈 스택이면 while이 실행되지 않습니다.
💡 디버그 출력을 추가해서 어느 단계에서 최대 면적이 계산되는지 확인하세요. 입력에 따라 메인 루프에서 계산될 수도 있고, 스택 처리에서 계산될 수도 있습니다.
💡 코드 리뷰 시 이 부분이 빠졌는지 항상 확인하세요. 히스토그램 알고리즘의 가장 흔한 구현 실수 중 하나가 바로 스택 처리를 빠뜨리는 것입니다.
5. 시간 복잡도 O(n) 증명
시작하며
여러분이 이 알고리즘을 처음 보면 "while 루프가 for 루프 안에 있는데 정말 O(n)일까?"라는 의문이 들 수 있습니다. 중첩 루프는 보통 O(n²)인데, 이 경우는 왜 다를까요?
이것이 바로 단조 스택의 핵심적인 특징입니다. 시간 복잡도를 정확히 분석하지 않으면 알고리즘 선택에서 실수할 수 있습니다.
예를 들어, 입력 크기가 10^5 정도일 때 O(n²) 알고리즘은 시간 초과가 나지만, O(n) 알고리즘은 여유있게 통과합니다. 실무에서 대용량 데이터를 처리할 때 이 차이가 결정적입니다.
단조 스택 알고리즘이 O(n)인 핵심 이유는 "각 요소가 정확히 한 번만 push되고 한 번만 pop된다"는 것입니다. 겉보기에는 중첩 루프지만, 실제로는 모든 연산의 총합이 2n을 넘지 않습니다.
이 사실을 수학적으로 증명해봅시다.
개요
간단히 말해서, 히스토그램의 각 막대는 스택에 정확히 한 번 들어가고(push) 한 번 나오므로(pop), 전체 연산 횟수는 최대 2n입니다. 따라서 시간 복잡도는 O(n)입니다.
이 분석이 중요한 이유는 알고리즘의 확장성을 보장하기 때문입니다. n이 100일 때와 1,000,000일 때 실행 시간이 선형적으로 증가한다는 것을 수학적으로 보장할 수 있습니다.
예를 들어, 실시간 주식 데이터 분석이나 대규모 로그 처리에서 이런 성능 보장은 필수적입니다. 브루트포스 방법에서는 각 막대마다 좌우로 탐색하므로 O(n²)이었다면, 단조 스택을 사용하면 스택 연산의 누적 속성 덕분에 O(n)으로 개선됩니다.
시간 복잡도 분석의 핵심 포인트: (1) 각 요소의 push는 정확히 한 번입니다 - for 루프에서 각 i마다 한 번씩, (2) 각 요소의 pop도 최대 한 번입니다 - while 루프에서 pop되면 그 요소는 스택에서 영구히 제거됩니다, (3) 따라서 push 총 n번 + pop 최대 n번 = 총 2n번의 스택 연산입니다. 이것이 빅오 표기법으로 O(n)이 되는 이유입니다.
코드 예제
def analyzeComplexity(heights):
"""시간 복잡도를 추적하는 버전"""
stack = []
max_area = 0
# 연산 카운터
push_count = 0
pop_count = 0
comparison_count = 0
# 메인 루프: n회 반복
for i, h in enumerate(heights):
# while 조건 체크
comparison_count += 1
# while 루프: 총 n번을 초과할 수 없음
while stack and heights[stack[-1]] > h:
comparison_count += 1
# pop 연산: 각 요소당 최대 1회
idx = stack.pop()
pop_count += 1
height = heights[idx]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
# push 연산: 각 요소당 정확히 1회
stack.append(i)
push_count += 1
# 스택 처리: 최대 n회
n = len(heights)
while stack:
idx = stack.pop()
pop_count += 1
height = heights[idx]
width = n if not stack else n - stack[-1] - 1
max_area = max(max_area, height * width)
return max_area, {
'input_size': len(heights),
'push_operations': push_count,
'pop_operations': pop_count,
'comparison_count': comparison_count,
'total_operations': push_count + pop_count + comparison_count,
'ratio': (push_count + pop_count + comparison_count) / len(heights)
}
설명
시간 복잡도 분석이 하는 일: 알고리즘의 모든 연산을 추적하여 입력 크기 n에 대한 최악의 경우 실행 시간이 선형임을 증명합니다. 첫 번째로, for 루프는 명백히 n회 반복됩니다.
각 막대를 한 번씩 방문하므로 이 부분은 O(n)입니다. 문제는 내부의 while 루프입니다.
각 for 반복마다 while이 몇 번 실행될지 불확실하므로, 직관적으로는 O(n²)처럼 보일 수 있습니다. 두 번째로, 핵심 통찰은 "전역적 관점"에서 봐야 한다는 것입니다.
특정 i에서 while이 몇 번 실행되는지가 아니라, 모든 i에 대해 while이 총 몇 번 실행되는지를 봐야 합니다. while 루프의 각 반복은 스택에서 요소를 하나 pop합니다.
그런데 각 요소는 한 번만 push되므로, pop도 최대 한 번만 가능합니다. 따라서 모든 for 반복을 합쳐서 while은 최대 n번 실행됩니다.
세 번째로, 수학적으로 표현하면: push 총 횟수 = n (각 요소가 for 루프에서 한 번씩 push됨), pop 총 횟수 ≤ n (각 요소가 최대 한 번 pop됨), 따라서 총 스택 연산 = push + pop ≤ 2n = O(n)입니다. 추가로 비교 연산, 면적 계산 등도 각 push/pop당 상수 시간이므로 전체 복잡도에 영향을 주지 않습니다.
여러분이 이 분석 기법을 이해하면 다른 누적 분석(amortized analysis) 문제도 해결할 수 있습니다. 동적 배열의 크기 조정, 유니온-파인드 알고리즘, 슬라이싱 윈도우 등 다양한 알고리즘에서 동일한 분석 방법이 사용됩니다.
실무에서는 성능 프로파일링 시 "개별 연산의 최악"이 아닌 "전체 연산의 합"을 측정해야 하는데, 이 개념이 바로 그 기초입니다.
실전 팁
💡 실제로 카운터를 넣어서 테스트해보세요. 다양한 입력에 대해 push_count + pop_count가 항상 2n 이하임을 확인하면 이론적 분석에 대한 확신이 생깁니다.
💡 최악의 경우를 구체적으로 생각해보세요. 단조 증가 배열 [1, 2, 3, ..., n]에서는 while이 거의 실행되지 않고, 단조 감소 배열 [n, n-1, ..., 1]에서는 while이 많이 실행되지만, 둘 다 총 2n번을 넘지 않습니다.
💡 공간 복잡도도 O(n)입니다. 최악의 경우 모든 요소가 스택에 들어갈 수 있으므로(단조 증가 배열), 스택의 최대 크기는 n입니다.
💡 누적 분석(amortized analysis) 개념을 공부하세요. 단조 스택뿐 아니라 동적 프로그래밍, 자료구조 최적화 등 많은 알고리즘에서 이 기법이 사용됩니다.
💡 성능 벤치마크를 작성할 때 다양한 n 값(10³, 10⁴, 10⁵, 10⁶)으로 테스트하고 실행 시간을 그래프로 그려보세요. 선형 증가를 시각적으로 확인할 수 있습니다.
6. 실전 구현 시 주의사항
시작하며
여러분이 이론을 완벽히 이해했어도 실제 구현에서는 예상치 못한 버그가 발생할 수 있습니다. 인덱스 에러, 잘못된 초기화, 엣지 케이스 처리 실수 등이 대표적입니다.
특히 코딩 인터뷰에서는 시간 압박이 있어서 작은 실수를 하기 쉽습니다. 예를 들어, stack[-1]을 호출하기 전에 스택이 비어있는지 확인하지 않으면 IndexError가 발생합니다.
또는 heights[stack[-1]]와 heights[i]를 비교해야 하는데 인덱스와 값을 헷갈려서 버그가 생기기도 합니다. 실무에서는 코드의 가독성과 유지보수성도 중요합니다.
변수명이 명확하고, 로직이 이해하기 쉬우며, 엣지 케이스가 명시적으로 처리되어야 합니다. 단순히 동작하는 코드가 아니라 "좋은" 코드를 작성하는 것이 목표입니다.
개요
간단히 말해서, 실전 구현에서는 엣지 케이스 처리, 변수명 명확화, 방어적 프로그래밍, 그리고 충분한 테스트가 필요합니다. 실전 구현이 중요한 이유는 알고리즘 지식만으로는 부족하기 때문입니다.
빈 배열, 길이 1인 배열, 모든 요소가 같은 배열, 음수 높이 등 다양한 입력에 대해 안정적으로 동작해야 합니다. 예를 들어, 실제 데이터 분석 시스템에서는 예상치 못한 입력이 들어와도 크래시하지 않아야 하며, 로그를 통해 문제를 추적할 수 있어야 합니다.
이론적인 코드에서는 핵심 로직만 다루지만, 프로덕션 코드에서는 입력 검증, 에러 처리, 로깅, 문서화가 추가로 필요합니다. 실전 구현의 핵심 요소: (1) 입력 검증 - None 체크, 빈 배열 처리, 음수/0 처리, (2) 방어적 프로그래밍 - 스택 접근 전 빈 스택 체크, 배열 범위 확인, (3) 명확한 변수명 - height_idx, current_height 등 의미가 분명한 이름 사용, (4) 충분한 주석 - 특히 복잡한 부분(너비 계산, 경계 처리)에 설명 추가, (5) 단위 테스트 - 정상 케이스와 엣지 케이스 모두 커버.
이 요소들이 코드의 품질과 신뢰성을 결정합니다.
코드 예제
def largestRectangleAreaProduction(heights):
"""프로덕션 레벨의 구현 예제"""
# 입력 검증
if not heights:
return 0
if len(heights) == 1:
return heights[0]
# 음수 높이 체크 (문제 요구사항에 따라)
if any(h < 0 for h in heights):
raise ValueError("Heights must be non-negative")
stack = [] # 단조 증가 스택 (인덱스 저장)
max_area = 0
try:
# 메인 루프: 각 막대 순회
for current_idx, current_height in enumerate(heights):
# 단조성 유지: 현재 높이보다 큰 스택 요소 제거
while stack and heights[stack[-1]] > current_height:
# 높이 계산
height_idx = stack.pop()
rectangle_height = heights[height_idx]
# 너비 계산: 경계 사이의 거리
if not stack:
# 왼쪽 경계 없음: 처음부터 확장 가능
rectangle_width = current_idx
else:
# 양쪽 경계 존재
left_boundary = stack[-1]
rectangle_width = current_idx - left_boundary - 1
# 면적 갱신
area = rectangle_height * rectangle_width
max_area = max(max_area, area)
stack.append(current_idx)
# 스택에 남은 요소 처리
n = len(heights)
while stack:
height_idx = stack.pop()
rectangle_height = heights[height_idx]
# 오른쪽 경계: 배열 끝
if not stack:
rectangle_width = n
else:
left_boundary = stack[-1]
rectangle_width = n - left_boundary - 1
area = rectangle_height * rectangle_width
max_area = max(max_area, area)
return max_area
except Exception as e:
# 프로덕션에서는 로깅 추가
print(f"Error processing histogram: {e}")
raise
설명
프로덕션 코드가 하는 일: 알고리즘의 핵심 로직뿐 아니라 입력 검증, 에러 처리, 가독성 향상을 통해 실제 서비스에서 안정적으로 동작할 수 있도록 만듭니다. 첫 번째로, 입력 검증부터 시작합니다.
빈 배열이 들어오면 즉시 0을 반환하여 불필요한 연산을 방지합니다. 길이가 1인 배열도 특별히 처리하면 메인 로직을 더 단순화할 수 있습니다.
음수 높이 같은 잘못된 입력에 대해서는 명확한 에러 메시지와 함께 예외를 발생시킵니다. 이런 검증 로직이 있으면 디버깅 시간을 크게 줄일 수 있습니다.
두 번째로, 변수명을 명확하게 작성합니다. i, h 같은 짧은 이름 대신 current_idx, current_height, rectangle_height, rectangle_width 처럼 의미가 분명한 이름을 사용합니다.
특히 height_idx와 current_idx를 구분하여 pop된 막대와 현재 막대를 혼동하지 않도록 합니다. 코드를 6개월 후에 다시 봐도 즉시 이해할 수 있어야 합니다.
세 번째로, 방어적 프로그래밍을 적용합니다. stack[-1]에 접근하기 전에 항상 if stack으로 확인합니다.
이것이 IndexError를 방지하는 가장 확실한 방법입니다. 또한 너비 계산에서 경계 조건을 명시적으로 분기 처리하여 각 케이스가 명확하게 드러나도록 합니다.
if-else를 사용하면 삼항 연산자보다 가독성이 높아집니다. 네 번째로, 주석을 적절히 추가합니다.
알고리즘의 핵심 단계("단조성 유지", "너비 계산")에 간단한 설명을 달아서 코드 리뷰어나 미래의 자신이 쉽게 이해할 수 있도록 합니다. 특히 -1이 나오는 부분처럼 헷갈리기 쉬운 곳에는 이유를 설명하는 주석이 필수입니다.
여러분이 이런 프랙티스를 적용하면 버그 발생률이 크게 줄어들고, 코드 리뷰가 빨라지며, 유지보수가 쉬워집니다. 실무에서는 알고리즘의 효율성만큼이나 코드의 품질이 중요하며, 특히 팀 프로젝트에서는 다른 사람이 이해할 수 있는 코드를 작성하는 것이 핵심입니다.
실전 팁
💡 타입 힌트를 추가하세요. def largestRectangleArea(heights: List[int]) -> int: 처럼 타입을 명시하면 IDE의 자동완성과 타입 체킹이 가능해집니다.
💡 docstring을 작성하세요. 함수의 목적, 파라미터, 반환값, 시간/공간 복잡도, 예제를 포함하면 문서화가 자동으로 됩니다.
💡 단위 테스트를 먼저 작성하는 TDD 방식을 고려하세요. 엣지 케이스를 테스트로 먼저 정의하면 구현 시 놓치지 않게 됩니다.
💡 assert 문으로 불변 조건을 검증하세요. 예: assert len(stack) <= len(heights) - 디버그 모드에서 논리 오류를 조기에 발견할 수 있습니다.
💡 코드 리뷰를 요청하세요. 다른 개발자의 피드백을 통해 놓친 엣지 케이스나 개선점을 발견할 수 있습니다. 특히 알고리즘 코드는 혼자 보면 버그를 찾기 어렵습니다.
7. 단조 스택의 다양한 응용 문제
시작하며
여러분이 히스토그램 문제를 마스터했다면, 이제 이 패턴을 다른 문제에 응용할 차례입니다. 단조 스택은 히스토그램만의 전유물이 아닙니다.
"각 요소에 대해 다음/이전의 더 큰/작은 요소를 찾는" 모든 문제에 적용할 수 있습니다. 실무에서도 이런 패턴은 자주 등장합니다.
주식 거래 시스템에서 "각 날짜에 대해 다음으로 가격이 오르는 날짜 찾기", 웹 서버 로그에서 "각 요청에 대해 이전의 더 느린 요청 찾기", UI 렌더링에서 "각 요소에 대해 뒤에 가려지지 않는 범위 찾기" 등이 모두 단조 스택 패턴입니다. 문제의 표면적 설명은 다르지만, 근본적으로는 동일한 구조를 가지고 있습니다.
이 패턴을 인식하는 능력을 키우면 다양한 문제를 효율적으로 해결할 수 있습니다.
개요
간단히 말해서, 단조 스택 패턴은 히스토그램 외에도 Next Greater Element, Daily Temperatures, Trapping Rain Water, 최대 이진 트리 등 수십 가지 문제에 적용됩니다. 이 패턴이 널리 쓰이는 이유는 "상대적 크기 비교"와 "범위 확장"이라는 개념이 많은 문제에 내재되어 있기 때문입니다.
예를 들어, "온도가 더 따뜻해지려면 며칠을 기다려야 하나" 문제는 "각 온도에 대해 다음으로 더 높은 온도의 위치 찾기"로 변환되며, 이는 단조 감소 스택으로 O(n)에 해결됩니다. 전통적으로 중첩 반복문으로 O(n²)에 풀던 문제들을 단조 스택으로 O(n)으로 개선할 수 있습니다.
단조 스택 패턴을 적용할 수 있는 문제의 특징: (1) 각 요소에 대해 "다음/이전의 더 큰/작은 요소"를 찾아야 합니다, (2) 연속된 범위에서 특정 조건을 만족하는 구간을 찾습니다, (3) 스택에 저장된 정보가 "아직 해결되지 않은 문제"를 나타냅니다, (4) 새 요소가 기존 요소의 답을 확정합니다. 이 특징들이 보이면 단조 스택을 시도해보세요.
코드 예제
# 응용 예제 1: Next Greater Element
def nextGreaterElement(nums):
"""각 요소의 오른쪽에서 처음으로 더 큰 요소 찾기"""
n = len(nums)
result = [-1] * n # 기본값: 없음
stack = [] # 단조 감소 스택
for i, num in enumerate(nums):
# 현재 값이 스택 top보다 크면
# 스택의 요소들이 답을 찾은 것
while stack and nums[stack[-1]] < num:
prev_idx = stack.pop()
result[prev_idx] = num # 답 저장
stack.append(i)
return result
# 응용 예제 2: Daily Temperatures
def dailyTemperatures(temperatures):
"""며칠 후 더 따뜻해지는지 계산"""
n = len(temperatures)
answer = [0] * n
stack = [] # 단조 감소 스택
for i, temp in enumerate(temperatures):
while stack and temperatures[stack[-1]] < temp:
prev_idx = stack.pop()
# 날짜 차이 계산
answer[prev_idx] = i - prev_idx
stack.append(i)
return answer
# 응용 예제 3: Trapping Rain Water (변형)
def trapRainWater(height):
"""히스토그램 패턴의 고급 응용"""
stack = []
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom_idx = stack.pop()
if not stack:
break
# 물이 고이는 높이
distance = i - stack[-1] - 1
bounded_height = min(h, height[stack[-1]]) - height[bottom_idx]
water += distance * bounded_height
stack.append(i)
return water
설명
응용 문제들이 하는 일: 히스토그램과 동일한 단조 스택 패턴을 사용하되, 문제의 요구사항에 맞게 스택의 단조성 방향, 저장할 값, 계산 방식을 조정합니다. 첫 번째 예제인 Next Greater Element는 가장 직접적인 응용입니다.
각 요소에 대해 오른쪽에서 처음으로 더 큰 요소를 찾아야 합니다. 단조 감소 스택을 사용하여, 현재 요소가 스택 top보다 크면 스택의 요소들이 "답을 찾았다"는 의미로 pop하면서 결과를 저장합니다.
히스토그램과 달리 여기서는 면적이 아니라 값 자체를 저장하는 것이 차이점입니다. 주식 거래 시스템에서 "다음으로 가격이 오를 시점" 찾기, 이벤트 처리에서 "다음 중요 이벤트" 찾기 등에 직접 활용됩니다.
두 번째 예제인 Daily Temperatures는 Next Greater Element의 변형입니다. 더 큰 요소의 값이 아니라 "며칠 후인지"를 계산합니다.
이는 인덱스 차이 i - prev_idx로 간단히 구할 수 있습니다. 이 패턴은 시계열 데이터 분석에서 매우 유용합니다.
예를 들어, 서버 응답 시간이 개선되는 시점 찾기, 사용자 활동이 증가하는 시점 예측하기 등에 응용됩니다. 실무에서는 대시보드의 추세 분석, 알림 시스템의 이벤트 탐지 등에 사용됩니다.
세 번째 예제인 Trapping Rain Water는 고급 응용입니다. 히스토그램 문제와 구조가 비슷하지만, 계산하는 것이 직사각형 면적이 아니라 빗물이 고이는 양입니다.
물은 양쪽 벽 사이의 낮은 부분에 고이므로, 바닥(bottom)과 양쪽 벽의 최소 높이를 고려해야 합니다. bounded_height가 물의 높이이고, distance가 너비입니다.
이 패턴은 컨테이너 최적화(Container With Most Water), 빌딩 실루엣, 지형 분석 등 2D 공간 문제에 확장할 수 있습니다. 여러분이 이런 응용 문제들을 연습하면 단조 스택 패턴을 자유자재로 사용할 수 있게 됩니다.
새로운 문제를 만났을 때 "이게 단조 스택 문제인가?"를 판단하고, 적절한 변형을 적용하는 능력이 생깁니다. 실무에서는 이런 패턴 인식 능력이 복잡한 비즈니스 로직을 효율적인 알고리즘으로 변환하는 핵심 역량입니다.
실전 팁
💡 문제를 단순화하여 패턴을 찾으세요. "각 X에 대해 Y를 찾기" 형태로 표현되면 단조 스택을 의심해보세요.
💡 단조 증가 vs 감소를 결정하는 규칙: "다음 큰 요소"를 찾으려면 단조 감소 스택, "다음 작은 요소"를 찾으려면 단조 증가 스택입니다. 헷갈리면 작은 예제로 손으로 그려보세요.
💡 스택에 무엇을 저장할지 고민하세요. 인덱스만? 값도 함께? (인덱스, 값) 튜플? 문제에 따라 다르지만, 인덱스만 저장하고 필요시 배열에서 값을 가져오는 것이 일반적으로 깔끔합니다.
💡 LeetCode나 백준에서 관련 문제를 묶어서 풀어보세요. Monotonic Stack 태그가 있는 문제들을 연속으로 풀면 패턴이 몸에 익습니다.
💡 각 응용 문제의 차이점을 정리하세요. 표를 만들어서 "문제 이름 스택 방향 저장 값 계산 내용"을 비교하면 공통점과 차이점이 명확해집니다.
8. 테스트 케이스와 디버깅 전략
시작하며
여러분이 단조 스택 알고리즘을 구현했다고 생각해도, 테스트 없이는 정확성을 보장할 수 없습니다. 특히 엣지 케이스에서 미묘한 버그가 숨어있는 경우가 많습니다.
코딩 인터뷰에서 "일반적인 케이스는 통과하는데 엣지 케이스에서 틀렸다"는 피드백을 받는 경우가 흔합니다. 빈 배열, 길이 1, 모두 같은 값, 단조 증가/감소 등은 반드시 테스트해야 하는 케이스들입니다.
실무에서도 프로덕션 배포 전에 이런 극단적인 입력을 테스트하는 것이 버그 예방의 핵심입니다. 디버깅도 체계적으로 해야 합니다.
단순히 print를 찍는 것보다, 스택의 상태, 계산된 면적, 경계 값을 구조화해서 추적하면 버그를 훨씬 빨리 찾을 수 있습니다.
개요
간단히 말해서, 포괄적인 테스트 케이스(정상, 엣지, 극단)와 체계적인 디버깅 전략(스택 상태 추적, 단계별 검증)이 알고리즘의 정확성을 보장합니다. 테스트가 중요한 이유는 알고리즘의 모든 실행 경로를 검증하기 위함입니다.
예를 들어, 스택이 비는 경우, 스택이 가득 차는 경우, while 루프가 여러 번 실행되는 경우, 스택 처리 단계에서만 면적이 계산되는 경우 등 다양한 시나리오를 커버해야 합니다. 하나라도 놓치면 특정 입력에서 런타임 에러나 잘못된 결과가 발생할 수 있습니다.
일반적인 단위 테스트에서는 입력과 기대 출력만 비교하지만, 알고리즘 테스트에서는 중간 상태도 검증해야 합니다. 테스트 케이스의 종류: (1) 정상 케이스 - 문제 설명의 예제, 중간 크기의 일반적인 입력, (2) 엣지 케이스 - 빈 배열, 길이 1, 길이 2, 모두 같은 값, (3) 극단 케이스 - 단조 증가, 단조 감소, 최대 크기 입력, (4) 특수 케이스 - 0이 포함된 경우, 음수(허용 시), 최대 높이 값.
각 카테고리에서 적어도 하나씩 테스트해야 합니다.
코드 예제
import unittest
class TestHistogramAlgorithm(unittest.TestCase):
def largestRectangleArea(self, heights):
"""테스트할 알고리즘"""
if not heights:
return 0
stack = []
max_area = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height_idx = stack.pop()
height = heights[height_idx]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
n = len(heights)
while stack:
height_idx = stack.pop()
height = heights[height_idx]
width = n if not stack else n - stack[-1] - 1
max_area = max(max_area, height * width)
return max_area
# 정상 케이스
def test_normal_case(self):
self.assertEqual(self.largestRectangleArea([2, 1, 5, 6, 2, 3]), 10)
self.assertEqual(self.largestRectangleArea([2, 4]), 4)
# 엣지 케이스
def test_empty_array(self):
self.assertEqual(self.largestRectangleArea([]), 0)
def test_single_element(self):
self.assertEqual(self.largestRectangleArea([5]), 5)
def test_all_same_height(self):
self.assertEqual(self.largestRectangleArea([3, 3, 3, 3]), 12)
# 극단 케이스
def test_monotonic_increasing(self):
self.assertEqual(self.largestRectangleArea([1, 2, 3, 4, 5]), 9)
def test_monotonic_decreasing(self):
self.assertEqual(self.largestRectangleArea([5, 4, 3, 2, 1]), 9)
# 특수 케이스
def test_with_zeros(self):
self.assertEqual(self.largestRectangleArea([0, 2, 0]), 2)
self.assertEqual(self.largestRectangleArea([0, 0, 0]), 0)
# 디버깅 헬퍼 함수
def debugHistogram(heights):
"""스택 상태를 추적하며 실행"""
print(f"\n입력: {heights}")
stack = []
max_area = 0
step = 1
for i, h in enumerate(heights):
print(f"\n[Step {step}] 현재 인덱스: {i}, 높이: {h}")
print(f" 스택 (전): {[f'i={idx},h={heights[idx]}' for idx in stack]}")
popped = []
while stack and heights[stack[-1]] > h:
idx = stack.pop()
height = heights[idx]
width = i if not stack else i - stack[-1] - 1
area = height * width
max_area = max(max_area, area)
popped.append(f"i={idx}(h={height}, w={width}, a={area})")
if popped:
print(f" Pop: {popped}")
print(f" 최대 면적 갱신: {max_area}")
stack.append(i)
print(f" 스택 (후): {[f'i={idx},h={heights[idx]}' for idx in stack]}")
step += 1
print(f"\n[최종 처리] 스택에 남은 요소: {stack}")
n = len(heights)
while stack:
idx = stack.pop()
height = heights[idx]
width = n if not stack else n - stack[-1] - 1
area = height * width
max_area = max(max_area, area)
print(f" 처리: i={idx}, h={height}, w={width}, a={area}, max={max_area}")
print(f"\n최종 답: {max_area}\n")
return max_area
설명
테스트와 디버깅이 하는 일: 알고리즘이 모든 입력에 대해 정확하게 동작하는지 검증하고, 문제 발생 시 원인을 신속하게 파악할 수 있도록 합니다. 첫 번째로, 체계적인 단위 테스트를 작성합니다.
unittest나 pytest 같은 프레임워크를 사용하여 각 케이스를 독립적으로 검증합니다. 정상 케이스는 문제에서 제공한 예제를 포함하며, 이것이 통과하지 않으면 기본 로직에 문제가 있는 것입니다.
엣지 케이스는 빈 배열(크래시 방지), 길이 1(루프 진입 여부), 모두 같은 값(while이 실행되지 않는 경우)을 테스트합니다. 극단 케이스는 알고리즘의 최선/최악 시나리오를 검증합니다.
두 번째로, 각 테스트 케이스가 커버하는 코드 경로를 이해해야 합니다. 예를 들어, 단조 증가 배열은 메인 루프에서 while이 실행되지 않고 모든 계산이 최종 스택 처리에서 이루어지는 경로를 테스트합니다.
단조 감소 배열은 반대로 while이 많이 실행되는 경로를 테스트합니다. 이렇게 다양한 실행 경로를 커버하는 것이 테스트의 목표입니다.
세 번째로, 디버깅 전략을 수립합니다. debugHistogram 함수처럼 각 단계에서 스택의 상태, pop된 요소, 계산된 면적을 상세히 출력하면 문제를 시각적으로 파악할 수 있습니다.
특히 "왜 이 시점에서 이 값이 계산되었는가"를 추적하면 논리 오류를 빠르게 발견할 수 있습니다. 예를 들어, 너비가 음수로 나온다면 경계 계산 로직에 문제가 있는 것이고, 특정 막대의 면적이 계산되지 않는다면 pop 조건이나 최종 스택 처리에 버그가 있는 것입니다.
네 번째로, 실패한 테스트를 그대로 두지 말고 즉시 수정합니다. TDD(Test-Driven Development) 방식을 따르면 테스트를 먼저 작성하고 코드를 작성하므로, 자연스럽게 모든 케이스가 커버됩니다.
코드를 먼저 작성한 경우에도 테스트를 추가하면서 놓친 버그를 발견하고 수정하는 반복 과정이 필요합니다. 여러분이 이런 테스트와 디버깅 습관을 들이면 코드 품질이 크게 향상됩니다.
실무에서는 CI/CD 파이프라인에 이런 테스트를 통합하여 모든 커밋이 자동으로 검증되도록 설정합니다. 버그가 프로덕션에 도달하기 전에 조기에 발견하는 것이 개발 비용을 크게 줄이는 방법입니다.
실전 팁
💡 테스트 커버리지 도구를 사용하세요. pytest-cov나 coverage.py로 코드의 어느 부분이 테스트되지 않았는지 확인할 수 있습니다.
💡 경계값 분석(Boundary Value Analysis)을 적용하세요. 0, 1, n-1, n 같은 경계 인덱스에서 문제가 발생하기 쉬우므로 집중적으로 테스트하세요.
💡 속성 기반 테스트(Property-based Testing)를 시도해보세요. Hypothesis 라이브러리로 무작위 입력을 생성하고 불변 조건(예: 결과가 항상 0 이상)을 검증할 수 있습니다.
💡 시각화 도구를 만들어보세요. matplotlib로 히스토그램과 계산된 직사각형을 그려보면 알고리즘의 동작을 직관적으로 이해할 수 있습니다.
💡 페어 프로그래밍이나 코드 리뷰를 활용하세요. 다른 사람의 눈으로 보면 자신이 놓친 테스트 케이스나 버그를 발견할 수 있습니다.