알고리즘 대회나 코딩 인터뷰에서 효율적으로 문제를 해결하기 위한 기술 중 하나가 바로 세그먼트 트리(Segment Tree)입니다.
이 글에서는 세그먼트 트리의 기본 개념과 함께 실제 문제를 통해 그 써보는 방법을 알아보겠습니다. 세그먼트 트리는 주로 구간 쿼리 문제에서 매우 유용하게 사용될 수 있습니다.
특히, 구간 합, 구간 최소/최대값, 구간 업데이트 등의 작업을 효율적으로 처리할 수 있습니다.
세그먼트 트리란?
세그먼트 트리는 배열의 구간에 대한 정보를 효율적으로 관리하기 위한 자료구조입니다.
이를 통해 특정 구간에 대한 쿼리 연산 및 업데이트를 로그 시간 복잡도(logarithmic time complexity)로 처리할 수 있습니다.
세그먼트 트리는 일반적으로 이진 트리 형태로 구성되며, 각 노드는 특정 구간에 대한 정보를 저장합니다.
세그먼트 트리의 구조
세그먼트 트리는 아래와 같은 구조로 구성됩니다:
- 리프 노드: 배열의 각 요소를 나타냅니다.
- 내부 노드: 자신의 자식 노드(리프 노드)의 정보를 바탕으로 구간의 정보를 나타냅니다. 예를 들어, 리프 노드들에 대한 합, 최소 혹은 최대값 등을 저장합니다.
문제 소개
자 이제, 세그먼트 트리를 사용하여 해결할 수 있는 알고리즘 문제를 소개합니다.
문제 설명
주어진 정수 배열에서 다음의 두 가지 작업을 효율적으로 처리하는 프로그램을 작성하세요.
- 구간 합 쿼리: 배열의 특정 구간 [l, r]에 대한 합을 계산합니다.
- 구간 업데이트: 배열의 특정 인덱스에 있는 값을 업데이트하고, 이에 따른 변경사항을 반영합니다.
입력 형식
첫 줄에 배열의 크기 N과 쿼리의 수 M이 주어집니다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000)
이후 N개의 정수가 배열에 주어지며, 이후 M개의 쿼리가 주어집니다.
쿼리의 형식은 다음과 같습니다:
- 1 l r: 배열의 인덱스 l에서 r까지의 합을 출력합니다 (1 ≤ l ≤ r ≤ N)
- 2 x y: 배열의 x번째 요소를 y로 업데이트합니다 (1 ≤ x ≤ N, -1,000,000,000 ≤ y ≤ 1,000,000,000)
세그먼트 트리의 구현
이제 C#을 사용하여 위의 문제를 해결하기 위한 세그먼트 트리를 구현해보겠습니다.
using System;
class SegmentTree
{
private int[] tree;
private int size;
public SegmentTree(int n)
{
size = n;
tree = new int[n * 4]; // 세그먼트 트리의 크기
}
// 트리 구축
public void Build(int[] arr, int node, int start, int end)
{
if (start == end)
{
tree[node] = arr[start]; // 리프 노드
}
else
{
int mid = (start + end) / 2;
Build(arr, node * 2, start, mid); // 왼쪽 자식
Build(arr, node * 2 + 1, mid + 1, end); // 오른쪽 자식
tree[node] = tree[node * 2] + tree[node * 2 + 1]; // 부모 노드 업데이트
}
}
// 구간 합 쿼리
public int Query(int node, int start, int end, int l, int r)
{
if (r < start || end < l)
{
return 0; // 합을 구할 수 없는 구간
}
if (l <= start && end <= r)
{
return tree[node]; // 완전 포함
}
int mid = (start + end) / 2;
int leftSum = Query(node * 2, start, mid, l, r);
int rightSum = Query(node * 2 + 1, mid + 1, end, l, r);
return leftSum + rightSum; // 두 구간의 합 반환
}
// 업데이트
public void Update(int node, int start, int end, int idx, int val)
{
if (start == end)
{
tree[node] = val; // 리프 노드 업데이트
}
else
{
int mid = (start + end) / 2;
if (start <= idx && idx <= mid)
{
Update(node * 2, start, mid, idx, val); // 왼쪽 자식 업데이트
}
else
{
Update(node * 2 + 1, mid + 1, end, idx, val); // 오른쪽 자식 업데이트
}
tree[node] = tree[node * 2] + tree[node * 2 + 1]; // 부모 노드 업데이트
}
}
}
class Program
{
static void Main(string[] args)
{
int N, M;
N = int.Parse(Console.ReadLine());
M = int.Parse(Console.ReadLine());
int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
SegmentTree segTree = new SegmentTree(N);
segTree.Build(arr, 1, 0, N - 1); // 세그먼트 트리 구축
for (int i = 0; i < M; i++)
{
string[] query = Console.ReadLine().Split(' ');
int type = int.Parse(query[0]);
if (type == 1)
{
// 구간 합 쿼리
int l = int.Parse(query[1]) - 1;
int r = int.Parse(query[2]) - 1;
Console.WriteLine(segTree.Query(1, 0, N - 1, l, r));
}
else if (type == 2)
{
// 업데이트
int x = int.Parse(query[1]) - 1;
int y = int.Parse(query[2]);
segTree.Update(1, 0, N - 1, x, y);
}
}
}
}
코드 설명
위의 C# 코드는 주어진 문제를 해결하기 위한 세그먼트 트리의 구현입니다.
각 메서드와 클래스에 대한 설명은 다음과 같습니다:
클래스 및 변수를 설명
SegmentTree: 세그먼트 트리를 나타내는 클래스입니다. 배열을 받아 트리를 구축하고, 구간 합 쿼리와 업데이트를 처리합니다.tree: 세그먼트 트리의 배열입니다. 배열의 최대 크기는N * 4입니다.Build: 주어진 배열로부터 세그먼트 트리를 구축하는 메서드입니다.Query: 주어진 구간에 대한 합을 반환하는 메서드입니다.Update: 주어진 인덱스의 값을 업데이트하고, 이에 따른 변경사항을 트리에 반영하는 메서드입니다.
메인 함수 설명
메인 함수에서는 배열의 크기와 쿼리의 수를 입력받고, 주어진 배열로 세그먼트 트리를 구축한 다음, 쿼리에 따라
구간 합을 계산하거나 업데이트를 수행합니다.
결론
이번 글에서는 C#을 이용한 세그먼트 트리의 구현과 구간 합 쿼리 및 업데이트 문제를 해결하는 방법에 대해 알아보았습니다.
세그먼트 트리는 구간 쿼리를 효율적으로 처리할 수 있는 강력한 도구이며, 여러 문제에 적용 가능합니다.
복잡한 쿼리나 업데이트가 요구되는 문제에 직면했을 때, 세그먼트 트리를 고려해보는 것이 좋습니다.
다양한 연습 문제를 풀어보며 이 자료구조의 이해를 깊이 있게 다지길 바랍니다.