백준 6549 히스토그램에서 가장 큰 직사각형

문제보러가기

https://www.acmicpc.net/problem/6549

히스토그램에서 가장 큰 직사각형

흥미로운 문제다

생각의 진행은 다음과 같다.

Main Think.

[l ,r] 특정 구간내의 가장 큰 직사각형은 무엇인가?

김 : 가장 높이가 낮은 것을 기준으로  *(r-l+1) 가로길이 를 하면된다.

정 : 그렇겐 할 수 없다. 그렇게 푼다면 O(n)의 솔루션이 가능하다. 반례는 쉽게 구할 수 있다. 가로 길이가 2인 것을 직사각형 set을 생각하고 h 배열이 다음과 같다고 해봐라 [1, 1,000,000] 가장 큰 직사각형은 2인가? 1,000,000 인가?

김 : 내 솔루션이 틀렸다는걸 이해했다. 그러면 다음과 같이 해보자. 이건 조합문제라고 생각한다. 어쨌든 모든걸 시도하지 않으면 정답을 찾을 수가 없는 구조이다. 

정 : 모든 걸 시도하지 않으면 정답을 찾을 수가 없다는 건, 나도 동의한다.

김 : 다음과 같이 생각 해보자. (0-based) [0, n-1] 구간까지의 건전한 (건설가능한) 직사각형은 무엇인가? 결국엔 가장 높이가 낮은 것을 기준으로 (n) 가로길이 만큼 늘어뜨린 직사각형일 것이다.

정 : 맞다.

김 : 음.. 잠깐! 방금 말하면서 무엇인가 생각났다. 어떤 큰 직사각형이든 간에 [0, n-1] 구간안에 존재해야한다. 이 솔루션은 어떤가?

 [0, 0], [0, 1], [0, 2] ... [0, n-1], [1, 1], [1, 2], [1, 3] ... [1, n-1], [2, 2], [2, 3] .... [2, n-1]  ... [n-1, n-1] 를 순회하자.

그리고 그 구간내에 가장 작은 높이의 막대를 기준으로  *(r-l+1) 를 하는 것이다. 

이렇게 하면 어쨌든 간에 정답을 구할 수 있다!.

정 : 굉장한 진전이다. 그렇게 하면 모든 경우의 수를 완벽히 탐색하므로 정확하게 정답을 구해낼 수 있다. 하지만 탐색하는 경우의 수는 어떤가?

김 : 끄응... 구간 내에 가장 작은 높이의 막대를 뽑아 내는것은 naive한 선형탐색은 O(n), 세그먼트 자료구조를 쓰면 O( log n ) 에 가능하다. 하지만 [0, n-1]의 모든 조합 구간을 순회하는것은 O(n^2) 이다. 따라서 내가 제시한 알고리즘은 O (n^2 * log n) 이다.

정 : 정확하다. 이미 훌륭한 접근이지만, 시간복잡도를 위해 김의 솔루션에서 조금 살을 보태겠다. [0, n-1] 이라는 임의의 직사각형 set을 생각해보자. 그리고 [l, r] 구간을 탐색한다고 하자. 그리고 a (l<= a <= r 를 만족함) 에서 가장 낮은 높이가 있다고 하자. 

김, 당신의 접근방법에서는 [l, a]를 탐색한다. a가 [l, r] 구간중 가장 낮은 것이라면, [l, a] 안에서 가장 높이가 낮은 사각형을 찾아 (a-l+1) 가로길이를 곱하는 수행을 할 필요가 있나?

a가 가장 낮은 높이일 때  { [l, a] : a *(l-a+1) } <= { [l, r] : a * (l-r+1) } 임은 자명하다.

a를 포함한 구간들 [l, a], [l+1, a] ... [a, a], [a, a+1], [a, a+2] .. [a, r], [l+1, r-1], [l+2, r-2], ... 등등의 구간은 조사할 필요가 있을까?

김 : 와.. 생각해보니, 그럴필요가 없다. 

그럼 내가 한번 마지막으로 정리해봐도 되나?

일단은 [0, n-1] 에서 가장 작은 높이를 찾는다. 이 작업은 세그먼트 트리를 이용해 log (n) 안에 수행된다. [0, n-1] 중 가장 작은 높이의 인덱스를 a 라고 하자. 그러면 나는 [0, a-1], [a+1, n-1] 에서 다시 가장 작은 높이를 찾으면 되는 것이다.

그리고 이 행위는 재귀적으로 계속 반복되고, 해당 재귀 함수 하나 하나는 자기가 찾은 가장 작은 높이 * (자신이 탐색하고 있는 구간의 길이) 를 가지고 있으면된다.

이 재귀의 책임은 , 즉 반환값은 자기 구간에서 가장 큰 직사각형의 넓이이다. 

그리고 자식 재귀들로부터 자식들이 찾아낸 가장 큰 직사각형 것들과 비교해서 가장 큰 녀석들을 반환하면 된다... !

***************

정 : 정답입니다. 조금 어려운 문제죠.

김 : 조금이 아닌데요? 켁... 보통 전공생들 중에는 이걸 푸는 사람들이 별로 없을거에요!... 

정 : 음 ... 그렇긴 해요. 하지만 공부만하면 금방 할 수 있을거에요. 물론 제한 시간 내에 이렇게 생각을 진전해나갈 수 있는 사람들은 이미 잘 훈련한 수준의 실력자들이에요. 

CLRS 책에서 분할정복파트에 이 문제가 있는 것을 보았어요. 하지만 제가 기억하기론 백준에서의 문제는 더 가혹한 조건이죠. 그래서 세그먼트 사용을 하는 것이 좋아요.

물론 이 접근법 말고도 다른 몇 개의 접근법이 있긴하지만, 여전히 세그먼트 트리 응용문제로 좋은 것 같네요.

김 : 오늘도 좋은걸 배웠네요

소스보러가기

https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/6549.cc

흠..

이런 방식으로 쓰는것이 읽기에 더 쉽고 공감가지 않을까 고민하며 써봤다.