BOJ 6549, 히스토그램에서 가장 큰 직사각형(분할정복을 이용한 풀이)

아주 유명한 분할 정복 문제입니다. Stack을 사용해서 풀 수 있는 문제이기도 하지만, 문제 테마가 분할정복이니 분할정복을 이용한 풀이로만 소개하겠습니다.

분할 정복 (Divide and Conquer)이란?

문제를 같은 속성을 지닌 부분 문제로 쪼개서 각개격파 하는 방법으로, BruteForce(모든 경우의 수를 다 탐색하는 방법)로 푸는 것 보다 일반적으로 매우 빠릅니다.

그럼 이 문제는 어떻게 분할 정복을 해야할까요?

분할 정복을 사용할 부분 문제를 찾기 위해서는, 먼저 가장 큰 문제를 봐야합니다.

가장 큰 문제는 무엇일까요?

"입력으로 주어진 히스토그램에서, 가장 큰 직사각형을 구하는 프로그램을 작성하시오" 입니다.

결국 우리가 풀어야 할 문제는 [0,n) 사이의 히스토그램에서 최대 넓이의 직사각형을 찾는 것입니다.

가장 편한 방법은 Brute Force의 방법입니다.

 > 너비가 1인 막대 중에서 가장 큰 직사각형 찾기 [0,0] [1,1] ...

 > 너비가 2인 막대 중에서 가장 큰 직사각형 찾기 [0,1], [1,2], [2, 3] ...

 > 너비가 3인 막대 중에서 가장 큰 직사각형 찾기 [0,2], [1,3], [2, 4] ...

...

이런식으로 문제를 해결하는 것이죠.

하지만, n의 범위가 [1, 100000]이기 때문에 시간복잡도 상으로, 제한 시간 안에 해결할 수 없습니다.

그럼 분할 정복은 어떻게 하는 것일까요?

큰 문제를 알았으니 작은 문제를 써 봅시다.

[0, n)까지의 히스토그램 중, 가장 큰 직사각형의 넓이.

  = max ( [0,n/2) 히스토그램 중 가장 큰 직사각형의 넓이, [n/2,n) 히스토그램 중 가장 큰 직사각형의 넓이 )

이고

 이렇게 쪼갠 문제들은 다시 또 반으로 쪼갤 수 있습니다.

그림으로 설명해드리죠

이런 식으로 문제를 쪼갤 수 있습니다. 탐색해야하는 총 Level 수는 lgN이고,

각 레벨을 탐색하는데 걸리는 시간은 N이므로, O(N lgN)의 시간복잡도로 이 문제를 쉽게 해결 할 수 있습니다.

하지만,분할 정복 문제에서는 가장 큰 맹점이 있습니다. 문제를 분할한다는 것은 좋지만, 반드시 가장 넓이가 큰 직사각형이 왼쪽이나 오른쪽으로 나눈 히스토그램 범위 안에 존재한다는 보장이 없다는 것입니다.

이를 위해, 반으로 나눈 뒤, 두 범위에 걸쳐 있는 직사각형이 있나 없나 한번 살펴야합니다. 이는 left = n/2, right = n/2로 설정한 뒤, 다음 히스토그램의 높이가 높은 쪽으로(오른쪽이든 왼쪽이든) 계속 한 칸씩 이동시키면서 계산해야합니다. 그림으로 설명을 하자면.

보라색 막대가 그려진 순서대로 탐색을 하면 됩니다. 높이가 같은 경우엔 어느쪽으로든 진행해도 됩니다. 어차피 넓이를 구하는데 걸리는 시간은 O(1)이고, 구간을 탐색하는데 걸리는 시간은 O(N)이므로,

O(NlgN + N) = O(NlgN)에 문제를 해결할 수 있음은 변하지 않습니다.