BOJ 18438 | LCS 5

LCS 1부터 풀다가 결국 여기까지 왔는데 난이도가 갑자기 미친듯이 수직상승하는게 백준 1000번부터 번호순으로 푸는 느낌이라서 재밌다. 과연 LCS 6은 얼마나 어려울까?

일단 메모리 제한이 4MB인 것부터 극한의 최적화를 요구하는 문제임을 짐작할 수 있다.

int형 변수가 4B를 잡아먹는데, 4MB라는 제한은 int 형 변수를 26만개밖에 선언할 수 없는 아주 작은 용량이다.

문제에서 주어지는 문자열은 7000글자이므로, $O(N^2)$의 공간복잡도로는 해결할 수 없다.
$O(N)$으로 어떻게든 메모리를 절약해서 구현해야 한다.

이 문제는 히르쉬버그 알고리즘을 사용해서 해결할 수 있다.
사실 나도 이름만 들어봤지 이게 대체 뭐하는 알고리즘인지 지금까지 몰랐다.
이 문제로 입문한 셈인데, 다이아 I 문제가 입문용이라니 정말 두려워지는 알고리즘이다.

이 알고리즘을 설명하기 전에, LCS를 구하는 방법에 대해 먼저 생각해보자.

원래 LCS를 구하기 위해서는 2차원 배열을 생성해서 $O(NM)$으로 해결해왔다.
그러나 지금은 바이트 하나도 아껴야 하는 상황이기 때문에 이 부분에서 크게 절약해야 한다.

LCS를 구하기 위해 필요한 정보는 위, 대각선, 아래 이므로 토글링을 사용할 수 있다.
그러므로 LCS는 공간복잡도 $O(N)$으로 구할 수 있다.

$dp[i][j]$를 $dp[i\%2][j]$로 바꾸어서 생각하면 어떻게 이게 가능한지 알 수 있다.
LCS 표를 그릴 때 한 줄씩 차례대로 그리는데, 내가 그리고 있는 줄의 윗줄은 필요하지만 그 윗줄부터는 필요가 없으므로 덮어씌워도 되는 것이다.

다만 이렇게 하면 역추적을 할 수가 없다.
이미 덮어씌워진 표를 다시 불러올 수는 없으니 이 역추적을 위해 히르쉬버그 알고리즘을 사용해야 한다.

히르쉬버그 알고리즘

커다란 네모를 계산한 후, 다음 계산을 하얀 네모 두 개로 나누어서 실행한다.
이게 기본 아이디어이다.

기본적으로 분할 정복인데, 알고 나면 정말 쉽지만 몰랐을 때는 어려운 종류의 알고리즘이다.
솔직히 어떻게 이런 생각을 했는지 정말 궁금하다.

저 기준이 되는 가로와 세로는 하나는 정해 두고, 하나는 유동적으로 움직이게 한다.
가로를 분할하는 지점을 mid라고 하고, mid = (start + end) / 2 이다.
세로는 k라고 두고, 우리는 계산을 하면서 적절한 k를 찾아주면 된다.

이후, 재귀를 통해 위쪽 하얀색을 먼저 실행하고 아래쪽 하얀색을 나중에 실행해주면 순서대로 위쪽부터 결과물을 뽑을 수 있다.

string 1 : [s1, e1]
string 2 : [s2, e2]

일 때, LCS(s1, e1, s2, e2)를 실행하면 LCS(s1, mid, s2, k) 와 LCS(mid+1, e1, k+1, e2)로 분할되고, 전달받은 s1과 e1이 같을 때 결과물을 출력하면 된다.

계산할 행이 하나일 때는 s2~e2를 순회하며 string1[s1] == string2[i] 인지 판단할 수 있으므로 깔끔하게 for문 하나로 해결된다.

계산할 행이 2개 이상일 때는, LCS를 돌려야 한다.
여기서 핵심은 LCS(s1, e1, s2, e2) = LCS(s1, mid, s2, k) + LCS(mid+1, e1, k+1, e2) 로 분할되는 k를 찾는 것인데, LCS는 최대여야 하므로 LCS(s1, mid, s2, k) + LCS(mid+1, e1, k+1, e2)가 최대인 k를 찾아야 한다.

k가 여러개일 수도 있는데, 그럴 때는 그냥 아무거나 잡아도 괜찮다. 구현하기 편한 대로 하자.
중요한 건 LCS가 손실 없이 두 개로 분할되었다는 것이고, 이걸 계속 반복할 수 있다는 것이다.

행이 하나가 될 때까지 분할된 후, 행이 하나일 때 return하므로 시간복잡도는 $O(NM)$이고, 공간복잡도는 $O(N)$이다.

나는 제곱근 분할 같이 뭔가를 적절히 분할해서 처리하는 알고리즘을 이미 공부해서인지 의외로 히르쉬버그는 딱히 어렵지 않게 느껴진다.

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

string a, b;
string result;

void LCS(int s1, int e1, int s2, int e2){
	if (s1 == e1){ // one row
		for (int i = s2; i <= e2; i++){
			if (a[s1] == b[i]) {
				result += a[s1];
				break;
			}
		}
		return;
	}
	
	int mid = (s1 + e1) / 2;
	int len = e2-s2+1;
	vector<int> upper(len+2), lower(len+2);
	vector<int> save(len+2);
	for (int i = s1; i <= mid; i++){ // LCS (a[s1:mid], b[s2:e2])
		for (int j = s2; j <= e2; j++){
			if (a[i] == b[j])
				upper[j-s2+1] = save[j-s2] + 1;
			else
				upper[j-s2+1] = max(save[j-s2+1], upper[j-s2]);
		}
		save = upper;
	}
	fill(save.begin(), save.end(), 0);
	for (int i = e1; i >= mid+1; i--){ // LCS (a[mid+1:e1], b[s2:e2])
		for (int j = e2; j >= s2; j--){
			if (a[i] == b[j])
				lower[j-s2+1] = save[j-s2+2] + 1;
			else
				lower[j-s2+1] = max(save[j-s2+1], lower[j-s2+2]);
		}
		save = lower;
	}
	
	for (auto &i: upper) debug << i << ' '; debug << endl;
	for (auto &i: lower) debug << i << ' '; debug << endl;
	
	int mxv = INT_MIN; int idx = 0;
	for (int i = s2-1; i <= e2; i++){
		if (mxv <= upper[i-s2+1] + lower[i-s2+2] ){
			mxv = upper[i-s2+1] + lower[i-s2+2];
			idx = i;
		}
	}
	
	LCS(s1, mid, s2, idx);
	LCS(mid+1, e1, idx+1, e2);
	
}

int main(){
	FASTIO;
	int x, y; cin >> x >> y;
	cin >> a >> b;
	a = ' ' + a; b = ' ' + b;
	
	LCS(1, a.length()-1, 1, b.length()-1);
	cout << result.length() << '\n' << result;
}

upper, lower, save 배열은 각각 [0 (내용) 0] 으로 쓸 수 있게 len+2 크기로 선언했다.
0 0 0
0 1 0
같이 upper와 lower가 나오는 경우, 마지막에 LCS(s1, mid, s2, k) + LCS(mid+1, e1, k+1, e2)가 최대인 k를 찾기 위해 인덱스를 1부터 돌리면 볼드처리한 부분부터 검색되므로 인덱스는 0부터 시작해야 한다. (int i = s2-1; 부분)

이거 못 찾아서 좀 고생했다.