1. 문제
https://www.acmicpc.net/problem/6549
[
6549번: 히스토그램에서 가장 큰 직사각형
입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, …, hn (0 ≤ hi ≤
](https://www.acmicpc.net/problem/6549)
https://www.acmicpc.net/problem/1725
[
1725번: 히스토그램
첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은
](https://www.acmicpc.net/problem/1725)
히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.
히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.
2. 아이디어
다음 블로그의 내용을 참조하였다.
https://cocoon1787.tistory.com/314
[
[C/C++] 백준 6549번 - 히스토그램에서 가장 큰 직사각형 (분할 정복 & 세그먼트 트리, 스택 풀이)
문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1,
cocoon1787.tistory.com
](https://cocoon1787.tistory.com/314)
전반적인 알고리즘 아이디어는 다음과 같다.
-
다음 사진과 같이 히스토그램 그림이 있을 경우, 세그먼트 트리를 이용해 전체 구간에서 가장 작은 높이의 인덱스를 구한다.
-
구간의 길이(ed - st + 1) * 가장 작은 히스토그램의 높이 값(heights[minIdx - 1])을 구해 현재까지의 가장 큰 넓이(maxSize)와 비교해 만약 그 넓이보다 크다면 maxSize를 갱신한다.
-
가장 작은 높이의 인덱스(minIdx)를 기준으로, 히스토그램을 두 구간으로 나누고, 재귀함수로 각 구간별로 2. 의 과정을 반복한다.
-
만약 구간을 쪼갰을 때 넓이를 구할 수가 없다면 (st > ed로 1인 히스토그램에서 쪼개지는 경우) return한다.
알고리즘이 매우 단순해 처음에는 이걸로 해결할 수 있을지 모르겠지만, 재귀를 반복하다 보면, 결국 그림에서 3, 4번째 히스토그램과 같이 큰 히스토그램만 있는 구간에서 3번째 히스토그램이 가장 작은 높이(4)이므로 4 * 2 = 8로 이를 이용해 구간에서의 넓이를 구하게 된다.
또한, 엄청 높은 히스토그램 하나가 있는 경우에도, 그 막대의 높이 * 구간의 길이(1) = 그 막대의 높이 와 같이 그 막대의 높이를 그대로 사용하므로, 문제를 해결할 수 있다.
3. 개선할 점 및 배운점
특정 구간에서의 특정 값이 필요한 경우 -> 세그먼트 트리 자료구조 사용
부분 문제의 해를 재귀적으로 구하는 것이 전체 문제의 해와 관련이 있는 경우 -> 분할정복 알고리즘 사용