모노토닉 스택 코딩테스트: 같은 높이와 사각형 너비를 검증하기

모노토닉 스택 코딩테스트에서 같은 높이의 막대를 만나면, pop 조건과 사각형 폭 계산을 함께 검증해야 합니다. 핵심은 >와 >= 가운데 하나를 외우는 일이 아니라, 스택이 보존하는 경계 의미를 끝까지 일관되게 유지하는 것입니다. 아래에서 [2,2,2]와 [2,1,2]를 직접 추적하고, 단순 완전탐색과 비교해 구현을 확인합니다. PracHub의 Largest Rectangle in a Histogram는 다양한 후보 문제를 연습하는 자료이며 특정 시험의 출제 문제를 예측하지 않습니다.

근거 범위. 공식 언어 문서는 라이브러리 동작의 근거입니다. 아래 불변식과 풀이의 정당성은 명시한 입력 계약에 따른 유도이며, 배열·그래프·시간축과 검산 코드는 이 글의 합성 교육 사례입니다. 후보자 보고나 특정 회사의 출제 형식은 사용하지 않았습니다.

먼저 고정할 불변식: 스택에는 무엇을 저장하나? (Stack invariant)

막대 높이 배열 h에서 각 막대 p를 직사각형의 최솟값으로 삼아, 그 높이로 확장 가능한 최대 폭을 찾습니다. 인덱스를 오름차순으로 쌓고 높이를 증가하는 순서로 유지하면, 현재 막대보다 낮은 막대가 나오는 순간 더는 확장할 수 없는 막대가 확정됩니다.

막대 p를 인덱스 i에서 꺼낼 때 왼쪽 경계는 새 스택 top입니다. 오른쪽 경계는 i이며 둘 다 직사각형에 포함되지 않으므로 width = i - left - 1, 넓이는 h[p] * width입니다. 왼쪽 top이 없다면 경계 인덱스를 -1로 간주합니다. left=1, i=4라면 실제 인덱스는 2와 3이어서 폭은 2입니다.

같은 높이는 >와 >= 모두 가능하다 (Equal heights)

while h[stack[-1]] > h[i]는 같은 높이를 스택에 남깁니다. [2,2,2]가 끝나면 마지막부터 차례로 꺼내면서 시작점이 왼쪽으로 전달되고, 높이 2의 폭 3을 계산할 수 있습니다. 반대로 >=를 사용하면 같은 높이의 이전 인덱스를 먼저 제거해 새 인덱스가 더 이른 시작점을 이어받도록 해야 합니다. 조건만 바꾸고 경계 전달을 빠뜨리면 최대 폭을 놓칩니다.

구현: sentinel로 남은 막대를 정리하기 (Sentinel)

아래 구현은 실제 배열을 수정하지 않고, 마지막 인덱스에서만 높이 0인 가상 sentinel을 사용합니다. 높이가 0인 막대가 입력에 있을 수 있으므로 >=로 pop하고, 새 막대의 시작 인덱스를 pop한 막대의 시작값으로 갱신합니다. 빈 배열은 0을 반환합니다.

def largest_rectangle(heights):
    stack = []  # (earliest_start, height), 높이는 비감소
    best = 0
    n = len(heights)
    for i in range(n + 1):
        cur = 0 if i == n else heights[i]
        start = i
        while stack and stack[-1][1] >= cur:
            left, height = stack.pop()
            best = max(best, height * (i - left))
            start = left
        if i < n:
            stack.append((start, cur))
    return best

이 표현은 left를 경계 막대가 아니라 직사각형을 시작할 수 있는 가장 이른 인덱스로 저장합니다. 따라서 폭은 i-left입니다. 앞서 설명한 경계 인덱스 방식의 i-left-1과 섞지 마세요. 둘은 저장하는 의미가 다릅니다.

반례를 작은 완전탐색 오라클과 비교하기 (Brute-force oracle)

스택 코드는 모든 연속 구간 [l,r]에서 최솟값을 구하는 단순 풀이와 비교할 수 있습니다. 작은 입력에서 모든 경우를 대조하면 경계 오류를 빠르게 찾습니다. [2,2,2]처럼 동률만 있는 입력, [2,1,2]처럼 낮은 막대가 가운데 있는 입력, [0], 빈 배열을 반드시 포함합니다.

def brute(h):
    ans = 0
    for l in range(len(h)):
        low = float('inf')
        for r in range(l, len(h)):
            low = min(low, h[r])
            ans = max(ans, low * (r - l + 1))
    return ans

from itertools import product

for n in range(7):
    for heights in product(range(4), repeat=n):
        assert largest_rectangle(heights) == brute(heights), heights

복잡도 설명과 제출 전 체크 (Amortized cost)

각 인덱스는 스택에 한 번 들어가고 많아야 한 번 나옵니다. 내부 while문이 중첩돼 보여도 전체 pop 횟수는 n 이하이므로 시간은 O(n), 스택 공간은 O(n)입니다. 제출 전에 높이가 음수가 될 수 있는지, 넓이 자료형이 충분한지 문제 제약을 확인하세요. Python은 정수 오버플로가 없지만 C++과 Java에서는 height * width 계산 전에 넓은 정수형으로 변환해야 합니다.

연습 문제로 불변식을 설명하기 (Practice)

아래 연습 자료는 최대 직사각형, 창 최댓값, 조합 생성, 구간 sweep, 행렬 그래프 거리를 함께 다룹니다. 각 문제의 공식 레코드는 연습용 자료이며 특정 시험의 출제를 예측하지 않습니다.

단조 스택의 정당성: pop된 막대는 왜 끝났나? (Correctness proof)

높이가 height인 막대가 스택 top에 있다고 합시다. 현재 높이가 그보다 작으면 현재 위치부터 오른쪽으로는 높이 height를 유지할 수 없습니다. 현재 인덱스가 그 막대의 첫 번째 더 낮은 오른쪽 경계입니다. 인덱스 스택에서 >=로 pop하면 새 top은 꺼낸 높이보다 엄격히 낮은 왼쪽 경계입니다. >로 pop하는 정책에서는 같은 높이의 top이 남을 수 있으므로, 각 pop이 곧 그 높이의 최대 폭을 계산한다고 말하면 부정확합니다. 같은 높이 중 가장 왼쪽 항목을 꺼낼 때 전체 폭까지 계산되고, 그중 최대 넓이를 보존합니다.

이 논증은 같은 높이의 처리 방식을 설명할 때도 유용합니다. <만 비교하면 같은 높이가 여러 개 남을 수 있습니다. 그중 먼저 만난 막대를 계산할 때 왼쪽 낮은 경계가 같고 오른쪽 경계가 갱신되며 결국 넓이 6이 만들어집니다. <=로 모두 합치면 가장 왼쪽 시작 인덱스를 새 항목에 전달해야 합니다. 두 구현을 비교할 때는 “동률이면 pop할까?”만 묻지 말고 “pop한 시작 경계를 다음 항목에 어떻게 전달하는가?”를 함께 확인하세요.

경계 인덱스 저장 방식과 시작 인덱스 저장 방식 (Boundary vs start)

다음과 같이 경계 인덱스만 저장하는 구현도 가능합니다. 여기서는 높이가 같은 막대를 남기는 < 조건을 사용합니다. pop 뒤 stack top은 왼쪽의 낮거나 같은 높이의 경계이고, 스택이 비었다면 왼쪽 경계는 -1입니다. i는 현재 막대보다 낮아진 오른쪽 경계이므로 넓이는 i-left-1입니다.

def largest_rectangle_boundary(heights):
    stack = []  # index; heights are nondecreasing
    best = 0
    for i in range(len(heights) + 1):
        cur = 0 if i == len(heights) else heights[i]
        while stack and heights[stack[-1]] > cur:
            p = stack.pop()
            left = stack[-1] if stack else -1
            best = max(best, heights[p] * (i - left - 1))
        if i < len(heights):
            stack.append(i)
    return best

[2,2,2]에서는 세 인덱스가 남아 있다가 마지막 sentinel에서 차례로 pop됩니다. 처음 pop의 폭은 1, 다음은 2, 마지막은 3이어서 최댓값 6을 얻습니다. 앞서 나온 시작 인덱스 방식과 결과는 같지만, 하나는 각 높이가 가진 가장 이른 시작점을 들고 다니고 다른 하나는 왼쪽 경계 인덱스를 다시 계산합니다. 코드를 설명하는 중간에 두 공식을 섞지 않도록 각 변수의 의미를 말로 붙여 두세요.

다음 연습에서 설명할 한 가지 (Next exercise)

오늘은 Largest Rectangle in a Histogram를 풀면서 같은 높이 반례를 손으로 추적한 뒤 경계 사례 하나와 시간·공간 복잡도를 소리 내어 설명해 보세요. Practice 자료는 연습을 위한 기록이며 실제 시험 문제를 예측하지 않습니다.

한 손으로 경계를 추적하는 미니 워크스루 (Trace)

입력 [2,2,2]에서 >= 정책을 쓰면 인덱스 0의 높이 2가 인덱스 1을 만날 때 먼저 꺼내집니다. 새 항목의 start가 0으로 되돌아가고 (0,2)가 스택에 들어갑니다. 인덱스 2에서도 같은 일이 일어나 (0,2)가 남습니다. 마지막 가상 높이 0을 만나 이 항목이 꺼내지면 계산값은 2 × (3-0)=6입니다. 여기서 세 인덱스를 모두 쌓아 두는 방식으로 바꾼다면 pop 때 계산 폭이 달라집니다. 둘 중 하나의 표현을 골라 일관되게 유지하세요.

[2,1,2]에서는 높이 1인 막대가 오른쪽의 2를 만나기 전 이미 왼쪽의 2를 꺼냅니다. 왼쪽 막대가 만들 수 있는 가장 넓은 폭은 1이므로 넓이 2입니다. 마지막 sentinel은 오른쪽 2를 넓이 1로 정리하고, 남아 있던 높이 1은 폭 3으로 계산해 넓이 3을 얻습니다. 이 입력은 “각 막대의 높이로 좌우 확장한다”는 설명을 코드로 확인하기 좋습니다.

구현을 바꿀 때 다시 확인할 경계 (Numeric bounds)

인덱스 스택 구현에서 sentinel을 실제 배열에 추가하면 입력이 수정되는 부작용이 생길 수 있습니다. 함수가 입력 불변을 요구하는지 확인하고, 가상 인덱스 또는 별도 반복으로 끝을 처리하세요. 높이가 음수일 수 있는 문제라면 sentinel 0이 모든 막대를 정리하지 못하는 상황도 고려해야 합니다. 일반적인 막대 문제는 높이가 0 이상이라는 제약이 있지만, 그것은 문제마다 확인할 조건입니다.

또한 정답이 32비트 범위를 넘을 수 있는지 제약으로 계산해 보세요. 폭의 최댓값은 n, 높이 최댓값이 H라면 최댓넓이 상한은 nH입니다. 이 곱이 자료형 한계를 넘으면 변수 하나만 넓게 선언하는 것으로 충분한지, 곱셈 시점에 형변환되는지까지 확인해야 합니다.

Sources and Further Reading

• USACO Guide: Stacks — 스택 연산과 가까운 작은 원소를 찾는 예제. 히스토그램의 동률 정책과 두 폭 공식은 본문에서 별도로 유도하고 검증합니다.
• Python data structures: lists as stacks — 본문 Python 예제의 append/pop 스택 동작 공식 문서.
• CP-Algorithms: Minimum Stack / Minimum Queue — 히스토그램 해설은 아니며, 후보를 제거하며 유지하는 단조 자료구조의 인접 예제.