최장 증가 수열(LIS), 최장 공통 문자열(LCS)

lis는  10, 20, 10, 30, 20, 50   이런 길이 5의 수열중  10, 20 ,30 ,50  과 같이 계속해서 증가하는 수열들 중, 가장 긴 수열을 찾는 문제다. 

우선 lcs는 푸는 방식이 정말 다양한데, 전부 시간 복잡도가 다르다.

dp를 통해서 풀게되면 O(N^2)   이고,  lower_bound를 통해서 풀게 되면 O(NlogN) 의 시간 복잡도가 발생한다.

lis 문제는 시간초과를 가지고 장난을 많이 치기에 lower_bound 방식만 가지고 문제를 풀어보겠다. 

자세한건 아래 문제를 보면서 알아보자..!

 

 

 

1.lis 의 길이는?   

lis의 길이를 구하는 문제로, 위 의 입력의 경우 10,20,30,50 이기에 4가 정답입니다.

 

흔히 전깃줄 문제로 응용 됩니다. 자세한 건 아래 문제를 확인 해봅시다! 

https://www.acmicpc.net/problem/1365

1365번: 꼬인 전깃줄

우선 정답 코드부터 같이 봅시다.

#include<iostream>
#include<vector>
using namespace std;
int main(){
	int n,data;
	cin>>n;
	vector<int> v;
	vector<int>::iterator it;
	for(int i=0;i<n;i++){
		cin>>data;
		if(i==0)
			v.push_back(data);
			
		else if(v.back()<data){
			v.push_back(data);
		}
		
		else{
			it=lower_bound(v.begin(),v.end(),data);
			*it=data;
		}
	}
	cout<<(n-v.size());
}

각 전깃줄이 교차 되지 않게 하려면 어떻게 되야할까요? 

쉬운 이해를 위해 왼쪽 전봇대를 A그룹,  오른쪽 전봇대를 B 그룹으로 칭하고, B 그룹 을 기준으로 설명하겠습니다.

B그룹의 1째 전봇대가 A그룹의 3번째 전봇대와 연결되어있고,   B그룹의 2째 전봇대가 A 그룹의 2째 전봇대와 연결되있다면 어떻게 될까요? 교차가 됩니다. ( 한번만 그려보시면 바로 아하! 하실 겁니다) 

B그룹이 연결된 A그룹 전봇대의 번호를 배열에 저장하고, 그 값들로 LIS를 구하여 길이를 찾으면, 줄을 끊어서 나올 수 있는  최대 길이가 됩니다.

 

Ex)     10 20 15 25 >>      LIS 는 10 15 25 이고, 이는 위의 문제 관점으로  A그룹의 20번째 전봇대와 B그룹의 2째 전봇대를 잇는 전설을 제거한다고 볼 수 도 있습니다

 

그럼 이제 LIS 를 구해봅시다.

위의 코드에서 딱 한가지만 이해하면 됩니다.

lower_bound 인데요,  #include<vector> 를 통해 사용 가능합니다.

lower_bound(시작위치, 끝 위치, val)  을 해주면 ,   시작 위치~ 끝위치를 전부 탐색하며 " 최초로 val 이상 의 값이 나오는 위치값" 을 돌려줍니다.  말이 어려운데요, 이 개념 하나만 이해하면 끝입니다.   예시를 들어 설명하겠습니다.

    
1,2,3,4     

가 들어있는 vector 'V' 에서 lower_bound(V.begin(),V.end(), 3  ) 을 해주게 되면 

최초로 3 "이상" 의 숫자가 나온 위치 값을 리턴해줍니다.   

그럼 이걸로 어떻게 LIS 를 구할 수 있을까요?

 

1 2 10 2 3 10 13 15 

 

이러한 수열이 있다고 가정해봅시다.

하이라이트 된 위치에 10이 2번 나오는데요,   이 경우 앞의 10을 없애도 괜찮을까요?

답은 yes 입니다.   

 

10 2 3 10   

 

의 경우엔 뒤에 같은 숫자 10이 나옴으로써, 그 사이에 다른 숫자들이 위치할 경우의수(2,3) 가 생기기 때문에 기존 값보다 긴 LIS 를 생성할 가능성이 생기고, 만약 그렇지 않더라도 

 

1 2 10 2 3  10     

 

하이라이트 된 것 처럼   이전의 10이 생성한 LIS (1,2)를 그대로 가져올 수 있기 때문입니다. 

 

이 생각을 가지고 직접 위의 코드에서   'v'  벡터 내부가 어떻게 변할지 적어가며 이해해 봅시다. 

(꼭!! 직접 해보셔야 합니다. 이 알고리즘의 경우 이해 없이 설명만 보면 더 헷갈려서 백번 설명 보는거 보다

직접하고 왜 이렇게 되는지 이해해야합니다..!)

 

lower_bound 가 어떻게 돌아가는지 이해했다면 이제 간단합니다.

1) 여태까지 vector내부에 들어온 모든 수들보다 큰 수가 들어오면 vector의 뒤에 push_back() 해주고

 

2) 그렇지 않다면 lower_bound() 를 사용하여 치환해준다. 

 

이렇게 1~N까지 다 돌리고, 그 vector의 길이를 구하면, LIS 의 길이가 됩니다.    

(*** 주의 vector 안의 값들은 실제 LIS 가 아닙니다. 길이를 아는 것만 가능합니다!

이 점이 이해가 되지 않는다면 다시 한 번  loop를 돌 때마다 vector에 값이 어떻게 변할지 생각해 봅시다.) 

 

 

2. lis 수열을 출력해라 

쓸만한 LIS 알고리즘들은 전부 LIS의 길이만 알 수 있고, LIS를 구성하는 숫자들은 알 수 없습니다. 

따라서 여기서 추가로 필요한 알고리즘이 바로 '경로 추적' 입니다. 이건 아래링크에 구체적으로 설명해놓았으니 참고해주세요!

https://codenme.tistory.com/9?category=1026697 

경로 추적에 대하여 (다익스트라, 플로이드, )

#include<iostream>
#include<vector>
using namespace std;

int lis[100001]; //해당위치의 값을 마지막으로하는 LIS 길이
int arr[100001];
int main() {
	int N;
	cin >> N;
	int a;
	vector<int> v;


	for (int i = 0; i < N; i++) {
		cin >> a;
		arr[i] = a;
		if (i == 0) {
			
			v.push_back(a);
			lis[i] = 1;
			//continue;
		}
		else if (v.back() < a) {// 증가하는 값, 뒤에 추가!
			v.push_back(a);
			lis[i] = v.size();
			//ans[v.size() - 1] = a;
		}
		else {
			int idx= lower_bound(v.begin(), v.end(), a)-v.begin();
			lis[i] = idx+1;
			*lower_bound(v.begin(), v.end(), a) = a;
		}
		//lis[i] = v.size();

	}
	vector<int> ans;

	int now_lis = v.size();
	for (int i = N - 1; i >= 0; i--) {
		
		if (( ans.empty() || ans.back()>arr[i]) && now_lis == lis[i] ) { //자신을 포함해서 현재까지의 lcs가 완성되는거면 lcs 경로에 추가. 
			ans.push_back(arr[i]);
			now_lis--;
		}

		if (now_lis == 0)break;
		
	}

	reverse(ans.begin(), ans.end());
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << " ";
	}
	cout << endl;
	
	cout << v.size();
	
}

 

 

위가 정답 코드입니다.

lis[i] 에는  i째 값을 마지막으로 하는 lis 의 길이가 저장 되어있습니다.

해당 배열을 거꾸로 거슬러 올라가며 경로추적을 해주면 간단하게 해결 되는 문제였습니다!

 

 

 

2) LCS ( 최장 공통 부분 문자열)

두 문자열에서, 공통된 문자열의 최대 길이를 찾으면 되는 문제입니다.

 

https://www.acmicpc.net/problem/9251

9252번: LCS 2

 

 

 

#include<iostream>
using namespace std;
#include<math.h>
int dp[1001][1001];
int main() {
	string s1, s2;

	cin >> s1 >> s2;
	int s1_len = s1.size(), s2_len = s2.size();

	for (int i = 1; i <= s1_len; i++) {
		for (int j = 1; j <= s2_len; j++) {
			if (s1[i-1] == s2[j-1])
				dp[i][j] = dp[i - 1][j - 1]+1;
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}
	cout << dp[s1_len][s2_len];
}