[삼성 알고리즘] 희소성 테이블 (Separse Table)

1. 내용

희소성테이블은 값의 연산 결과를 테이블에 저장해서 빠르게 값의 결과를 찾아가는 문제로 구간합, 구간 최대,최솟값, 중첩함수 등 문제를 풀 때 빠른 시간내에 해결이 가능하다.

희소테이블은 위 언급한 문제들에 따라 다른 값들을 저장하며 문제 풀이에 효율적인 시간을 제공한다.

 

기본적으로 희소테이블은 2차원배열 table[i][j]로 이루어진다. 그리고 기본적으로 i+2^(j-1)-1 공식을 이용해서 희소성테이블을 만들 수 있다.

 

Ex)

구간합 문제

이 경우에는 table[i][j]가 의미하는 것은 배열 arr이 주어졌을 때 arr[i]에서 arr[2^(j-1)-1]까지 구간의 합이 저장되어있다.

즉 임의의 x,y가주어지고 arr배열의 x~y구간까지의 합을 구한다면 y-x의 길이에 근접한 [log(y-x)] 가우스 정수 값을 구하고 해당 값은

Table[i][j]를 이용해서 O(1)로 알 수 있다. 그리고 그외 구간은 더해주면 된다.

 

위 처럼 구간합 뿐만 아니라 각각 f(x)의 함수식으로 나타낼 수 있는 최소, 최대 중첩 함수 등의 문제에서도 활용이 가능하며 결합법칙의 특징을 이용한 만큼

F(x,y,z) = F(F(x,y),z) = F(x,F(y,z))

공식이 성립하는 조건이 존재한다.

 

2. 구현

알고리즘의 구현에 앞서 희소성 테이블은 2의 거듭제곱을 이용한 i+2^(j-1)-1이 핵심 공식이다.

즉 다시 말해 i와 j값을 바탕으로 희소성 테이블을 만드는 초기화 작업이 필요하다. I는 arr배열의 길이 즉 길이를 N이라할 때

0 <= i <= N-1

이 된다. 그리고 j값은 N을 log(2의 거듭제곱)으로 했을 때 가우스 값으로 얻은 값 즉 logN보다 작으면서 가장 큰 정수 값을 최대 값으로 가진다.

0 <= j <= [logN]

 

위와 같은 범위를 바탕으로 희소성테이블을 만들 수 있고 각 희소성 테이블을 만들 때는 재귀를 이용해서 좀 더 빠르게 구할 수 있다.

 

3. 알고리즘

• 백준(합성함수와 쿼리)

#include<iostream>

#include<cmath>

 

using namespace std;

 

int arr[200001];

int table[200001][20];

 

void query(int n, int& x,int log_n) {

while (log_n != 0 && n>0) {

log_n = (int)(log(n)/log(2));

x = table[x][log_n];

n -= pow(2, log_n);

}

}

int main(void) {

int M,buf,Q,buf2;

cin >> M;

for (int i = 0; i < M; i++) {

cin >> buf;

arr[i] = buf;

table[i][0] = buf;

}

for (int j = 1; j < 19; j++) {

for (int i = 0; i < M; i++) {

table[i][j] = table[table[i][j - 1]-1][j - 1];

}

}

cin >> Q;

for (int i = 0; i < Q; i++) {

cin >> buf >> buf2;

int log_n = 1;

buf2 -= 1;

query(buf, buf2,log_n);

cout << buf2 << endl;

}

return 0;

}