dp와 분할정복으로 LIS 해결

LIS(Longest Increasing Subsequence)를 해결하는 방법은 다양하다. 특히 $O(nlogn)$ 으로 푸는 방법들에는 이분탐색과 세그먼트 등이 있다. 이번에는 시간복잡도는 $O(nlog^2n)$ 으로 약간 뒤쳐지지만 분할정복과 dp로 lis의 길이를 구할 수 있는 방법에 대해 써보려고 한다.

 

이 풀이는 KOI 2018 고등부 3번 조화로운 행렬 을 풀어보려고 하다가 ba*arkingdog님의 블로그를 보고 알게된 koosaga님의 댓글을 보고 알게 되었다. (복잡한 사연..)

https://codeforces.com/blog/entry/43319

여기를 보면

이와 같이 풀이에 대한 아이디어가 적혀있는데 여기서 붉은 문단을 이해할 수 없어서 결국 koosaga님의 조화로운 행렬풀이를 보고 공부하였다.  그 문제에 대한 포스팅에 앞서 이해를 돕기 위해 이번 포스팅을 하게 되었다.

 

먼저,

$dp[i]$ : 1번 ~ $i$번까지 수로 이루어진 lis의 길이로 정의하자.

분할정복으로 lis의 길이를 구하는 방법은 다음과 같다.

$solve(s,e)$: $s$에서 $e$까지의 $dp$값을 계산.

1. call solve(s,m) (단 ,$m=(s+e)/2$)

2. $(s,m)$에서 계산된 $dp$정보를 $(m+1,e)$로 넘기는 과정

3. call solve(m+1,e)

 

여기서 2번 과정이 중요한데,

pair로 구성된 두 개의 벡터를 만들어 놓자. 각각 $l$, $r$이라 하자.

$l$에는 $(s,m)$의 index에 대해 (원소값,dp값)을 저장해놓고,

$r$에는 $(m+1,e)$의 index에 대해 (원소값,index)을 저장해놓자.

각 벡터를 정렬시키고,

$r$에서 정렬된 순서대로 dp update를 진행할 것이다.

현재 $r$에서 update하고자 하는 pair를 $(v[i] , i)$라 하자.

 

그리고 정렬된 $l$의 원소값 중 $v[i]$보다 작은 것들에 해당하는 원소에 딸린 dp값을 BIT에 update해놓자.

그러면 $Max(j<i, v[j]<v[i]) dp[j]$ 를 $O(logn)$에 구할 수 있다. 

 

결국 전체 시간복잡도는

$T(n)=2T(n/2)+O(nlogn)$ 이고 마스터 정리에 의해 최종 시간복잡도는 $O(nlog^2n)$ 임을 알 수 있다.

 

그냥 LIS 길이 구하는 문제를 풀 때는 널리 알려진 풀이로 푸는 것이 낫지만

이 방법은 LIS뿐만 아니라 DP 풀이 방법으로 좋으니 알아두는 것이 좋을 것 같다.

 

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<stack>
#include<map>
#include<queue>
#include<utility>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<cmath>
#include<time.h>
using namespace std;

/*lis 풀이 분할 정복 & segment tree*/
typedef pair<int,int> P;
int n;
vector<int> v;
#define MAX 1000010
int dp[MAX];
int fen[MAX+10];
void add(int pos,int val){
	pos++;
	while(pos<=MAX){
		fen[pos]=max(fen[pos],val);
		pos+=(pos&-pos);
	}
}
int query(int pos){
	pos++;
	int ret=0;
	while(pos>0){
		ret=max(ret,fen[pos]);
		pos-=(pos&-pos);
	}
	return ret;
}
void erase(int pos){
	pos++;
	while(pos<=MAX){
		fen[pos]=0;
		pos+=(pos&-pos);
	}
}

void solve(int s,int e){
	if(s==e){
		dp[s]++;
		return;
	}
	int m=(s+e)/2;
	solve(s,m);
	vector<P> l,r;
	for(int i=s;i<=m;i++) l.push_back(P(v[i],dp[i]));
	for(int i=m+1;i<=e;i++) r.push_back(P(v[i],i));
	sort(l.begin(),l.end());
	sort(r.begin(),r.end());
	int ptr=0;
	int len=l.size();
	for(P here: r){
		while(ptr<len && l[ptr].first<here.first){
			add(l[ptr].first,l[ptr].second);
			ptr++;
		}
		dp[here.second]=max(dp[here.second],query(here.first-1));
	}
	for(int i=0;i<ptr;i++) erase(l[ptr].first);
	solve(m+1,e);
}

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		int x;
		scanf("%d",&x);
		v.push_back(x);
	}
	solve(0,n-1);
	cout<< *max_element(dp,dp+n);
	return 0;
}

 

참고로 위의 풀이는 다음 포스팅인 조화로운 행렬을 이해하는데 도움이 되는 풀이이고,

그냥 lis길이만을 구하는 것은 아래와 같이 분할정복 과정을 더 간단히 할 수 있다.

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<stack>
#include<map>
#include<queue>
#include<utility>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<cmath>
#include<time.h>
using namespace std;

/*lis 풀이 분할 정복 & segment tree*/
typedef pair<int,int> P;
int n;
vector<int> v;
#define MAX 1000010
int dp[MAX];
int fen[MAX+10];
void add(int pos,int val){
	pos++;
	while(pos<=MAX){
		fen[pos]=max(fen[pos],val);
		pos+=(pos&-pos);
	}
}
int query(int pos){
	pos++;
	int ret=0;
	while(pos>0){
		ret=max(ret,fen[pos]);
		pos-=(pos&-pos);
	}
	return ret;
}
void erase(int pos){
	pos++;
	while(pos<=MAX){
		fen[pos]=0;
		pos+=(pos&-pos);
	}
}

void solve(int s,int e){
	if(s==e){
		dp[s]++;
		return;
	}
	int m=(s+e)/2;
	solve(s,m);
	vector<P> l,r;
	for(int i=s;i<=m;i++){
		add(v[i],dp[i]);
	}
	for(int i=m+1;i<=e;i++) {
		dp[i]=max(dp[i],query(v[i]-1));
	}
	for(int i=s;i<=m;i++){
		erase(v[i]);
	}
	solve(m+1,e);
}

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		int x;
		scanf("%d",&x);
		v.push_back(x);
	}
	solve(0,n-1);
	cout<< *max_element(dp,dp+n);
	return 0;
}