안녕하세요! 이번 강좌에서는 데이터 구조 중 하나인 세그먼트 트리에 대해 자세히 살펴보도록 하겠습니다. 세그먼트 트리는 주로 구간 쿼리를 효율적으로 처리할 수 있는 자료구조로, 특히 배열의 구간 합이나 구간 최솟값, 구간 최댓값 등을 구할 때 유용합니다. 이 글에서는 세그먼트 트리에 대한 기본 개념과 구현 방법, 그리고 실전에서 자주 출제되는 문제를 함께 해결해보겠습니다.
1. 세그먼트 트리란?
세그먼트 트리는 배열의 구간 정보를 효율적으로 관리하는데 강력한 도구입니다. 보통 배열의 크기가 N일 때, 세그먼트 트리는 대략 2 * 2⌈log₂(N)⌉의 메모리 공간을 사용합니다. 이는 포화 이진트리 구조를 활용하기 때문입니다. 기본적으로 세그먼트 트리는 다음 두 가지 작업을 효율적으로 수행할 수 있습니다.
- 구간 쿼리: 특정 구간의 정보를 빠르게 가져올 수 있습니다.
- 업데이트: 배열의 특정 요소를 변경한 후, 이로 인해 영향을 받는 구간 정보를 빠르게 갱신할 수 있습니다.
2. 세그먼트 트리의 구조
세그먼트 트리는 노드로 구성되며, 각 노드는 특정 구간을 나타냅니다. 예를 들어, 배열의 인덱스 0부터 N-1까지의 구간을 관리하는 루트 노드가 존재하고, 이 노드는 두 개의 자식 노드를 통해 배열을 절반으로 나누어 관리합니다. 이런 방식으로 배열을 계속 나누면서 각각의 노드가 특정 구간의 정보를 갖게 됩니다.
2.1 노드 정의
각 노드는 다음과 같은 정보를 가집니다:
- 시작 인덱스 (start): 해당 구간의 시작 지점
- 끝 인덱스 (end): 해당 구간의 끝 지점
- 값(value): 해당 구간의 정보를 저장할 변수 (예: 합, 최솟값 등)
3. 세그먼트 트리 생성 및 쿼리
세그먼트 트리를 구현하기 위해서는 먼저 트리를 구성해야 합니다. 이를 위해, 배열을 입력받아 세그먼트 트리 노드를 재귀적으로 생성하는 방법을 사용합니다. 간단한 예로, 구간 합 세그먼트 트리를 만들어보겠습니다.
// Swift Code
class SegmentTree {
var tree: [Int] // 세그먼트 트리를 저장할 배열
var n: Int // 배열 크기
init(_ data: [Int]) {
self.n = data.count
self.tree = Array(repeating: 0, count: 4 * n) // 트리 배열 초기화
buildTree(data: data, node: 1, start: 0, end: n - 1)
}
// 배열의 구간을 사용하여 세그먼트 트리 구성
func buildTree(data: [Int], node: Int, start: Int, end: Int) {
if start == end {
tree[node] = data[start] // 리프 노드에 값 저장
} else {
let mid = (start + end) / 2
buildTree(data: data, node: 2 * node, start: start, end: mid) // 왼쪽 서브트리
buildTree(data: data, node: 2 * node + 1, start: mid + 1, end: end) // 오른쪽 서브트리
tree[node] = tree[2 * node] + tree[2 * node + 1] // 부모 노드 값 갱신
}
}
}
4. 세그먼트 트리 쿼리 처리하기
세그먼트 트리는 이제 구간 합을 계산하는 기능을 추가해야 합니다. 구간 합 쿼리를 처리하기 위해 다음과 같은 함수를 추가하겠습니다:
// 주어진 구간의 합을 구하는 함수
func query(node: Int, start: Int, end: Int, l: Int, r: Int) -> Int {
if r < start || end < l { // 구간이 겹치지 않는 경우
return 0 // 기본값
}
if l <= start && end <= r { // 구간이 완전히 포함되는 경우
return tree[node]
}
let mid = (start + end) / 2
let leftSum = query(node: 2 * node, start: start, end: mid, l: l, r: r) // 왼쪽 서브트리 쿼리
let rightSum = query(node: 2 * node + 1, start: mid + 1, end: end, l: l, r: r) // 오른쪽 서브트리 쿼리
return leftSum + rightSum // 결과 합산
}
5. 세그먼트 트리 업데이트하기
배열의 원소를 업데이트할 수 있는 함수도 추가합니다. 배열의 특정 인덱스를 변경했을 때, 세그먼트 트리의 정보를 신속하게 갱신하는 방법은 다음과 같습니다:
// 배열의 특정 인덱스를 업데이트 하는 함수
func update(node: Int, start: Int, end: Int, idx: Int, value: Int) {
if start == end { // 리프 노드 도착
tree[node] = value // 해당 노드를 업데이트
} else {
let mid = (start + end) / 2
if start <= idx && idx <= mid {
update(node: 2 * node, start: start, end: mid, idx: idx, value: value) // 왼쪽 서브트리 업데이트
} else {
update(node: 2 * node + 1, start: mid + 1, end: end, idx: idx, value: value) // 오른쪽 서브트리 업데이트
}
tree[node] = tree[2 * node] + tree[2 * node + 1] // 부모 노드 값 갱신
}
}
6. 실전 문제 예제
이제 세그먼트 트리의 기본 구조와 쿼리, 업데이트 방법을 살펴보았으니, 실전에서 자주 출제되는 문제를 하나 다뤄보겠습니다. 문제는 다음과 같습니다:
문제 설명
배열이 주어질 때, 다음 질문에 답하시오:
- 구간 [L, R]의 합을 구하라.
- 인덱스 I의 값을 V로 업데이트하라.
입력 형식
N (배열 크기) arr[0], arr[1], ..., arr[N-1] Q (질문 개수) 각 질문은 다음과 같은 형식으로 주어진다: 1 L R (구간 합 쿼리) 2 I V (업데이트 쿼리)
출력 형식
각 구간 합 쿼리에 대해 출력
예제
5 1 2 3 4 5 3 1 1 3 2 2 10 1 1 3
예제 출력 6
7. 문제 해결 과정
- 입력 받은 배열에 대해 세그먼트 트리를 구축합니다.
- 쿼리 타입에 따라, 구간 쿼리일 경우에는 query() 함수를 호출하고, 업데이트 쿼리일 경우에는 update() 함수를 호출합니다.
- 결과를 출력합니다.
// 문제를 해결하는 메인 함수
import Foundation
func main() {
// 입력 처리
let n = Int(readLine()!)!
let arr = readLine()!.split(separator: " ").map { Int($0)! }
let q = Int(readLine()!)!
// 세그먼트 트리 구축
let segmentTree = SegmentTree(arr)
// 쿼리 처리
for _ in 0..
8. 마무리
이번 세그먼트 트리 강좌를 통해 데이터 구조의 중요성과 그 활용 방법을 배웠습니다. 세그먼트 트리는 다양한 구간 쿼리 문제에 효과적으로 사용할 수 있습니다. 더 많은 연습 문제를 통해 세그먼트 트리의 적용 능력을 키우시길 바랍니다. 감사합니다!