자료구조 #1. Sparse Table
Sparse Table 자료 구조 훑어보기
애플리케이션을 구현하다 보면, 구간의 합계를 구하거나 구간 내 최솟값을 구해야 하는 경우가 있다. 합계를 구하는 것과 최솟값을 구하는 건 약간의 차이가 있긴 하지만, 어찌 보면 둘 다 RMQ(Range Minimum Query) 문제라고 볼 수 있다. RMQ 문제를 해결할 때 가장 많이 사용하는 자료구조는 Segment Tree이다. Segment Tree를 사용하면, Tree를 구성하는데 O(N) 시간이 들고, 조회 및 업데이트를 O(logN) 시간 안에 수행할 수 있다. 그래서 동적으로 원소를 업데이트하는 경우에 Segment Tree를 사용하는 편이다.
물론 정적인 배열에 대해서도 Segment Tree를 사용할 수 있다. 즉, 업데이트가 발생하는 일이 없다고 하더라도, Segment Tree를 통해서 문제를 해결할 수 있다는 의미이다. 하지만, 이보다 더 빠르게 문제를 해결할 수 있는 방법이 있다. 바로 Sparse Table이라는 자료구조를 사용하면 된다.
Sparse Table을 배열의 정보가 업데이트되지 않는다는 전제하에 만드는데 O(NlogN) 시간, 조회하는데 O(logN) 시간만큼 걸린다. 단, 연산 내용에 따라서 O(1) 시간 내에 구할 수도 있다.
Sparse Table의 원리는 다음과 같다.
모든 구간은 특정 시작점에서 2의 제곱수를 더한 범위로 쪼갤 수 있다. 이때, 구간 시작은 포함하지만, 구간 끝은 포함하지 않는다. 예컨대, [1,5] 범위를 가정하면, [1, 1 + 4(2^2))과 [5, 5 + 1(2^0)), 즉 [1,5), [5, 6)으로 구분된다. 이렇게 나누는 이유는 특정 시작점에서 2의 제곱수만큼의 범위 내에서 최솟값을 미리 계산해 놓기 위함이다. 미리 연산을 해두면 [a, b] 구간 최소를 구할 때, 그보다 작은 범위에 미리 연산한 값을 통해 연산 속도를 높일 수 있다. 이는 Segment Tree와 비슷한 원리이다. 약간 다른 건, 모든 시작 점에서 2 제곱수만큼의 길이 구간 내 결과를 미리 가지고 있다는 점이다. 그래서 Sparse Table은 만드는데 O(NlogN)만큼의 시간이 발생한다.
구간의 최소를 구하는 Sparse Table의 예시는 다음과 같다.
- 길이가 N인 배열에 대해서 range 길이가 2,4,8... 2^log(N) 일 때 각각의 최소를 미리 테이블에 저장한다.
- 아래 배열의 길이 N = 8 이므로, logN = 3 이 된다. 즉, 길이가 2^3 = 8인 경우까지만 구하면 된다.
- 인덱스 i부터 시작하는 2^p 만큼의 길이의 최소를 구하는 경우는 다음과 같이 구할 수 있다.
- 인덱스 i부터 시작하는 2^(p-1) 만큼의 길이의 최소: dp [p-1][i]
- 인덱스 i + 2^(p-1)부터 시작하는 2^(p-1)만큼의 길이의 최소: dp [p-1][i + 2^(p-1)]
- 이렇게 연산이 가능한 이유는 길이가 8인 경우, 길이가 4인 겹치지 않는 두 구간의 결과를 연산하면 전체 길이 8을 연산한 결과임을 보장하기 때문이다. 예컨대, 1반에서 1등과 2반에서 1등을 비교하면, 1반과 2반을 합친 학생들 중 1등을 가려낼 수 있는 것과 같다.
연산의 경우에는 종류에 따라 그 구현이 달라진다.
여기서 중요하게 알아두어야 할 것은 연산이 중복을 허용하냐 하는 것이다. 예컨대, 구간 [2, 5]까지의 최소를 구한다고 가정해 보자. 그러면 [2, 3], [3, 5] 결과를 각각 구해서 최소를 찾아도 문제가 되지 않는다. 인덱스 3이 양쪽에 포함되어 있어서 구간이 겹치지만, 최소를 구하는 경우이기 때문에 3이 어느 구간에서도 최소가 아니라면 결과에 영향을 미치지 않을 것이다. 설령 인덱스 3이 최솟값이라고 해도, 정답은 인덱스 3의 값이 나오게 된다.
하지만, 합계를 구하는 경우에는 상황이 달라진다. 똑같이 구한 [2, 5]까지의 합계를 구한다고 가정해 보자. 그리고 [2, 3], [3, 5] 결과를 각각 구해서 더하면 실제 [2,5] 구간을 더한 값보다 인덱스 3의 값만큼 더 늘어난다. 왜냐하면 두 구간에서 인덱스 3의 값이 각각 더해졌기 때문이다.
따라서, 겹치는 구간을 허용하는 연산의 경우인 최솟값 연산에 대해서 Sparse Table을 사용하면, 다음과 같이 O(1) 시간 안에 구간 내 최소를 구할 수 있다.
query(left, right) = min(dp[p][left], dp[p][right - 2^p + 1])
인덱스 left에서 시작하는 구간의 길이가 2^p인 구간의 최소(dp[p][left])
인덱스 right에서 끝나는 구간의 길이가 2^p인 구간의 최소 (dp[p][right - 2^p + 1])
만약 구간이 겹치면 안 되는 경우에는 제일 긴 구간부터 줄여나가면서 겹치지 않게 연산해야 한다.
예컨대, [2,10] 구간의 합을 구한다고 해보자.
query(left, right) = query(2, 10)
길이가 9(10 - 2 + 1)이므로, logN = 3이 된다. 즉, 2에서 시작하는 길이가 2^3 = 8인 구간, [2, 9] 만큼의 합계를 구한다.
left를 이전에 구한 구간의 길이만큼 더한다. left = 2 + 8 = 10
다시 이전 단계를 반복한다.
길이가 1 (10 - 10 + 1) 이므로, logN = 0이 된다. 즉, 10에서 시작하는 길이가 2^0 = 1인 구간, [10,10] 만큼의 합계를 구한다
left를 이전에 구한 구간의 길이만큼 더한다. left = 10 + 1 = 11
이제 left가 right보다 크므로, 여태까지 더한 합계를 반환한다.
Sparse Table 코드는 다음과 같다.
참고로, Operation에 대한 코드는 다음과 같이 별도 파일로 분리했다.
