특정 조건에서 LCS를 O((n+m) log (nm))에 구하는 알고리즘

 

*LCS

Longest Common Subsequence.

Subsequence는 부분수열들이 꼭 연속하지 않아도 된다.

 

예를 들어 두 수열 A,B가 있다 하자.

A = 1 5 3 4 2 6 5

B = 1 6 3 2 3 5

 

A와 B의 부분 수열은 {1}, {3}, {1,2} 등 여러가지가 있다.

A와 B의 LCS는 {1,3,4,5}이고 그 길이는 4이다.

 

A의 길이를 n, B의 길이를 m이라 할 때 다이나믹 프로그래밍을 이용해 O(nm)의 시간에 LCS(A,B)를 구할 수 있다.

이는 잘 알려져 있는 알고리즘이므로 쉽게 설명된 글이 많다.

 

이 글에서는 특정 상황에서 빠르게 LCS를 구하는 방법에 집중한다.

또한 앞으로 LCS를 구하는 것을 LCS의 길이를 구하는 것과 동일하게 취급한다.

*특정 조건에서 LCS를 O((n+m) log (nm))에 구한다

Obtaining LCS in O((n+m) log (nm)) at particular conditions.

 

n,m이 10^5라면 O(nm)의 알고리즘으로 1초 안에 LCS를 구할 수 없다.

더 빠른 알고리즘은 없을까? O(n*n/ log n)^[각주:1], O(n*m/w)^[각주:2] (w는 일반적으로 32 또는 64) 알고리즘이 존재한다고 알려져 있지만 이 문제를 해결하기에는 벅차 보인다.

 

그렇다면 문제의 조건을 약화시켜보자.

B가 서로 다른 원소들로 이루어졌다면 어떨까?

 

A[i]에 대해 B에는 1개 이하의 A[i]와 같은 원소가 존재한다.
그런 원소가 존재한다면 그 원소의 idx를 C[i]라 하자.

A의 원소 A[i]에 대해 C[i] 값이 대응될 것이다.  여기서 LCS를 구하는 방법은?

내가 전에 살펴본 원소 A[j]와 대응되는 C[j] 값이 있을텐데 이 C[j]가 C[i]보다 작아야지만

부분수열로 연결지을 수 있다.

 

D[i]를 A[i]를 마지막으로 하는 부분 수열의 최대 길이라 정의하자.

j<i, C[j]<C[i]인 j에 대해 D[i] = max(D[j]) + 1이 된다.  D를 관찰해보자.

 

어라? 어디서 많이 본 상황이다.

D의 의미는  i보다 작은 인덱스 j에 대해 배열의 값 C[j]<C[i]에 대해 dp값을 최대로 하는 것이다. 

즉 인덱스 배열 C에서 가장 긴 증가하는 부분 수열(LIS)을 구하면 되는 것이다!

 

LIS는 이분탐색을 이용해 O(n log n)에 구할 수 있다.

 

+ LIS 역추적은 역추적배열에 인덱스를 저장하여 할 수 있다.
 LCS 자체를 구해야 한다면 LIS의 인덱스를 역추적하면 된다.

LIS 역추적 구현은 다음의 코드를 참고하자.

boj.kr/e6abbd5cc944400bbb43e07068d77d1a 

 

A 배열에는 중복 원소가 존재해도 된다는 사실에 유의하라.

C[i]를 구하기 위해 미리 B 배열을 정렬해야 한다. 이는 O(m log m) 시간이 걸린다.

C[i]를 O(n log m) 시간에 구할 수 있고, LIS를 O(n log n)에 구할 수 있으므로

전체 시간복잡도는  O( m log m + n log n + n log m ) = O((n+m)(log m+log n))

= O((n+m)log(nm))이다.

 

*연습문제

code.sasa.hs.kr/problem.php?id=1366

SASA OJ discuss3

 

문제요약 

p,q ( 5<=p,q<=10^5)일 때 길이 p, 길이 q의 서로 다른 원소들로 이루어진 수열 2개가 있다.

두 수열의 LCS의 길이를 구하라.

 

 

문제 접근

문제 디스크립션이 난해해 상황을 이해하기 어렵다.
입력 예시/ 출력 예시를 통해 문제를 이해해보자.
 
난이도는 1~max(p,q)의 수로 주어진다고 명시되어 있지만 
예시부터 그 조건을 당당히 어겨버리기에 
문제를 던져버리고 싶은 충동이 강하게 든다.

인내심을 가지고 문제를 이해하려 노력하면
이 문제가 LCS 문제라는 것을 관찰할 수 있다. 
일반적인 LCS 문제는 다이내믹 프로그래밍으로 
O(n*m) 시간에 해결이 가능하다.

그러나 이 문제는 n,m <= 1e5이기에 제한 시간 내에 해결할 수 없다.

처음 생각할 수 있는 것은 최적화다. DP[n][m]을 채우기 위해
직전 행과 현재 행만 필요하기에 공간은 2*min(n,m)으로 줄일 수 있다.
그러나 이 방법으로는 시간복잡도는 줄지 않는다.
2번째 방법은 비트를 이용한 최적화다. 

www.secmem.org/blog/2019/09/12/lcs-with-bitset/

(w는 워드, 컴퓨터에서 처리 가능한 단위. 일반적으로 32 or 64)
이 방법을 이용하면 시간복잡도를 O(nm/w)로 최적화할 수 있다. 
10만*10만/64 ~= 1억 5천만이므로 간당간당해보인다.
koosaga.com/245 도 참고해보자.

 

우리는 정녕 최적화 + 상수 줄이기로 이 문제를 해결해야하는가?
문제를 다시 한 번 살펴보자.
각 난이도는 서로 다른 숫자로 이루어져 있다는조건이 있었다! 
즉 두 수열에 같은 원소가 있다면 그 앞으로는 똑같은 원소가 없다는 것이다.
두 수열을 A,B라 하자.
A[i]에 대해 B에는 1개 이하의 A[i]와 같은 원소가 존재한다.
존재한다면 그 원소의 idx를 C[i]라 하자.
A[i]를 마지막으로 하는 LCS의 길이를 D[i]라 하면 
j<i, C[j]<C[i]에 대해 D[i] = max(D[j]) + 1이 된다.
이 DP를 계산하기 전에 D를 면밀히 살펴보자.

LIS와 상황이 동일하다!
i보다 작은 인덱스 j에 대해 배열의 값 C[j]<C[i]에 대해 dp값을 최대로 하는 것이다.
LIS는 이분탐색을 이용해 O(n log n)에 해결가능하다.

 

 

코드

#include<stdio.h>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
vector<pair<int,int>> A;
int n,m;
int main(){
	scanf("%d%d",&n,&m);
	rep(i,n){
		int k; scanf("%d",&k);
		A.emplace_back(k,i);
	}
	sort(A.begin(),A.end());
	int ans=0,dp[100010]={};
	rep(i,m){
		int k; scanf("%d",&k);
		auto p = *lower_bound(A.begin(),A.end(),make_pair(k,-1));
		if(p.first != k) continue;
		int idx = lower_bound(dp+1,dp+ans+1,p.second)-dp;
		dp[idx] = p.second;
		if(idx == ans+1) ++ans;
	}
	printf("%d",ans);
}

 

 

 

 

 

1. www.cs.bgu.ac.il/~michaluz/seminar/four_russians.pdf [본문으로]
2. www.secmem.org/blog/2019/09/12/lcs-with-bitset/ [본문으로]