[알고리즘/파이썬] Sparse Table 희소 테이블 알아보기(코드)

Sparse table의 역할

배열에 대한 다양한 구간 쿼리를 할 수 있다. 생성에는 O(NlogN)이지만, 구간 쿼리는 O(1) (또는 O(logN))에 수행할 수 있다.

구간 쿼리에 대한 알고리즘으로 세그먼트 트리가 있는데, 그 역할과 매우 유사하다. 참고로 세그먼트 트리는 O(NlogN)시간에 생성하고 쿼리 처리는 O(logN)에 가능하다. 차이점이라면 세그먼트 트리는 mutable(변경 가능)한 자료구조이지만 sparse table은 immutable(변경 불가능)한 자료구조이다.

 

 

Sparse table의 원리

sparse table은 위의 그림과 같이 2차원 배열을 갖게 된다. 이때 열 갯수는 배열 길이가 N일때 [logN]을 해주면 된다.

 

테이블이 어떤 방식으로 구성되어 있는 지 알아보자.

sparse table의 가장 첫 행에는 기존의 배열이 오게된다.

그 아래 i번째 배열부터는 위의 그림처럼 i-1번째 배열의 일부분을 통해 만들어진다.

 

예를 들어 최솟값 정보를 담고 있는 sparse table이라 해보자.

table[1][5]는 table[0][5]와 table[0][6]을 통해 만들 수 있다. 이러면 table[1][5]는 원래 배열의 5, 6번째 정보를 모두 커버하는 최솟값을 담고 있게 된다. 

같은 방식으로 table[2][5]는 table[1][5]와 table[1][7]을 통해 만들 수 있다. 이러면 table[2][5]는 원래 배열의 5, 6, 7, 8번째 정보를 모두 커버하는 최솟값을 담고 있게 된다.

table[3][5]는 table[2][5]와 table[2][9]을 통해 만들 수 있다. 이러면 table[3][5]는 원래 배열의 5, 6, 7, 8, 9, 10, 11, 12번째 정보를 모두 커버하는 최솟값을 담고 있게 된다.

 

무슨 원리인지는 알겠는데, 어떻게 써먹어야 할 지 감이 안온다!! 이게 어떻게 쿼리를 O(1)에 해결하지?

 

예시1)

누군가가 배열 전체의 최솟값을 물어봤다고 해보자. 즉 0번째 정보부터 18번째 정보까지 모두 커버하는 최솟값을 찾아야 한다. sparse table에서 table[4][0]은 0~15번째 정보를 담고 있고 table[4][3]은 3~18번째 정보를 담고 있으므로

min(table[4][0], table[4][3])이 전체 배열을 커버하는 최솟값이 된다.

 

예시2)

또 다른 예시로 누군가가 배열의 부분 구간인 5~15에서의 최솟값을 물어봤다고 해보자. 즉 5번째 정보부터 15번째 정보까지 모두 커버하는 최솟값을 찾아야 한다. sparse table에서 table[3][5]은 5~12번째 정보를 담고 있고 table[3][8]은 8~15번째 정보를 담고 있으므로 min(table[3][5], table[3][8])이 5~15 구간 배열을 커버하는 최솟값이 된다.

아니 그럼 a, b는 어떻게 찾으라는 거야!!

 

구간 left, right가 주어졌다고 해보자. 그리고 일단 몇번째 행인지를 나타내는 i도 일단 알아냈다고 해보자.

그럼 이때 a = table[i][left] 인 것은 비교적 쉽게 알 수 있다. 열이 left이어야 left부터 커버하기 때문이다. 그럼 b는?

i번째 행에서 커버하는 개수는 2**i개다. 위의 그림에서도 3번째 행은 2**3=8개를 커버하고 있다.

이것을 이용해보면, right까지 커버하는 b는 right+1-2**i번째 열에 있다. 따라서 b는 table[i][right+1-2**i]이다.

그럼 이때 i값은 무엇일까? i는 구간 길이를 N이라 할때 [logN]이다. 그래야 2개 값 비교만으로 구간 전체를 커버할 수 있기 때문이다.

 

 

Sparse table 구현

딱 sparse table만 써도 풀리는 문제를 갖고 연습해보자.

https://www.acmicpc.net/problem/10868

10868번: 최솟값

위의 문제는 세그먼트 트리로도 풀 수 있으나, 배열이 변하지 않으므로 희소 테이블로 풀면 더 빠른 시간 내에 통과가 가능하다. 

 

아래는 희소 테이블 구현 코드다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
nums = []
for _ in range(n):
    nums.append(int(input()))

# height table
h = [0 for _ in range(n+1)]
h[1] = 0
for i in range(2, n+1):
    h[i] = h[i>>1] + 1

# sparse table
table = [[-1 for _ in range(n)] for _ in range(h[-1]+1)]
for i in range(n):
    table[0][i] = nums[i]

step = 1
for i in range(1, len(table)):
    for j in range(n):
        if j + step < n:
            table[i][j] = min(table[i-1][j], table[i-1][j+step])
    step = step << 1

# query
def query(left, right):
    r = h[right-left+1]  # find row
    return min(table[r][left], table[r][right + 1 - (1<<r)])


for _ in range(m):
    a, b = map(int, input().split())
    print(query(a-1, b-1))

코드를 하나씩 뜯어보자.

 

 

1. h 테이블 만들기

# height table
h = [0 for _ in range(n+1)]
h[1] = 0
for i in range(2, n+1):
    h[i] = h[i>>1] + 1

쿼리를 처리할때 구간 길이 L을 갖고 [logN]을 구해야 되는데, 이 정보들을 미리 구해놓은 것이다. 

아래는 n=10일때 h의 결과다. h[1]=0, h[2]=1, h[4]=2, h[8]=3임을 확인 할 수 있다.

[0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3]

 

 

2. 희소 테이블 만들기

# sparse table
table = [[-1 for _ in range(n)] for _ in range(h[-1]+1)]
for i in range(n):
    table[0][i] = nums[i]

step = 1
for i in range(1, len(table)):
    for j in range(n):
        if j + step < n:
            table[i][j] = min(table[i-1][j], table[i-1][j+step])
    step = step << 1

table의 열 길이는 n, 행 길이는 [logn]+1이 된다. 원래 배열도 담아야하므로 +1을 해준 것이다.

step을 2배씩 증가시켜주면서 적절히 테이블 값을 채워넣는다. 위에서 설명한 원리 그대로 실행하는 것이다.

 

 

3. 쿼리 처리하기

# query
def query(left, right):
    r = h[right-left+1]  # find row
    return min(table[r][left], table[r][right + 1 - (1<<r)])

쿼리 처리도 위에서 설명한 것 그대로 코드를 짠 것이다.

h테이블을 이용하여 빠르게 r을 구하고, 이 r은 테이블의 열 번호로 사용하면 된다.

 

 

Sparse table 주의점(중요!!!)

조심해야할 것이 한가지 있는데, 만약 최솟값을 찾는 게 아니고 sum을 찾는 경우였다면 위와 같은 로직을 적용할 수 없다. 쿼리 처리 함수를 잘 보면 두 값을 합쳐서 최솟값을 구하든, 최댓값을 구하든 요구되는 로직을 실행하는 구조인데,

만약 sum일때 이 두 값을 합쳐버리면 중복되어 더해지는 일이 발생한다.

왜냐면 두 값이 커버하는 구간이 일부 겹치기 때문이다.

이때는 커버 구간이 겹치지 않게끔 해줘야 답을 제대로 구할 수 있고, 이 경우 시간도 O(1)이 아니라 O(logN)에 해결할 수 있다.

 

예시)

sum을 구하라는 게 문제고, 구간은 3~13이라 해보자. 배열 길이는 11이 된다.

모든 수는 2의 거듭제곱의 합으로 표현할 수 있으므로 11은 8+2+1로 표현된다.

이렇게 분해를 하고 나면 각각은 모두 2의 거듭제곱이므로 적절한 값을 테이블에서 찾을 수 있다. 

코드)

def sum(left, right):
    if left > right:
        return 0

    length = right - left + 1

    val = 0
    while length > 0:
        last_bit = length & -length
        level = h[last_bit]
        val += table[level][left]

        left += last_bit
        length -= last_bit
    return val

 

 

 

Sparse table의 활용

희소 테이블은 그 제작 원리가 다른 문제에도 잘 활용되니, 다음을 풀어보자.

https://www.acmicpc.net/problem/3117

3117번: YouTube