'6549번 히스토그램에서 가장 큰 직사각형 넓이' 문제를 파고들었던 내용을 공유하려 합니다. 처음에는 그리디나 DP로 접근하려 했지만, 결국 '단조 스택'이라는 자료구조 패턴을 통해 명쾌하게 해결할 수 있었습니다. 문제 해결 과정에서 느꼈던 좌절감, 깨달음, 그리고 마...

6549번 히스토그램에서 가장 큰 직사각형 넓이: 스택으로 파헤치는 문제 해결 전략

'6549번 히스토그램에서 가장 큰 직사각형 넓이' 문제를 파고들었던 내용을 공유하려 합니다. 처음에는 그리디나 DP로 접근하려 했지만, 결국 '단조 스택'이라는 자료구조 패턴을 통해 명쾌하게 해결할 수 있었습니다. 문제 해결 과정에서 느꼈던 좌절감, 깨달음, 그리고 마지막에 퍼즐 조각이 맞춰지듯 이해하게 된 순간들을 나누고 싶습니다.

학습 주제

문제: 6549번 히스토그램에서 가장 큰 직사각형 넓이 (백준)
학습 날짜: 2026년 2월 2일

질문과 탐구

이 문제는 여러 막대 높이로 이루어진 히스토그램에서 가장 넓은 직사각형을 찾는 문제입니다. 처음에는 각 막대 높이를 기준으로 주변을 탐색하며 그리디하게 접근하려 했습니다.

초기 궁금증: "가장 높은 막대를 중심으로 주변을 확장하면 되지 않을까?" 또는 "현재 막대 높이를 유지하면서 최대한 넓혀보자."
주요 질문:
- "현재 선택이 미래에 최적일지는 어떻게 알 수 있을까?"
- "만약 지금은 낮지만 나중에 더 높은 막대가 계속 나온다면, 현재 높이를 유지하는 게 최적일까?"
- "가장 높은 막대를 기준으로 시작하는 것이 항상 정답일까?"
탐구 과정:
- 높이가 다른 막대들로 이루어진 예시 [2, 1, 5, 6, 2, 3]에서 5와 6 막대를 볼 때, 6을 기준으로 넓이를 계산하는 것보다 5를 기준으로 5와 6을 포함하는 넓이가 더 크다는 것을 발견했습니다. 이는 그리디 접근의 한계를 보여주었습니다.
- '가장 높은 막대 중심' 전략도 [5, 5, 1, 5, 5]와 같은 예시에서 중앙의 1 때문에 전체를 묶지 못하는 문제를 보며 틀렸음을 깨달았습니다.
- "미래를 봐야만 결정 가능한 문제"라는 점을 인지하고, 이를 어떻게 코드로 구현할지 고민했습니다.

핵심 학습 내용

이 문제는 각 막대를 '최소 높이로 하는 최대 구간'을 찾는 문제라는 것을 알게 되었습니다. 즉, 모든 막대를 기준으로 **'자기 자신을 최소 높이로 하는 최대 구간'**을 계산하여 그 중 최대값을 찾는 것이 핵심입니다.

이 문제를 효율적으로 해결하기 위한 핵심 자료구조는 **단조 증가 스택(Monotonic Stack)**입니다.

스택의 역할: 스택에는 항상 높이가 증가하는 막대들의 인덱스만 저장됩니다. 이는 '아직 오른쪽 경계를 만나지 않은 막대들'을 의미합니다.
팝(Pop) 시점: 현재 막대가 스택 top 막대보다 낮아지는 순간, 스택 top 막대는 '오른쪽 경계'를 만난 것이 됩니다. 이 때, 해당 막대를 기준으로 최대 직사각형 넓이를 계산합니다.
왼쪽 경계: pop 후 스택 top은 pop된 막대의 왼쪽 경계가 됩니다.
오른쪽 경계: 현재 막대의 인덱스 currentBarIndex가 오른쪽 경계가 됩니다.
폭 계산: width = currentBarIndex - leftBoundary_idx - 1
- leftBoundary_idx는 pop 후 스택 top (왼쪽 경계)
- currentBarIndex는 현재 막대의 인덱스 (오른쪽 경계)
- -1은 왼쪽 경계 막대와 오른쪽 경계 막대를 폭 계산에서 제외하기 위함입니다.
센티넬(Sentinel): 히스토그램 마지막에 높이 0인 막대를 추가하여, 반복문 끝에 스택에 남아있는 모든 막대들이 pop되도록 유도합니다. 이를 통해 모든 경우의 직사각형 넓이를 계산할 수 있습니다.
핵심 철학: '결정 유예 알고리즘'. 미래를 예측하는 대신, '나보다 낮은 막대가 나올 때까지 결정을 미룬다'는 철학을 통해 문제를 해결합니다.

예시 코드 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while (true) {
        int n;
        cin >> n;
        if (n == 0) break; // 0이면 종료

        vector<long long> histogram(n);
        for (int i = 0; i < n; i++) cin >> histogram[i];

        stack<int> barStack;      // 오른쪽 경계를 아직 만나지 않은 막대들의 인덱스
        long long maxRectangle = 0; // 최대 직사각형 넓이

        // 오른쪽 끝까지 남은 막대 처리를 위해 센티널 0 추가
        histogram.push_back(0);
        n++;

        for (int currentBarIndex = 0; currentBarIndex < n; currentBarIndex++) {
            // 연쇄 pop: 현재 막대보다 높은 막대 제거
            while (!barStack.empty() && histogram[barStack.top()] > histogram[currentBarIndex]) {
                int poppedBar_idx = barStack.top();
                barStack.pop(); // 현재 막대가 pop된 막대를 오른쪽 경계로 막음

                long long height = histogram[poppedBar_idx]; // 면적 계산 기준 높이

                // 왼쪽 경계 = pop 후 스택 top
                int leftBoundary_idx = barStack.empty() ? -1 : barStack.top();

                // 폭 계산: 오른쪽 경계 - 왼쪽 경계 - 1
                long long width = currentBarIndex - leftBoundary_idx - 1;

                // 면적 계산 후 최대값 갱신
                maxRectangle = max(maxRectangle, height * width);
            }

            // 현재 막대 push: 아직 오른쪽 경계를 만나지 않아 살아있음
            barStack.push(currentBarIndex);
        }

        cout << maxRectangle << "\n";
    }

    return 0;
}

이해한 내용

그리디의 함정: 특정 시점의 최적 선택이 전체 최적이 되지 않는다는 점을 확실히 이해했습니다. 이 문제는 '미래를 봐야만 결정 가능한 문제'였기에 그리디 접근이 어려웠습니다.
단조 스택의 원리: 스택을 활용하여 '결정 시점'을 뒤로 미루는 아이디어가 매우 신선했습니다. 스택에 높이가 증가하는 순서대로 인덱스를 쌓아두고, 현재 막대가 더 작아지는 순간 과거의 결정을 확정하는 방식이었습니다.
폭 계산의 정확성: currentBarIndex - leftBoundary_idx - 1 공식이 어떻게 pop된 막대의 최대 가능한 직사각형 폭을 정확하게 계산하는지 이해했습니다. 이는 왼쪽 경계 막대와 오른쪽 경계 막대를 제외하고 그 사이의 인덱스 차이를 이용하는 것입니다.
센티널의 중요성: 마지막에 0을 추가하는 센티넬 기법이 왜 필요한지, 그리고 스택에 남아있는 모든 막대들의 넓이 계산을 어떻게 보장하는지 명확해졌습니다.
엣지 케이스 처리: 높이가 0이거나, 모두 같거나, 급격히 변하는 경우에도 스택 알고리즘이 견고하게 작동한다는 것을 다양한 예시를 통해 확인했습니다.

실전 적용

적용 분야: 히스토그램 문제 외에도, '다음 큰 수/작은 수 찾기', '주식 가격 스팬', '레이저 문제' 등 유사한 패턴을 가진 다양한 알고리즘 문제에 이 단조 스택 기법을 적용할 수 있습니다.
실습 계획:
- 백준 1725번 'N개의 분리된 최대 직사각형' 문제 풀어보기.
- 다른 단조 스택 관련 알고리즘 문제들을 찾아 풀어보며 패턴 익히기.
응용 아이디어:
- 시간 변화에 따른 데이터의 최대 연속 구간(예: 최대 주가 상승률)을 찾는 문제에 적용.
- 이미지 처리에서 특정 색상 영역의 최대 넓이를 찾는 문제에 변형 적용.

추가 학습 계획

깊이 공부할 부분:
- 스택을 활용한 다른 유사 알고리즘 패턴 (Next Greater Element, Largest Rectangle in Histogram 등)을 더 깊이 파악하고 싶습니다.
- 분할 정복 방식과 스택 방식의 근본적인 원리 비교를 더 자세히 해보고 싶습니다.
관련 자료 찾기:
- 알고리즘 관련 유명 서적(예: '알고리즘 문제 해결 전략')에서 단조 스택 관련 챕터 다시 읽기.
- 온라인 강의나 블로그 포스팅에서 다양한 스택 활용 예제 찾아보기.
다음 학습 주제: 스택을 응용한 다른 문제들을 풀면서 알고리즘적 사고력을 확장할 예정입니다.

참고 자료

ChatGPT와의 대화 내용: 문제의 핵심 개념, 알고리즘 구조, 변수 의미, 각 코드 라인의 역할 등에 대한 심도 깊은 설명.
백준 6549번 문제: 문제의 정의와 예제 입력/출력.
C++ STL stack: 스택 자료구조의 기본적인 사용법.

이 문제로 인해 '결정을 미루는 전략'과 '단조 스택'이라는 도구를 얻게 되었습니다.