종이 1000장의 두께를 만들고 싶다면 어떻게 할까요?
단순하게 종이 1000장을 쌓으면 됩니다.
하지만 종이 1000장을 쌓는 것(\(1 \times 1000\))보다 더 빠르고 편한 방법이 있습니다.
바로 종이 1장을 10번 접는 것(\(2^{10}\))입니다.
1. 희소 배열(Sparse Table)
위와 같은 갈림길이 없는 순환 그래프가 있습니다.
어떤 정점에서 1000번 이동하면 어떤 정점에 도착할까요?
종이 접기 문제처럼 1000번을 이동하는 대신 2의 제곱수로 건너 뛰며 빠르게 확인할 수 있는 방법이 있습니다.
각 정점에서 간선을 통해 1번 이동하여 도착하는 다음 정점을 표로 나타내면 다음과 같습니다.
| 출발 정점 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1회 이동 | 5 | 7 | 7 | 3 | 4 | 3 | 1 |
한 번 더 작성하면 다음과 같습니다.
| 출발 정점 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1회 이동 | 5 | 7 | 7 | 3 | 4 | 3 | 1 |
| 2회 이동 | 4 | 1 | 1 | 7 | 3 | 7 | 5 |
작성을 하다보니 전에 작성한 표를 활용하여, 도착한 정점이 다시 출발 정점이 되어 다음 정점을 구하면 편합니다.
다시 말하면 1회 이동, 2회 이동의 두 줄은 출발 정점, 1회 이동의 두 줄과 순서만 다르고 값은 같습니다.
이 과정을 반복하여 4회 이동까지 표를 구하면 다음과 같습니다.
| 출발 정점 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1회 이동 | 5 | 7 | 7 | 3 | 4 | 3 | 1 |
| 2회 이동 | 4 | 1 | 1 | 7 | 3 | 7 | 5 |
| 3회 이동 | 3 | 5 | 5 | 1 | 7 | 1 | 4 |
| 4회 이동 | 7 | 4 | 4 | 5 | 1 | 5 | 3 |
앞서 1회 이동, 2회 이동의 두 줄이 출발 정점, 1회 이동의 두 줄과 같았던 것과 마찬가지로
2회 이동, 4회 이동의 두 줄은 출발 정점, 2회 이동의 두 줄과 순서만 다르고 값은 같게 됩니다.
이제 이 방법을 바로 적용시키면 8회 이동의 결과도 한 번에 확인할 수 있습니다.
| 출발 정점 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| ... | |||||||
| 4회 이동 | 7 | 4 | 4 | 5 | 1 | 5 | 3 |
| ... | |||||||
| 8회 이동 | 3 | 5 | 5 | 1 | 7 | 1 | 4 |
불필요한 열을 제외하고 처음부터 표를 그리면 다음과 같습니다.
| 출발 정점 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1(\(2^{0}\))회 이동 | 5 | 7 | 7 | 3 | 4 | 3 | 1 |
| 2(\(2^{1}\))회 이동 | 4 | 1 | 1 | 7 | 3 | 7 | 5 |
| 4(\(2^{2}\))회 이동 | 7 | 4 | 4 | 5 | 1 | 5 | 3 |
| 8(\(2^{3}\))회 이동 | 3 | 5 | 5 | 1 | 7 | 7 | 5 |
| 16(\(2^{4}\))회 이동 | 5 | 7 | 7 | 3 | 5 | 5 | 7 |
| ... |
이렇게 그려지는 표를 희소 배열(Sparse Table)이라고 합니다.
이 표의 두 번째 줄부터 구하는 방법을 점화식으로 나타내면
N번째 줄의 M번째 칸 = N-1번째 줄의 ( N-1번째 줄의 M번째 칸 )번째 칸
으로 나타낼 수 있습니다.
2. 2의 제곱수가 아닌 n만큼 이동하는 법
이제 희소 배열을 통해 2의 제곱수 만큼 이동한 정점은 빠르게 구할 수 있습니다.
그러나 2의 제곱수가 아닌 1000번을 이동한 정점을 구하려면 어떻게 해야할까요?
정답은 위에서 3회 이동한 결과 값을 표에 입력하는 과정을 통해 알 수 있습니다.
3회 이동한 결과를 구하기 위해서 2회 이동한 결과에서 다시 1회 이동하는 결과 표를 이용하여 구하였습니다.
결국 n번 이동한 결과는 n을 2의 제곱수의 합으로 나타내어 희소 배열을 이용하면 됩니다.
1000은 512(\(2^{9}\)) + 256(\(2^{8}\)) + 128(\(2^{7}\)) + 64(\(2^{6}\)) + 32(\(2^{5}\)) + 8(\(2^{3}\))으로 나타낼 수 있습니다.
따라서 예를 들어 정점 1에서 1000번 이동한 결과는 희소 배열에서,
(3+1)번째 줄의 ((5+1)번째 줄의 ((6+1)번째 줄의 ((7+1)번째 줄의 ((8+1)번째 줄의 ((9+1)번째 줄의 1번째 칸)번째 칸)번째 칸)번째 칸)번째 칸)번째 칸
으로 나타낼 수 있습니다.
이 과정을 통해 1000번의 계산을 하지 않고, 희소 배열 10줄을 그리는 단계와 표에서 단 6번의 이동을 통해서 빠르게 구해낼 수 있습니다.
