저번 포스터에서 세그멘트 트리를 공부하였다.
이번 문제는 세그멘트 트리 응용 문제이다.
굳이 세그멘트 트리를 사용하지 않아도 되지만 나는 세그멘트 트리를 배운김에 적용해보고 싶었다.
응용까지는 아직 좀 더 공부해야할 것 같다. 생각이 어렵다
문제 요약
히스토그램은 막대 그래프의 일종으로, 각 막대의 높이는 어떤 값을 나타냅니다. 이 문제에서는 모든 막대의 너비가 1이라고 가정합니다. 따라서, 목표는 이 막대들로 구성할 수 있는 직사각형 중에서 가장 큰 넓이를 가진 직사각형을 찾는 것입니다.
문제 접근
###분할 정복
가장 직관적으로 생각해볼 수 있는 방법은 모든 나눌 수 있는 구간의 경우의 수에서 직사각형을 비교하는 것이다. 하지만 이렇게 한다면 굉장히 많은 구간에 대해서 n^2의 탐색을 진행해야하므로 이렇게하면 시간초과가 뜰 것이다.
조금만 생각해본다면 분항 정복 방식으로 접근할 수 있다.
- 구간에서 가장 최솟값을 구해
- 그 최솟값 기준으로 해당 구간만큼 직사각형을 만들고
- 그 최솟값을 제외한 왼쪽 부분, 오른쪽 부분에 대해서 1,2를 반복하면서 진행하면 된다.
최솟값 요소를 제외한 왼쪽,오른쪽 부분 구간만 계속해서 탐색하면 되는 이유는 이전 최솟값은 이전 전체 구간을 기준으로 직사각형을 만드는 값이다. 즉, 해당 구간 요소들을 전체 포함할 때 만들 수 있는 최대값이라는 것이다.
그 최솟값을 포함해서 다른 구간을 만든다면 어처피 전체 구간을 포함한 부분보다 항상 작다.
그러니 그 최솟값을 제외한 구간을 만들어야만 더 큰 직사각형을 만들 수 있는 경우가 나온다.
그래서 그 최솟값 요소 기준으로 오른쪽 왼쪽에 대해서 1,2 과정을 반복하여 독립적으로 최대 직사각형의 넓이를 찾는 것이다.
1. 왼쪽 서브 히스토그램에서 가장 큰 직사각형
2. 오른쪽 서브 히스토그램에서 가장 큰 직사각형
3. 중간에 걸쳐 있는 직사각형으로, 가장 낮은 높이를 가진 막대를 포함하며 왼쪽과 오른쪽 서브 히스토그램을 아우르는 직사각형
재귀를 통해 이 세 경우를 비교하여 가장 큰 값을 갱신해 나가면 된다.
이렇게 진행하면 하나의 최솟값을 제외한 나머지 양쪽 그룹에 대해서만 고려를 하면 되므로 n개의 구간만 탐색하면 된다.
세그멘트 트리
하지만 분할 정복을 통해 구간을 줄이더라도 해당 구간 마다 최소 막대(최솟값)을 구하는 일이 빈번하게 일어나므로 시간 복잡도(O(n))를 줄이는 방법이 필요하다.
이때 쿼리에 logN의 시간복잡도가 소요되는 세그멘트 트리를 사용하면 된다.
세그먼트 트리는 각 구간에 대해 최소 높이를 가진 막대의 인덱스를 저장하여, 그 인덱스의 높이를 기준으로 직사각형을 계산 한후 인덱스를 기준으로 양쪽으로 할 정복 방식을 활영하여 할 수 있다.
세그멘트 트리는 이전 포스터에 자세히 설명해놨으니 헷갈리면 참고 바란다.
코드
import kotlin.math.*
fun main() {
val br = System.`in`.bufferedReader()
val sb = StringBuilder()
while (true) {
val nums = br.readLine().split(" ").map { it.toInt() }
val n = nums.first()
if (n == 0) break
val segmentTree = SegmentTree(nums.drop(1).toIntArray())
sb.append(segmentTree.getMaxArea(0, n - 1)).append("\n")
}
print(sb.toString())
}
class SegmentTree(private val heights: IntArray) {
private val size = heights.size
private val tree: IntArray = IntArray(4 * size)
init {
build(0, 0, size - 1)
}
private fun build(node: Int, start: Int, end: Int) {
// 리프노드에는 인덱스를 저장
if (start == end) {
tree[node] = start
} else {
val mid = (start + end) / 2
build(node * 2 + 1, start, mid)
build(node * 2 + 2, mid + 1, end)
// 부모 노드에는 두 자식 중 높이가 낮은 막대의 인덱스를 저장
tree[node] =
if (heights[tree[node * 2 + 1]] < heights[tree[node * 2 + 2]])
tree[node * 2 + 1]
else
tree[node * 2 + 2]
}
}
private fun query(node: Int, start: Int, end: Int, left: Int, right: Int): Int {
if (right < start || end < left) return -1
if (left <= start && end <= right) return tree[node]
val mid = (start + end) / 2
val m1 = query(node * 2 + 1, start, mid, left, right)
val m2 = query(node * 2 + 2, mid + 1, end, left, right)
if (m1 == -1) return m2
if (m2 == -1) return m1
return if (heights[m1] < heights[m2]) m1 else m2
// 더 낮은 높이를 가진 막대의 인덱스 반환
}
fun getMaxArea(left: Int, right: Int): Long {
val mIndex = query(0, 0, size - 1, left, right)
// mIndex를 최소 높이로 포함하는 최대 직사각형 사이즈
var area : Long = (right - left + 1).toLong() * heights[mIndex]
// mIndex를 제외한 부분에 대해서도 반복
// mIndex 왼쪽에 남은 구간이 있다면
if (left < mIndex) { // 왼쪽 구간에 대한 최대 넓이
area = max(area, getMaxArea(left, mIndex - 1))
}
// mIndex 오른쪽에 남은 구간이 있다면
if (mIndex < right) { // 오른쪽 구간에 대한 최대 넓이
area = max(area, getMaxArea(mIndex + 1, right))
}
return area
}
}
배운점
세그멘트 트리의 응용, 분할정복
연속된 부분에 대해서 그 부분들의 결과로 해답이 필요할 때 분할 정복을 떠올려보자
