가장 긴 증가하는 부분 수열 (Longest Increase Sequence)

 

안녕하세요. 이번 포스팅에서는 가장 긴 증가하는 부분 수열문제를 해결해 보도록 하겠습니다.

 

우선 가장 기본적인 포맷은 다음과 같습니다.

 

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

11053번: 가장 긴 증가하는 부분 수열

 

 

 

 

이 문제를 dp로 해결할 수도 있는데, 이번 포스팅에서는 dp를 사용하지 않고 풀어보도록 하겠습니다.

 

#include<bits/stdc++.h>
using namespace std; 
int n, res;
int lis[1000+1];
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);	
	cin >> n;
	vector<int> v(n);
	
	for(int i = 0; i < n; i++) cin >> v[i];
	
	for(int i = 0; i < n; i++) {
		int maxVal = 0;
		for(int j = 0; j < i; j++) {
			if(v[j] < v[i] && lis[j] > maxVal) {
				maxVal = lis[j]; 
			}
		}
		lis[i] = maxVal+1;
		res = max(res, lis[i]);
	}
	
	cout << res << endl;
 	return 0; 
}

 

이 문제의 경우 시간제한 1초에 N의 제한이 1000까지이므로 N^2의 알고리즘도 충분히 사용 가능합니다. 

 

이중 포문을 돌면서, 현재 j가 가리키는 인덱스가 i를 가리키는 인덱스보다 작고, (즉 이전의 부분수열중 일부가 되고)

j의 lis배열 (j까지의 최대 증가 수열의 수)보다 지금까지 센 count가 적다면, 

 

Count를 lis[j]로 변경해주시면 됩니다. 그리고 j의 루프가 끝났다면 lis[i]에 이전까지의 최대 증가수열의 count 수 + 1을 갱신해주면 됩니다.

 

코드로 보았을 때 직관적으로 이해하기 어려운 부분은 없습니다.

 

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

14002번: 가장 긴 증가하는 부분 수열 4

 

그 다음 단계로 이 문제를 해결해보도록 하겠습니다.

 

 

이 문제의 경우 위 문제와 제한은 똑같지만, 가장 긴 증가하는 부분 수열의 경로를 출력해야 합니다.

 

#include<bits/stdc++.h>
using namespace std; 
int n, start, res;
int lis[1000+1];
int trace[1000+1];
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);	
	cin >> n;
	vector<int> v(n);
	
	for(int i = 0; i < n; i++) cin >> v[i];
	
	fill(trace, trace+1001, -1);
	for(int i = 0; i < n; i++) {
		int maxVal = 0;
		for(int j = 0; j < i; j++) {
			if(v[j] < v[i] && lis[j] > maxVal) {
				maxVal = lis[j];
				trace[i] = j; 
			}
		}
		lis[i] = maxVal+1;
		if(res < lis[i]) { 
			res = lis[i], start = i;
		}
	}
	
	vector<int> path;
	while(trace[start] != -1) {
		path.push_back(start);
		start = trace[start];
	}
	path.push_back(start);
	
	cout << res << "\n";
	for(int i = path.size()-1; i >= 0; i--) cout << v[path[i]] << " ";
	
 	return 0; 
}

 

기본적인 알고리즘은 처음 문제와 같습니다. 하지만 이 문제의 경우 지나온 경로를 출력해야 합니다. 따라서 maxVal만 갱신하는 것이 아니라,

 

maxVal이 갱신된다면, 현재를 기준으로 가장 긴 증가하는 부분 수열의 전 단계는 j이므로 trace[i] = j 

즉 i의 전단계는 j이다 라는 사실을 기록해주면 됩니다.

 

그리고 이제 마지막으로 res가 갱신되는 순간의 끝점부터 시작하여 다시 처음으로 회귀하면 됩니다. 저는 처음에 배열을 -1로 초기화하여, 배열의 값이 -1이 아닌 동안 계속 while loop로 지나온 path를 추가해 주었고, 마지막에 -1인 시작점을 추가해 주었습니다.

 

마지막으로 

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

14003번: 가장 긴 증가하는 부분 수열 5

 

가장 긴 증가하는 부분 수열 5를 보도록 하겠습니다.

 

 

문제에서 요구하는 바는 같습니다. 하지만 범위가 1000000까지 늘어났습니다.

 

범위가 1000000이면 죽었다 깨어나도 N^2의 알고리즘으로는 해결할 수 없습니다. 따라서 저희는 NlogN 이하의 알고리즘을 찾아야합니다.

 

우선 이 문제를 해결하기 위해 기본적인 이분 탐색과 lower_bound를 이해하고 계시면 좋습니다.

https://chanho0912.tistory.com/13?category=871243 

[C++/Algorithm] upper_bound, lower_bound 이해하기

 

lower_bound를 활용하여 결과 배열을 계속 만들어간다고 생각하시면 됩니다.

 

#include<bits/stdc++.h>
using namespace std; 
int n, MINVAL = -1000000001;
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);	

	cin >> n;
	
	int len = 0;
	vector<int> v(n), lis(n, MINVAL), res;
	vector<pair<int,int>> ans(n); 
	for(int i = 0; i < n; i++) {
		cin >> v[i];
		auto lower_pos = lower_bound(lis.begin(), lis.begin()+len, v[i]);
		int lower_posIdx = (int)(lower_pos-lis.begin());
		if(*lower_pos == MINVAL) len++;	
		*lower_pos = v[i];
		ans[i].first = lower_posIdx;
		ans[i].second = v[i];
	}
	
	cout << len << endl;
	
	for(int i = n-1; i >= 0; i--) {
		if(ans[i].first == len-1) {
			res.push_back(ans[i].second);
			len--;	
		}			
	}
	reverse(res.begin(), res.end());
	for(auto a : res) cout << a << " ";
 	return 0; 
}

 

만약에 input으로 

6

10 20 10 30 20 50

 

이 입력되었다고 생각해볼게요. 그러면 초기 배열은 MINVAL로 초기화되어있습니다. 그리고 len이 0입니다. 따라서 lower_bound(lis.begin(), lis.begin()+len, v[i])를 수행하였을 때 v[i]의 값을 찾지 못하고 MINVAL을 반환하게 됩니다.

 

저희는 len을 1 증가시키고 (결과 배열의 길이가 1 증가됨)

결과 배열에 10을 넣습니다.

 

같은 방식으로 20도 넣게 됩니다.

 

이 상황에 10이 들어오게 되면, 결과 배열에 10이 있는 인덱스의 위치를 반환합니다. 이를 10으로 대체합니다.

 

이 방식으로 진행하면 

 

10

10 20

10 20

10 20 30

10 20 30

10 20 30 50

 

의 순으로 결과 배열이 바뀌게 됩니다. 하지만 이 방법만 사용하게 되면, 

4
1 5 10 4

의 반례를 만나게 됩니다. 이 경우 1 4 10이 결과로 반환되는데, 4는 10 이후의 원소이므로 오답입니다. 이를 해결하기 위해서 인덱스의 정보도 같이 저장한 뒤, len -1부터 역행하며 찾아가면서 값을 찾았다면, 그 이전의 값만을 대상으로 결과에 추가해주시면 됩니다.

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.