Sparse Table (희소 배열) 연구일지

LCA를 공부하다가 LCA를 더 빠르게 구현할 수 있는 것을 알아내고, 이에 필요한 테크닉이 Sparse Table임을 알아냈습니다.

 

공부한 곳 (https://blog.naver.com/kks227/220793361738)

BOJ 17435 (https://www.acmicpc.net/problem/17435)

 

---

22.05.01 연구일지

✔️ Sparse Table이 필요한 이유

다음과 같이 같이 K개의 간선으로 이루어진 Directed Graph가 있다고 했을 때, 1부터 K + 1번 vertex까지 가려면 O(K)가 걸립니다.

vertex는 인접해있는, 즉 한 번 이동했을 때, 어떤 vertex로 가는지 알고 있습니다.

K가 적당한 숫자라면 괜찮지만 엄청나게 큰 수라면 Time Complexity면에서 무리가 갈 수 있습니다.

 

그렇다면 각 vertex들이 2번 이동했을 때의 값을 알고 있다면 어떨까요?

K가 홀수라면 O((K / 2) + 1),

K가 짝수라면 O(K / 2)입니다.

>> 확실히 Time Complexity가 줄어드는 것을 확인할 수 있습니다.

 

이러한 점을 이용하여 각 vertex가 H번 이동한 값들을 안다고 했을 때, K번 이동한다고 가정합니다.

H가 작고, K가 크다면 이는 크게 효율적이지 않습니다.

H가 크고, K가 크다면 이는 효율적으로 작용할 것입니다.

H가 K보다 크다면 H번 이동한 값을 아는 게 쓸모가 없어집니다.

 

H번 이동한 값을 유리하게 쓰는 방법이 어떤 게 있을까요?

>>H가 여러 개라면 더 효율적으로 사용할 수 있습니다.

즉, 각 vertex가 2번 이동한 값, 3번 이동한 값을 안다고 할 때, 보다 효율적으로 K + 1번 노드로 갈 것입니다.

 

하지만, H값이 무작위로 주어진다면 이는 깔끔하지 못할뿐더러 코드가 더러워질 것으로 보입니다.

>> 2의 지수를 사용한다면 깔끔하게 표현할 수 있습니다.

>> 2 ^ 0번, 2 ^ 1번, 2 ^ 2번, 2 ^ 3번

 

즉, Sparse Table은 vertex가 2의 지수만큼 이동한 값을 가지고서 이동 횟수를 줄이면서 시간 복잡도를 줄이는 테크닉입니다.

✔️ Space Complexity

그렇다면 vertex당 2의 지수만큼 이동한 값을 저장하는 배열을 만들어야 합니다. 이는 메모리를 많이 잡아먹을 것 같지만 이동하는 최댓값이 M이라 했을 때, 한 vertex당 O(logM)만큼 차지합니다.

그리고, vertex가 N개라면 O(NlogM)으로 크게 차지하지 않습니다.

 

✔️ Sparse Table Code

Implementation

 

Sparse Table을 코드로 표현해봅시다.

nextt[Vertex의 최대 개수][log(2)Vertex의 최대 개수]로 2차원 배열을 선언하여

i는 vertex, j는 2^j를 뜻하며 value는 i라는 vertex가 2^j만큼 이동했을 때를 나타냅니다.

 

값을 갱신하는 방법은 DP를 사용합니다.

점화식이 뜻하는 말은 Vertex i가 2^j만큼 이동한 것은 Vertex i가 2^(j - 1) 이동한 것에서 2^(j - 1)만큼 더 이동한 것과 같은 말입니다.

이 점화식이 가능하기 위해서는 j만큼 이동한 것을 구할 때, 모든 vertex가 j - 1만큼 이동한 것이 어딘지 알고 있어야 하기 때문에

 

1. 모든 Vertex가 j만큼 이동한 것을 구한다.

2. j + 1만큼 이동한 것을 점화식을 통해 구할 수 있게 된다.

 

와 같은 순서를 가지게 됩니다.

for(int j = 1; j < LOG_MAX; j++){
    for(int i = 1; i <= m; i++){
        nextt[i][j] = nextt[nextt[i][j - 1]][j - 1];
    }
}

 

Use Sparse Table

 

13만큼 이동한다 했을 때 이를 어떻게 구할 수 있을까요?

 

13을 이진수로 나타내면 1101(2)입니다. 이동하는 횟수를 이진수로 나타내고, 켜져 있는 비트가 있을 때, 그 비트만큼 움직여주면 됩니다.

int N, X; cin >> N >> X;
        
for(int j = LOG_MAX - 1; j >= 0; j--){
    if(N >= (1 << j)){ // j(0-based)비트가 켜져있는지 확인
        N -= (1 << j); // 켜져있는지 확인했으므로 꺼준다.
        X = nextt[X][j]; // 비트에 해당하는 수만큼 이동한다.
    }
}

---

Sparse Table이라는 테크닉을 알아보았습니다. 모든 vertex가 outdegree가 1인 상태에서만 사용할 수 있는 테크닉 같습니다.

이제 이 테크닉을 가지고서 LCA 2 (11438)을 풀 수 있습니다.