[C++] 12015 : 가장 긴 증가하는 부분 수열 2

골드 Ⅱ

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n;
	scanf("%d", &n);

	vector <int> seq;
	int s;
	for (int i = 0; i < n; i++) {
		scanf("%d", &s);
		seq.push_back(s);
	}
	vector <int> subsq;
	subsq.push_back(seq[0]);
	int idx;
	for (int i = 1; i < n; i++) {
		if (subsq.back() < seq[i]) {
			subsq.push_back(seq[i]);
		}
		else {
			idx = lower_bound(subsq.begin(),subsq.end(), seq[i]) - subsq.begin();
			subsq[idx] = seq[i];
		}
	}
	printf("%d", subsq.size());
} 

 

(+ 위의 코드에서 seq를 저장하는 벡터가 필요없으므로 수정함)

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n;
	scanf("%d", &n);

	int s;
	scanf("%d", &s);
	vector <int> subsq;
	subsq.push_back(s);

	int idx;
	for (int i = 1; i < n; i++) {
		scanf("%d", &s);
		if (subsq.back() < s) {
			subsq.push_back(s);
		}
		else {
			idx = lower_bound(subsq.begin(),subsq.end(), s) - subsq.begin();
			subsq[idx] = s;
		}
	}
	printf("%d", subsq.size());
} 

 

(메모리 8172KB -> 2016KB로 감소)

 

LIS 알고리즘

두 번째 풀이 방법인 O(nlogn)을 사용했다

근데 한 가지 주의할 점은

 

이 문제가 LIS의 "길이"를 구하라고 했기 때문에

위의 코드에서 subsequence는 실제로 LIS가 되지 않는다

따라서 만약 이 문제 + LIS를 출력하시오 라는 문제에

단순히 위의 subsequence를 출력해서 제출하면 당연히 틀린다

그래서 틀린 문제가 아마 백준에 있을 거다 이제 그것도 풀러 가야지...

 

그러면 어떻게 subsequence가 실제로 LIS가 되지 않는데

LIS의 길이를 출력하는 문제에서는 정답이 될까???

 

그건 알고리즘을 잘 뜯어보면 된다

 

애초에 내가 이 알고리즘을 알게 됐을 때

굉장히 허접하다고 생각했는데 그 이유가

?? 이걸로 정말 최장 부분 수열을 구할 수 있단 말이야?라고 생각했기 때문이다

 

실제로 못 구한다! 이 알고리즘으로는 죽었다 깨어나도 정확하게 LIS를 구할 수 없다

그러나 LIS의 길이만은 정확하게 구할 수 있기 때문에 이 알고리즘을 사용한 것이다

 

일단 이 알고리즘은 subseq에 LIS를 저장하는 것처럼 보인다

그러나 제대로 된 알고리즘이라면 새로 들어온 원소로 만들어지는

LIS가 더 긴 경우에만 subseq를 바꿀 것이다

하지만 위의 코드는 무조건 subseq를 업데이트 시킨다.

아래의 예를 보자

 

예를 들어서, 입력이 1 3 5 2 6 4 8 로 들어온다고 하자

1 3 5 까지 들어오면

subsq : 1 3 5

가 된다

다음, 2가 들어올 때 2로 인해서 만들어지는 LIS가 현재 subsq의 길이인 2보다

길어질지 아닐지 모르기 때문에 일단 보류해야 할 것이다 (새로운 부분 수열을 만들든지 해서)

그러나 위의 코드를 보면, 2가 5보다 작으므로 

subsq : 1 2 5

가 된다

 

보면 전혀 뚱딴지같은 부분 수열이 subsq에 들어있는 걸 볼 수 있다.. 아니애초에 1 2 5는 1 3 5 2 6 4 8에서 나올 수 없는 부분 수열이다 2가 5보다 뒤에 있으니

 

그러나 이렇게 하는 이유는

1 2~ 로 시작하는 부분수열의 길이가

그전에 만들어놓은 부분 수열(1 3 5)의 길이인 3을 넘기 시작하면

자동으로 1 2~로 시작하는 부분수열로 대체되기 때문이다

 

따라서 단순히 LIS의 길이를 구하는 문제인 12015에서,이 알고리즘은 타당하다!

 

그럼 이제 nlogn으로 실제 LIS를 구하는 문제를 풀어보자...

 

 

 

( + 이해가 안된다면 아래의 코드 이용하기..)

 

	for (int i = 1; i < n; i++) {
		if (subsq.back() < seq[i]) {
			subsq.push_back(seq[i]);
			printf(" + %d 넣음\n", seq[i]);
		}
		else {
			idx = lower_bound(subsq.begin(),subsq.end(), seq[i]) - subsq.begin();
			printf(" * idx(lower bound) : %d\n", idx);
			subsq[idx] = seq[i];
			printf(" * subsq[%d] 에 %d 대입\n", idx, seq[i]);
		}
	}

 

만약 이해가 안 됐다면 for문 이걸로 바꿔서 돌려보렴 미래의 나야...

아 근데 이건 첫번째 코드 용이야.. 두번째로 하고 싶으면 printf를 알아서 잘 넣어봐