Sparse Table - 희소 배열

희소 배열 (Sparse Table) 은 그래프 상에서 N번째 앞에 있는 정점을 빠르게 찾을 수 있는 자료 구조 기법이다.

 

다음과 같은 유향 그래프가 있다고 가정해보자. 모든 정점은 나가는 방향의 화살표를 1개 가지고 있다. 이 모든 정점에서 1번 이동했을 때의 정점은 각각 어디일까?

 

0번 이동	1	2	3	4	5	6	7
1번 이동	2	3	6	5	2	4	6

 

이와 같은 결과를 얻을 수 있다. 화살표를 따라가다 보면 2번 이동했을 때, 3번 이동했을 때... 도 얻어낼 수 있다.

0번 이동	1	2	3	4	5	6	7
1번 이동	2	3	6	5	2	4	6
2번 이동	3	6	4	2	3	5	4
3번 이동	6	4	5	3	6	2	5

 

 

이를 코드로 표현하면 다음과 같다.

n = 7 # 정점 개수
m = 3 # 3번 이동했을 때

table = [[0 for _ in range(n+1)] for _ in range(m+1)]
table[0] = [0, 1, 2, 3, 4, 5, 6, 7]
table[1] = [0, 2, 3, 6, 5, 2, 4, 6] # 1번 이동한 결과

for i in range(2, m+1):
  for j in range(1, n+1):
    # table[i][j] : j번 노드에서 i번 이동한 결과
    # table[1][ table[i-1][j] ] : "j번 노드에서 i-1번 이동한 노드"에서 1번 이동한 결과
    table[i][j] = table[1][table[i-1][j]]

for i in range(m+1):
  print(' '.join(map(str, table[i][1:])))

1 2 3 4 5 6 7
2 3 6 5 2 4 6
3 6 4 2 3 5 4
6 4 5 3 6 2 5

 

주요 아이디어는 "j번 노드에서 i번 이동한 결과는, j번 노드에서 i - 1번 이동한 결과 에서 1번 더 이동한 결과"이다. j번 노드에서 2번 이동한 결과는 j번 노드에서 1번 이동한 결과에서 1번 더 이동한 결과이고, j번 노드에서 4번 이동한 결과는 j번 노드에서 3번 이동한 결과에서 1번 더 이동한 결과이다. 단순한 테이블에서는 table[1] 로도 i번 이동한 결과를 구할 수 있다.

 

하지만 이러한 이동의 횟수와 정점의 개수가 많아진다면, 하나하나 순차적으로 i번 이동한 결과를 찾고 저장하는 것에 무리가 온다. 그렇기에 희소 배열을 사용한다.

 

희소 배열의 아이디어를 얻어보자.

 

2번 노드에서 30번 이동한 결과를 구한다고 가정해보자. 위의 코드에서 m 값을 30으로 바꾼 뒤 실행하면 2번 노드에서 30번 이동한 결과는 2이다.

 

하지만 이 방식은 이동을 30번 진행했다. 우리는 앞으로 수많은 이동을 진행하기 위해 30번을 적은 횟수로 최적화시켜 건너갈 것이다. 배열 데이터에 적은 양을 저장해놓으면서도, 많은 수의 이동을 진행할 수 있는 방법이 없을까?

 

여기서 비트 이론을 사용할 수 있다. 30을 2진수로 표현하면 11110 이다. 즉 30은 16 + 8 + 4 + 2 의 결과이다.

다른 수도 마찬가지이다. 112는 1110000 으로 64 + 32 + 16 으로 만들어진다.

희소 배열에 i번 이동했을 때의 결과를 저장할 때, 2의 제곱꼴로 저장하면 이를 조합하여 많은 수의 이동을 만들어 낼 수 있다.

 

2의 제곱꼴로 저장하기 위해서, 1번 이동했을 때의 결과에서 1번 더 이동했을 때 (-> 2번), 2번 이동했을 때의 결과에서 2번 더 이동했을 때 (-> 4번), 4번 이동했을 때의 결과에서 4번 더 이동했을 때 (->8번) ... 과 같이 배열에 저장되도록 코드를 수정한다.

n = 7 # 정점 개수

table = [[0 for _ in range(n+1)] for _ in range(20)] # 2^19 번 이동한 결과까지
table[0] = [0, 1, 2, 3, 4, 5, 6, 7]
table[1] = [0, 2, 3, 6, 5, 2, 4, 6] # 1번 이동한 결과

for i in range(2, 20):
  for j in range(1, n+1):
    # table[i][j] : j번 노드에서 i번 이동한 결과
    # table[i-1][ table[i-1][j] ] : "j번 노드에서 i-1번 이동한 노드"에서 i-1번 이동한 결과
    table[i][j] = table[i-1][table[i-1][j]]

for i in range(4):
  print(' '.join(map(str, table[i][1:])))

1 2 3 4 5 6 7
2 3 6 5 2 4 6
3 6 4 2 3 5 4
4 5 2 6 4 3 2

 

4 5 2 6 4 3 2 는 2^2 로, 4번 이동했을 때의 결과이다. 수정한 코드를 더 수정해서 30번 이동했을 때의 결과를 구해보자.

 

n = 7 # 정점 개수

table = [[0 for _ in range(n+1)] for _ in range(20)] 
table[0] = [0, 1, 2, 3, 4, 5, 6, 7]
table[1] = [0, 2, 3, 6, 5, 2, 4, 6] # 1번 이동한 결과

for i in range(2, 20):
  for j in range(1, n+1):
    # table[i][j] : j번 노드에서 i번 이동한 결과
    # table[i-1][ table[i-1][j] ] : "j번 노드에서 i-1번 이동한 노드"에서 i-1번 이동한 결과
    table[i][j] = table[i-1][table[i-1][j]]

num = 30
ans = 2
for i in range(20):
  if num & (1 << i) != 0:
    ans = table[i+1][ans]

print(ans)

2

 

이렇게 2진수를 이용해 2의 제곱꼴로 분해하여 저장한다면, 이동 횟수를 확연하게 줄일 수 있다.

 

---

출처

[Tistory]Sparse Table

Sparse Table