트리 알고리즘은 많은 문제들을 효과적으로 해결하기 위해 사용되는 중요한 알고리즘입니다. 그 중에서도 구간 쿼리를 해결하기 위한 세그먼트 트리는 매우 유용한 자료 구조입니다. 이번 포스트에서는 파이썬을 이용하여 구간 쿼리와 세그먼트 트리에 대해 알아보겠습니다.

구간 쿼리란?

구간 쿼리란, 주어진 배열 또는 리스트에서 특정 구간의 값을 조회하는 작업을 의미합니다. 예를 들어, 주어진 리스트에서 두 인덱스 사이의 합을 구하거나, 최소값을 찾는 등의 작업이 구간 쿼리에 해당합니다. 이러한 작업을 효율적으로 처리하기 위해 세그먼트 트리를 사용할 수 있습니다.

세그먼트 트리란?

세그먼트 트리는 완전 이진 트리(complete binary tree)를 기반으로 한 자료 구조입니다. 각 노드는 배열의 특정 구간에 대한 정보를 가지며, 전체 배열에 대한 정보는 루트 노드에서부터 리프 노드까지 내려가면서 계산됩니다.

세그먼트 트리를 사용하면 배열의 특정 구간에 대한 쿼리를 O(logN)의 시간 복잡도로 해결할 수 있습니다. 이는 효율적인 구간 쿼리 작업을 가능하게 합니다.

세그먼트 트리 구현하기

다음은 파이썬을 이용한 세그먼트 트리의 간단한 구현 예시입니다.

class SegmentTree:
    def __init__(self, arr):
        self.arr = arr
        self.tree = [0] * (4 * len(arr))
        
    def build(self, node, start, end):
        if start == end:
            self.tree[node] = self.arr[start]
        else:
            mid = (start + end) // 2
            self.build(2 * node + 1, start, mid)
            self.build(2 * node + 2, mid + 1, end)
            self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]
    
    def query(self, node, start, end, left, right):
        if left > end or right < start:
            return 0
        if left <= start and right >= end:
            return self.tree[node]
        
        mid = (start + end) // 2
        return self.query(2 * node + 1, start, mid, left, right) + self.query(2 * node + 2, mid + 1, end, left, right)

위의 코드에서 build 함수는 세그먼트 트리를 생성하는 함수입니다. query 함수는 주어진 구간에 대한 쿼리를 처리하는 함수입니다. 구체적인 사용 예시와 함께 세그먼트 트리의 사용법에 대해 더 자세히 알아보도록 하겠습니다.

사용 예시

다음은 세그먼트 트리의 사용 예시입니다. 예를 들어, 주어진 리스트에서 특정 구간의 합을 구하는 작업을 수행해보겠습니다.

arr = [1, 3, 5, 7, 9, 11]
st = SegmentTree(arr)
st.build(0, 0, len(arr) - 1)
print(st.query(0, 0, len(arr) - 1, 1, 4))

위의 코드에서 세그먼트 트리를 생성한 후, build 함수를 호출하여 트리를 초기화합니다. 그 다음, query 함수를 호출하여 인덱스 1부터 4까지의 구간의 합을 구합니다. 실행 결과는 24가 출력됩니다.

결론

트리 알고리즘을 활용한 구간 쿼리는 다양한 문제를 효과적으로 해결할 수 있는 중요한 기술입니다. 세그먼트 트리를 이용하면 배열의 구간에 대한 쿼리를 효율적으로 처리할 수 있습니다. 이번 포스트에서는 파이썬을 이용하여 세그먼트 트리를 간단히 구현하고 사용하는 방법에 대해 알아보았습니다. 추가적인 학습을 통해 세그먼트 트리를 더 깊이 이해하고 다양한 문제에 적용해보시기 바랍니다.