고급 자료구조 (Advanced Data Structures)

고급 자료구조는 효율적인 데이터 저장과 검색을 가능하게 하며, 알고리즘 설계의 핵심이 된다. 이 글에서는 대표적인 고급 자료구조들을 정리하고, 간단한 파이썬 예제를 통해 동작 원리를 살펴본다.

---

Trie (트라이)

트라이는 문자열 집합을 저장하고 빠르게 검색할 수 있는 자료구조다.
자동완성, 사전(Dictionary), 검색엔진의 추천 기능 등에 활용된다.

파이썬 예제

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str):
        node = self.root
        for char in word:
            node = node.children.setdefault(char, TrieNode())
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

trie = Trie()
trie.insert("hello")
print(trie.search("hello"))  # True
print(trie.search("hell"))   # False

---

Segment Tree (세그먼트 트리)

세그먼트 트리는 배열의 특정 구간 합, 최소값, 최대값을 빠르게 구할 수 있도록 설계된 자료구조다.
쿼리와 업데이트 연산을 O(log n) 시간에 처리할 수 있다.

파이썬 예제 (구간 합)

class SegmentTree:
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (2 * self.n)
        self.build(arr)

    def build(self, arr):
        # 리프 채우기
        for i in range(self.n):
            self.tree[self.n + i] = arr[i]
        # 내부 노드 채우기
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[i << 1] + self.tree[i << 1 | 1]

    def update(self, idx, val):
        idx += self.n
        self.tree[idx] = val
        while idx > 1:
            idx >>= 1
            self.tree[idx] = self.tree[idx << 1] + self.tree[idx << 1 | 1]

    def query(self, l, r):
        res = 0
        l += self.n
        r += self.n
        while l < r:
            if l & 1:
                res += self.tree[l]
                l += 1
            if r & 1:
                r -= 1
                res += self.tree[r]
            l >>= 1
            r >>= 1
        return res

arr = [1, 3, 5, 7, 9, 11]
st = SegmentTree(arr)
print(st.query(1, 3))  # 3 + 5 = 8
st.update(1, 10)
print(st.query(1, 3))  # 10 + 5 = 15

---

Fenwick Tree (펜윅 트리, Binary Indexed Tree)

Fenwick Tree는 부분 합(prefix sum)을 빠르게 계산하고 업데이트할 수 있다.
쿼리와 업데이트 모두 O(log n) 시간에 처리된다.

파이썬 예제

class FenwickTree:
    def __init__(self, n):
        self.tree = [0] * (n + 1)

    def update(self, idx, delta):
        while idx < len(self.tree):
            self.tree[idx] += delta
            idx += idx & -idx

    def query(self, idx):
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    def range_query(self, l, r):
        return self.query(r) - self.query(l - 1)

ft = FenwickTree(6)
arr = [1, 3, 5, 7, 9, 11]
for i, val in enumerate(arr, 1):
    ft.update(i, val)

print(ft.range_query(2, 4))  # 3 + 5 + 7 = 15

---

Disjoint Set (서로소 집합, Union-Find)

서로소 집합은 원소들이 같은 집합에 속하는지 판별하고, 두 집합을 합치는 연산을 효율적으로 수행한다.
주로 크루스칼 알고리즘(최소 스패닝 트리)에서 사용된다.

파이썬 예제

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 경로 압축
        return self.parent[x]

    def union(self, x, y):
        rootX, rootY = self.find(x), self.find(y)
        if rootX != rootY:
            if self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            elif self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

ds = DisjointSet(5)
ds.union(0, 1)
ds.union(3, 4)
print(ds.find(0) == ds.find(1))  # True
print(ds.find(0) == ds.find(2))  # False

---

Suffix Array & Suffix Tree (접미사 배열과 트리)

접미사 배열과 트리는 문자열 검색 문제를 효율적으로 해결하기 위한 자료구조다.

• 접미사 배열: 문자열의 모든 접미사를 정렬한 배열
• 접미사 트리: 모든 접미사를 포함하는 압축된 트라이

파이썬 예제 (접미사 배열)

def build_suffix_array(s: str):
    suffixes = [(s[i:], i) for i in range(len(s))]
    suffixes.sort()
    return [idx for _, idx in suffixes]

text = "banana"
sa = build_suffix_array(text)
print(sa)  # [5, 3, 1, 0, 4, 2] (사전순 접미사 시작 인덱스)

---

마무리

이 글에서는 Trie, Segment Tree, Fenwick Tree, Disjoint Set, Suffix Array와 같은 고급 자료구조를 살펴보았다.
이 자료구조들은 단순히 데이터를 저장하는 것을 넘어서 빠른 검색, 효율적인 갱신, 문자열 처리, 그래프 알고리즘 최적화 등 다양한 분야에서 활용된다.