스파스 테이블 (sparse table) : 2의 거듭제곱 단위로 점프한다.

 이런 문제를 생각해 보겠습니다.

 

 

 뭔가 많이 본 거 같은데, 효율적으로 풀기는 쉽지 않아 보입니다. 왜냐하면 naive하게 구하면, 최악의 경우에, dQ만큼이나 수행해야 하기 때문입니다. 이걸 어떻게 하면 좋을지 먼저 생각해 봅시다.

 

 

---

일단, 자연수 k의 2진수 표현은 유일합니다. 이것부터 보여 봅시다. 귀류법을 써 보겠습니다. 간단하게 상위 비트부터 쭉 저장이 되어 있다고 가정해 봅시다. 만약에 k의 2진수 표현이 2가지 이상이라고 한다면, 분명하게도, 비트가 다른 부분이 존재할 겁니다.

 

 

 그러면 이 둘의 차이의 절댓값은 2^x보다는 크거나 같을 겁니다. 이제 보라색 부분을 봅시다.

 

 

 가정이 성립하려면, 보라색 부분을 어떻게 잘 채워서, 2^x만큼 상쇄해야 할 건데요. 상쇄를 하려면, 보라색 부분의 차이의 절댓값이 2^x보다 크거나 같아야 합니다. 차이의 최댓값을 생각해 봅시다. 위에 것이 1..1이고 밑에 것이 0..0인 경우에 차이의 절댓값이 최대가 되어 버립니다. 즉, 2^(x-1) + ... + 2^0이 최대가 되는데요. 이 값은 2^x - 1입니다. 2^x - 1 > 2^x는 거짓입니다.

 

 따라서 가정이 거짓이 되고, 어떠한 자연수 k의 이진 표현은 유일하게 존재합니다. 그런데 왜 쌩뚱맞게 이런 걸 자료 구조 시간에 이런 글을 올릴까요? 뜬금 없이. 다시 2진수로 돌아와 봅시다.

 

 

 5는 101(2)로 표현을 할 수 있어요. 이는 4 + 1로 표현이 가능하다는 것입니다. 2^2 + 2^0으로 표현 가능한가요? 네. 그렇다고 합니다. 다음에, 11을 보겠습니다.

 

 

 11은 2진수로 1011(2)로 표현할 수 있어요. 이를 잘 표현해 보면 2^3 + 2^1 + 2^0으로 표현할 수 있어요. 즉, 8거리 이동한 다음에 2거리 이동하고, 1거리를 이동하면 11거리를 이동한 것과 같습니다. 그렇다면 d = 10^9 - 1이면, 몇 개의 상태로 표현할 수 있을까요? 켜지고 꺼지고의 state 30개 정도로 표현할 수 있습니다.

 

 

---

 그러면 결국 우리는, 1, 2, 4, 8, ... 이런 식으로 2^t 거리만큼만 이동할 수 있어요. 그러면, 2^t만큼 이동한 것을 어떻게 compress 하면 좋을까요? t만큼 MOVE 했다고 퉁쳐도 됩니다. 어짜피, 2^0, 2^1, ... , 2^t꼴 이동밖에 못하기 때문입니다.

 

 

 그렇다면, 우리는 a에서부터 2^t만큼 이동했을 때, 어디로 오느냐의 문제를 풀어야 합니다. 그렇게 하기 위해서는, a에서 2^(t-1)만큼 이동한 다음에, 그 위치로부터 2^(t-1)로 이동하면 됩니다. a에서 2^(t-1)만큼 이동했을 때 위치를 pa라고 한다면, a에서 2^t만큼 이동했을 때 위치는, pa에서 2^(t-1)만큼 이동한 위치와 같습니다.

 

 

 그런데, 이런 상황이 있을 수 있어요. 그러면 a에서부터 거리 1만큼 이동하면 어떻게 될까? 이것은 위와 같은 방법으로 구할 수 없습니다. 이것은 보통 문제에서 주어지는데요. mv(a)는 a로부터 거리 1만큼 이동했을 때 나타나는 위치입니다. 따라서, a로부터 1만큼 이동한 거리를 구하기 위해서는 그냥 mv(a)값을 채우면 됩니다.

 

 

 이것을 코드로 그대로 구현하면 다음과 같습니다. 여기서 중요한 것은 dp[x][t]의 의미인데요. dp[x][t]는 x로부터 거리 2^t만큼 이동했을 때 어느 위치로 도달하는가를 나타냅니다. 그러면 처음에 dp[i][0]은 무슨 말인가요? i로부터 1번 move 하면 어디로 가느냐를 나타내는데요.

 

 이것은 보통, 문제에서 입력으로 주어집니다.

 

 

---

 이제 이렇게 채워진 dp 배열을 가지고, 우리는 x에서부터 거리 d만큼 이동했을 때 어떤 값이 나오는지 구해보도록 하겠습니다. 예를 들어, d = 6이라고 해 봅시다.

 

 

 그러면 2^2와 2^1을 나타내는 비트가 켜져있을 겁니다. 이를 각각 2번, 1번 비트라고 칭해 보겠습니다. 그러면 어떻게 이동하면 될까요? 당연하게도 아래 그림과 같이 이동하면 됩니다.

 

 

 이동할 때 마다 cur의 값을 갱신해 가면 될 거에요. 최대 몇 번 이동 연산을 할까요? 상태 수만큼 할 거에요. 이것은 d의 최댓값에 log를 씌운 값에 비례합니다. 아래 코드를 보겠습니다.

 

 

 보시면 x가 있는데, m 거리만큼 이동해서 어디에 도달하는지를 물어보고 있어요. 그러면, 먼저 cur 값은 x로 초기화를 시켜야 할 거에요. 그리고, 몇 번 비트가 켜졌느냐에 따라서, cur 값을 계속 업데이트 시켜주면 됩니다. 이것은 17번째 줄의 for문에서 수행하고 있습니다.

 

 최종적으로 0번 상태까지 모두 고려하고 나서 cur 값을 출력하면 됩니다.

 

 

---

 그러면 이 구조는 언제 쓰는 게 좋을까요? 중간에 업데이트가 일어나면 쓸만할까요? 잘 생각해 보시면 골치가 매우 아파진다는 것을 알 수 있습니다. 예를 들어, 다음과 같은 데이터가 있다고 해 봅시다.

 

 

 군청색, 노란색, 하늘색으로 표시한 노드의 갯수는 모두 같습니다. 그리고 그것의 수는 2^17개로 모두 같다고 해 봅시다. 그러면 군청색 노드들에서, 2^17 거리만큼 가거나, 혹은 더 멀리 점프한다면, 하늘색 노드들로 간다는 정보가 저장이 되어 있을 겁니다. 그런데, 이것을 단순히 40만 1이 2로 간다는 것을, 40만 1이 20만으로 간다는 정보로 업데이트를 했다고 해 봅시다.

 

 

 그러면, 군청색으로 표시한 것들에서 2^17 거리보다 같거나 더 많이 점프하게 되는 경우에 하늘색 노드로 가지 않을 거에요. 즉, 원래는 하늘색 노드로 갔다는 것을, 하늘색 노드가 아닌 다른 색깔을 가진 node로 점프한다는 정보로 업데이트를 해야 합니다. 군청색으로 칠해져 있는 모든 것에 대해서. 따라서 Online 쿼리에 적합하지 않습니다.

 

 sparse table, 스파스 테이블은 정적인 것에 대해서 빠르게 처리할 수 있는 데이터 구조입니다.