2-13. 자료구조: Sparse Table (희소 테이블)

1. 희소 테이블(Sparse Table) 소개

희소 테이블은 데이터의 구간 쿼리(Range Query)를 효율적으로 처리하기 위한 자료구조입니다. 특히, "최솟값 찾기(Minimum Query, Min Query)"나 "최댓값 찾기(Maximum Query, Max Query)"와 같은 구간 쿼리에 특화되어 있습니다. 희소 테이블은 입력 데이터가 불변(immutable)일 때, 즉 데이터가 변경되지 않을 때 매우 강력한 성능을 발휘합니다. 이는 희소 테이블이 전처리 과정을 통해 쿼리에 대한 정보를 미리 계산해두기 때문입니다. 희소 테이블의 핵심 아이디어는 "중복 계산"을 활용하여 쿼리 처리 시간을 줄이는 것입니다.

희소 테이블을 이해하기 위해 몇 가지 중요한 개념을 짚고 넘어가겠습니다.

• 구간 쿼리(Range Query): 주어진 구간 내에서 특정 값을 찾는 쿼리입니다. 예를 들어, 배열 arr이 주어졌을 때, arr[i...j] 구간 내의 최솟값을 찾는 쿼리가 있습니다.
• 불변 데이터(Immutable Data): 데이터가 변경되지 않는 상태를 의미합니다. 희소 테이블은 데이터가 변경되지 않는다는 가정하에 최적화됩니다.
• 전처리(Preprocessing): 쿼리를 빠르게 처리하기 위해 사전에 정보를 계산하는 과정입니다. 희소 테이블은 전처리 과정을 통해 쿼리 처리 시간을 단축합니다.

2. 희소 테이블의 핵심 원리

희소 테이블의 핵심은 "중복되는 구간 정보를 저장하여 쿼리 처리 시간을 단축하는 것"입니다. 이를 위해 희소 테이블은 다음과 같은 두 가지 주요 단계를 거칩니다.

1) 전처리(Preprocessing) 단계

전처리 단계에서는 주어진 배열의 모든 부분 구간에 대한 정보를 미리 계산하여 저장합니다. 일반적으로, 희소 테이블은 2차원 배열 형태로 구현되며, ST[i][j]는 arr[i]부터 시작하여 길이가 2^j인 구간의 최솟값(또는 최댓값)을 저장합니다.

예를 들어, 배열 arr = [2, 5, 1, 4, 9, 3]이 주어졌다고 가정해 봅시다. 희소 테이블 ST를 구성하는 과정은 다음과 같습니다.

• ST[i][0]: 각 원소 자체를 의미합니다. 즉, ST[i][0] = arr[i].
• ST[i][1]: arr[i]부터 길이가 2인 구간의 최솟값입니다. ST[0][1]은 min(arr[0], arr[1]) <mark class="highlight"><strong><u> min(2, 5) </u></strong></mark> 2, ST[1][1]은 min(arr[1], arr[2]) <mark class="highlight"><strong><u> min(5, 1) </u></strong></mark> 1 과 같이 계산됩니다.
• ST[i][2]: arr[i]부터 길이가 4인 구간의 최솟값입니다. ST[0][2]은 min(ST[0][1], ST[2][1]), 즉 min(2, 1) = 1 과 같이 계산됩니다.
• ST[i][3]: arr[i]부터 길이가 8인 구간의 최솟값입니다. 이 예시에서는 배열의 길이가 6이므로, ST[0][3]은 min(ST[0][2], ST[4][2]) 와 같습니다.

전처리 과정의 핵심은 다음과 같은 점화식을 사용하여 ST 배열을 채우는 것입니다.

$$ ST[i][j] = min(ST[i][j-1], ST[i + 2^{j-1}][j-1]) $$

이 점화식은 ST[i][j]를 계산하기 위해 두 개의 하위 구간(ST[i][j-1]과 ST[i + 2^{j-1}][j-1])의 정보를 활용합니다. 이러한 방식으로, 희소 테이블은 작은 구간의 정보를 이용하여 큰 구간의 정보를 효율적으로 계산합니다.

2) 쿼리 처리 단계

쿼리 처리 단계에서는 주어진 구간 [L, R]에 대한 최솟값을 효율적으로 계산합니다. 희소 테이블의 가장 큰 장점은 O(1)의 시간 복잡도로 쿼리를 처리할 수 있다는 것입니다.

쿼리를 처리하는 방법은 다음과 같습니다.

1. k 계산: 구간의 길이에 해당하는 가장 큰 2의 거듭제곱 값을 구합니다. 즉, k = floor(log2(R - L + 1))입니다.
2. 최솟값 계산: ST[L][k]와 ST[R - 2^k + 1][k]의 최솟값을 반환합니다. 이 두 구간은 겹칠 수 있지만, 최솟값을 찾는 데는 문제가 없습니다.

예를 들어, arr = [2, 5, 1, 4, 9, 3]에서 구간 [1, 4]에 대한 최솟값을 찾는다고 가정해 보겠습니다.

1. R - L + 1 <mark class="highlight"><strong><u> 4 - 1 + 1 </u></strong></mark> 4, k <mark class="highlight"><strong><u> floor(log2(4)) </u></strong></mark> 2
2. min(ST[1][2], ST[4 - 2^2 + 1][2]) = min(ST[1][2], ST[1][2])

희소 테이블을 사용하면, 겹치는 구간을 포함하여 원하는 구간의 최솟값을 O(1)의 시간 복잡도로 구할 수 있습니다.

3. 구현 (Python 예시)

다음은 Python을 이용한 희소 테이블 구현 예시입니다. 이 코드는 최솟값 쿼리를 처리하는 희소 테이블을 구현합니다.

import math

def build_sparse_table(arr):
    """
    희소 테이블을 구축하는 함수.

    Args:
      arr: 입력 배열.

    Returns:
      희소 테이블 (2D list).
    """
    n = len(arr)
    k = int(math.log2(n)) + 1  # 로그 값 계산 시, 정수형 변환

    # Initialize sparse table
    st = [[0] * k for _ in range(n)]

    # Base case: 각 원소 자체
    for i in range(n):
        st[i][0] = arr[i]

    # Build sparse table
    for j in range(1, k):
        for i in range(n - (1 << j) + 1): # i 범위: (n - 2^j + 1)
            st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1])
    return st

def query_min(st, L, R):
    """
    구간 [L, R]의 최솟값을 구하는 함수.

    Args:
      st: 희소 테이블.
      L: 구간의 시작 인덱스.
      R: 구간의 종료 인덱스.

    Returns:
      구간 [L, R]의 최솟값.
    """
    k = int(math.log2(R - L + 1))
    return min(st[L][k], st[R - (1 << k) + 1][k])

# 예시 사용
arr = [2, 5, 1, 4, 9, 3]
sparse_table = build_sparse_table(arr)

# 쿼리 예시
L = 1
R = 4
min_value = query_min(sparse_table, L, R)
print(f"구간 [{L}, {R}]의 최솟값: {min_value}")  # Output: 구간 [1, 4]의 최솟값: 1

1) 코드 설명

• build_sparse_table(arr): 입력 배열 arr을 기반으로 희소 테이블을 구축하는 함수입니다. 2차원 배열 st를 생성하고, 각 셀에 min 값을 저장합니다. math.log2 함수를 사용하여 로그 값을 계산합니다.
• query_min(st, L, R): 희소 테이블 st를 사용하여 구간 [L, R]의 최솟값을 찾는 함수입니다. 구간 길이에 해당하는 가장 큰 2의 거듭제곱 값을 계산하고, 해당하는 st의 값을 비교하여 최솟값을 반환합니다.

2) 시간 복잡도

• 전처리 단계: O(N log N)의 시간 복잡도를 가집니다. 여기서 N은 입력 배열의 크기입니다.
• 쿼리 처리 단계: O(1)의 시간 복잡도를 가집니다.

4. 응용 및 활용 사례

희소 테이블은 다음과 같은 분야에서 유용하게 활용될 수 있습니다.

• 최소/최대 쿼리: 구간 내의 최소 또는 최대 값을 빠르게 찾아야 하는 경우.
• RMQ(Range Minimum Query) 문제: 구간 최소 쿼리 문제 해결에 사용됩니다.
• LCA(Lowest Common Ancestor) 문제: 트리에서 두 노드의 최소 공통 조상을 찾는 문제에 희소 테이블을 적용할 수 있습니다.
• DNA 서열 분석: DNA 서열의 특정 구간 내에서 가장 빈번하게 나타나는 서브 시퀀스를 찾는 문제에 활용될 수 있습니다.

5. 주의사항과 트러블슈팅

희소 테이블을 사용할 때 몇 가지 주의해야 할 사항이 있습니다.

• 불변 데이터: 희소 테이블은 데이터가 불변일 때 가장 효과적입니다. 데이터가 빈번하게 변경되는 경우에는 세그먼트 트리와 같은 다른 자료구조를 고려해야 합니다.
• 메모리 사용량: 희소 테이블은 O(N log N)의 메모리 공간을 사용합니다. 데이터의 크기가 클 경우, 메모리 사용량에 유의해야 합니다.
• 구현: 구현 시, 인덱스 계산과 log2 함수의 사용에 주의해야 합니다. 특히, log2 값은 정수형으로 변환해야 합니다.

6. 결론

희소 테이블은 구간 쿼리를 효율적으로 처리하기 위한 강력한 자료구조입니다. 불변 데이터를 대상으로 하는 최소/최대 쿼리에 특히 적합하며, O(1)의 시간 복잡도로 쿼리를 처리할 수 있다는 장점이 있습니다. 희소 테이블의 핵심 원리를 이해하고, 구현 및 활용 사례를 숙지하면 다양한 문제 해결에 도움이 될 것입니다.