Colin's Blog
[kotlin] 트리 세그먼트 트리(Segment Tree) 자료 구조의 활용

세그먼트 트리(Segment Tree)는 배열이나 리스트와 같은 자료 구조를 이용하여 범위 질의와 수정 작업을 효율적으로 처리하는 데 사용됩니다. 세그먼트 트리는 반복적인 범위 쿼리를 빠르게 수행할 수 있는 자료 구조로, 주로 수열과 같은 자료 구조에 적용됩니다.

세그먼트 트리의 구조

세그먼트 트리는 특정한 자료 구조를 사용하여 데이터를 나무 형태로 저장하고, 이를 활용하여 범위 질의와 수정 작업을 수행하는 방식으로 동작합니다. 세그먼트 트리는 주로 배열을 사용하여 구현되며, 높이가 log(n)인 이진 트리 형태를 가집니다.

세그먼트 트리는 배열의 값들을 이용하여 부분적인 정보들을 계산하고 저장하므로, 주어진 범위에 대한 질의나 수정 작업에 대해 효율적으로 동작합니다.

세그먼트 트리의 활용

세그먼트 트리는 다양한 문제에 사용될 수 있습니다. 예를 들어, 수열에서 특정 구간의 최소값, 최대값, 합계 등을 계산해야 하는 경우에 세그먼트 트리를 사용할 수 있습니다. 또한, 배열의 특정 요소를 변경해야 하는 작업을 빠르게 처리해야 하는 경우에도 세그먼트 트리가 유용합니다.

예시

코틀린을 사용하여 세그먼트 트리를 구현하는 간단한 예시를 살펴보겠습니다.

class SegmentTree(input: List<Int>) {
    private val tree: MutableList<Int> = MutableList(4 * input.size) { 0 }

    init {
        buildTree(input, 0, input.size - 1, 0)
    }

    private fun buildTree(input: List<Int>, start: Int, end: Int, index: Int) {
        if (start == end) {
            tree[index] = input[start]
        } else {
            val mid = (start + end) / 2
            buildTree(input, start, mid, 2 * index + 1)
            buildTree(input, mid + 1, end, 2 * index + 2)
            tree[index] = tree[2 * index + 1] + tree[2 * index + 2]
        }
    }

    fun queryRange(start: Int, end: Int, inputSize: Int): Int {
        return query(start, end, 0, inputSize - 1, 0)
    }

    private fun query(start: Int, end: Int, qStart: Int, qEnd: Int, index: Int): Int {
        if (qStart > end || qEnd < start) {
            return 0
        } else if (qStart >= start && qEnd <= end) {
            return tree[index]
        } else {
            val mid = (qStart + qEnd) / 2
            return query(start, end, qStart, mid, 2 * index + 1) +
                    query(start, end, mid + 1, qEnd, 2 * index + 2)
        }
    }
}

위 예시는 입력으로 주어진 리스트를 이용하여 세그먼트 트리를 구축하는 방법을 보여줍니다. 또한, 트리에 저장된 값을 활용하여 구간 질의를 처리하는 방법도 제공합니다.

요약

세그먼트 트리는 수열과 같은 자료 구조에 대해 범위 질의와 수정 작업을 효율적으로 처리하는 데 사용될 수 있는 자료 구조입니다. 코틀린을 사용하여 세그먼트 트리를 구현하는 방법을 살펴보았으며, 이를 활용하여 다양한 범위 질의를 처리하는 방법도 살펴보았습니다.

이러한 세그먼트 트리는 알고리즘 문제 해결과 같은 다양한 분야에서 유용하게 활용될 수 있습니다.

참고 문헌:

© 2018 Colin. All rights reserved.