[C++] 희소 테이블(Sparse Table)

희소 테이블(Sparse Table)

• 배열이 정적이어야 한다. 즉, 배열 내용이 수정되면 안 된다.
• 배열의 아이디어는 분할 정복과 비슷하지만 더 빠르다.

 

기본 원리

모든 정점의 간선이 1개인 유향 그래프가 존재할 때 어떤 정점에서 시작해 k번 이동을 하면 도착하는 점은 유일하다. 이때 k번을 일일이 매번 따라가며 도착점을 계산할 수도 있겠지만 k값이 커질수록 시간도 오래 걸릴 것이다.

 

만약 어떤 정점의 n번 이동했을 때 도착점, 또 그 도착점을 정점마다 다 기억하는 배열이 있다면 도착점을 매우 효율적으로 구할 수 있을 것이다.

 

그렇다면 이 배열은 어떻게 가져야 할까?

 

1칸, 2칸, 4칸, 8칸, 16칸,... 등 2진수를 이용해 2진수에 해당하는 이동 값을 모두 배열로 만든다. 그리고 이동 횟수 k를 2진수로 나타냈을 때 켜져 있는 비트에 해당하는 배열만 사용해 건너뛰면 된다. 여기서 뛰는 순서는 상관이 없다. 예를 들어, k가 13(1101(2))이라면 켜져 있는 비트에 해당하는 1칸, 4칸, 8칸 총 3번만 뛰면 된다.

 

문제

 

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

17435번: 합성함수와 쿼리

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    int m;
    cin >> m;

    int f[200001][20]; // f[i][j]: 정점 i에서 2^j번 이동한 후의 정점
    for (int i = 1; i <= m; ++i)
        cin >> f[i][0];

    // 2진수 이동 값을 배열에 채운다.
    for (int j = 1; j < 20; j++)
        for (int i = 1; i <= m; i++)
            f[i][j] = f[f[i][j - 1]][j - 1];

    int q;
    cin >> q;
    while (q--) {
        int n, x;
        cin >> n >> x;

        for (int i = 0; 0 < n; i++) {
            // 켜져있는 비트만 이동한다.
            if (n & 1)
                x = f[x][i];
            n >>= 1;
        }

        cout << x << '\n';
    }
}

 

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

14942번: 개미

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> energys;
vector<pair<int, int>> tunnels[100001];

int parent[100001][20]; // 정점 i에서 2^j번 이동한 후의 정점
int dist[100001][20]; // 정점 i에서 parent[i][j]로 이동하는데 필요한 에너지

void dfs(int start, int index) 
{
    parent[start][0] = index;
    for (pair<int, int> next : tunnels[start])
        if (next.first != index) {
            dist[next.first][0] = next.second;
            dfs(next.first, start);
        }
}

int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> n;
    energys.resize(n);
    for (int i = 0; i < n; ++i)
        cin >> energys[i];
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        tunnels[a].push_back({ b, c });
        tunnels[b].push_back({ a, c });
    }

    // 개미굴을 트리 구조로 만들어 초기화한다.
    dfs(1, 0);

    // 2진수 이동 값을 배열에 채운다.
    for (int i = 1; i < 20; i++)
        for (int j = 1; j <= n; j++) {
            dist[j][i] = dist[j][i - 1] + dist[parent[j][i - 1]][i - 1];
            parent[j][i] = parent[parent[j][i - 1]][i - 1];
        }

    for (int i = 0; i < n; i++) {
        int pos = i + 1, energy = energys[i];
        for (int j = 20 - 1; j >= 0; j--) {
            if (parent[pos][j] != 0 && energy >= dist[pos][j]) {
                energy -= dist[pos][j];
                pos = parent[pos][j];
            }
        }
        cout << pos << '\n';
    }
}