원래 취업하고 나면 동생과 함께 풀기로 약속한 문제가 있었는데, 마침 운 좋게도 IT 회사에 취업하고 연휴가 길어서 사흘 밤낮을 문제 하나에 매진했습니다. 삼각분할과 closest point query는 동생이 처리하기로 했고, 저는 링크컷 트리와 문자열 알고리즘을 처리했습니다. 링크컷 트리는 잘 만들어진 게 있으니까 그런대로 쉬웠는데, 문제는 두 문자열 간의 최장 공통 부분 문자열을 빠르게 구하는 게 병목이었습니다.

만약 두 문자열의 최장 공통 부분 문자열을 구하는 게 목적이라고 해봅시다. 아무런 최적화 없이 작업을 수행한다면 문자열 A에서 모든 부분문자열을 찾을 때 \(O(\vert S \vert^2)\), 또 문자열 B에서 해당 부분문자열과 일치 여부를 판단하는 데 \(O( \vert S \vert ^2)\)가 걸립니다. 패턴 매칭은 KMP로 좀 줄여볼 수는 있겠지만 크게 도움이 되지는 않습니다.

하지만 LCP 배열을 쓰면 \(O(\vert S \vert \log \vert S \vert)\)로 이를 처리할 수 있게 됩니다. 천지창조 문제를 풀기 전에 먼저 풀어볼만한 연습문제에서 이를 적용해볼 수 있습니다. 이 글에서는 희소배열을 다룰 것이므로 자세한 풀이는 생략하고, 핵심만 정리하자면 다음과 같습니다: 접미사가 정렬된 SA 배열에서 A 문자열의 인덱스와 B 문자열의 인덱스가 인접하여 나타날 때의 lcp 길이가 정답의 후보가 되고, 이를 모두 순회하는 것으로 답을 구할 수 있다는 것입니다.

다시 천지창조 문제로 돌아와서, 문자열이 3개 이상일 때도 lcp 배열을 이용해서 이 쿼리를 빠르게 처리해줄 수 있습니다. 대신 이번엔 문자열이 3개 이상이므로 인접한 인덱스 간의 lcp 길이를 확인하는 것만으로는 부족합니다. \(S_i\)의 인덱스와 \(S_j\)의 인덱스 사이에는 다른 문자열 인덱스가 끼어있는 경우가 있습니다. 이럴 때 두 문자열의 공통 문자열 길이는 구간 최소값 쿼리로 구해줄 수 있습니다. lcp 배열 길이가 가장 짧아지는 시점이 공통 문자열의 최대 길이가 되기 때문입니다.

여전히 문제는 남아있는데, 쿼리를 하나 처리하기 위해서는 여전히 \(O( \vert S \vert )\)번의 구간 최소값 쿼리를 함께 처리해야 한다는 것입니다. 쿼리 전체에 대해서는 \(O(Q \vert S \vert)\)가 됩니다. 제곱근 분할법으로 이를 \(O( \vert S \vert \sqrt{ \vert S \vert})\)까지 줄일 수 있으나, 세그먼트 트리로 구간 최소값 쿼리까지 처리하면 \(\log \vert S \vert \)가 추가로 소요됩니다. 실제로 쿼리를 100만 번 처리하니 15초 정도 걸리는 것을 확인했습니다.

희소배열과 특수한 구간 질의

희소배열은 구간을 쪼갠 후 빠르게 질의를 처리할 수 있는 자료구조라는 점에서 세그먼트 트리와 비슷합니다. 대신 값을 업데이트 하는 것은 어렵기 때문에 보통 오프라인 쿼리에서 활용합니다. 빈번한 업데이트에도 적용할 수 있는 세그먼트 트리에 비해 활용도가 다소 떨어지지만, 특수한 경우에는 매우 강력한 도구가 됩니다.

희소배열과 세그먼트 트리의 기본적인 아이디어는 동일합니다. 1, 2, 4, 8… 등 2의 거듭제곱의 합으로 모든 수를 표현할 수 있고, 해당 길이의 구간 값을 미리 갖고 있다면 그 구간 값 간의 연산만으로 전체 구간 질의를 처리하는 것입니다. 구간이 겹치지 않도록 잘 쪼개서 미리 처리된 구간들을 만들어내는 것이 핵심입니다.

그런데 만약 구간이 겹쳐도 된다면 굳이 \(\log N\)개로 쪼갤 필요가 없습니다. 1, 2, 4, 8… 길이로 쪼개는 것은 같은데, 대신 이렇게 처리할 수 있습니다.

  • 만약 구간 쿼리 길이가 8이라면 8짜리 구간 한 개
  • 쿼리 길이가 9라면 8짜리 두 개를 7칸 겹쳐서 처리
  • 길이가 10…15까지도 비슷하게 겹쳐서 처리
  • 길이가 16이라면 16짜리 한 개로 처리
  • 길이 17…31까지 겹쳐서
  • 길이 32부터는 32짜리 한 개…

임의의 구간 길이에 대해, 2개의 구간 값만 가지고 있다면 적당히 겹쳐서 해당 구간 값을 만들어낼 수 있습니다. 그리고 최소값 구간 쿼리는 구간이 겹쳐도 되는 케이스에 해당합니다.

struct SparseTable {
    int n;
    std::vector<int> lg;
    std::vector<std::vector<int>> st;
    SparseTable() : n(0) {}
    SparseTable(const std::vector<int>& a) { build(a); }
    void build(const std::vector<int>& a) {
		n = (int)a.size();
		if (n == 0) return;
		lg.assign(n + 1, 0);
		for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
		int K = lg[n] + 1;
		st.assign(K, std::vector<int>(n));
		st[0] = a;
		for (int k = 1; k < K; ++k) {
			int len = 1 << (k - 1);
			for (int i = 0; i + (1 << k) <= n; ++i) {
				st[k][i] = std::min(st[k - 1][i], st[k - 1][i + len]);
			}
		}
	}
    int query(int l, int r) const { // [l, r)
		if (l >= r) return INF;
		int len = r - l;
		int k = lg[len];
		return std::min(st[k][l], st[k][r - (1 << k)]);
	}
};

이번에 문제를 풀면서 더 복잡하고 어려운 트릭을 배운 것보다는 오히려 희소배열과 같은 어찌보면 기본에 가까운 내용을 복습할 수 있었다는 점에서 좋은 기회가 되었습니다.

사실 실무에서 KD Tree를 다룰 일이 있어서 문제를 풀다보니 이걸 더 공부해봐야 겠다는 생각은 들었는데, 막상 돌아보니 연휴가 끝나버렸습니다. 나중에 기회가 된다면 좀 파봐야겠습니다.