동적 계획법 - LIS (가장 긴 증가하는 부분 수열)

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

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

책을 공부하기 전 잠깐 동적 계획법에 대해 공부한 적이 있었다. 이 때, 위 문제를 푼 적이 있었고 그때도 물론 이 문제를 오랜시간 고민하다 결국 다른 분들 설명을 보고 풀었던 기억이 있다. (https://wonsjung.tistory.com/65?category=949214) 이 코드를 보면 2중 for문으로 (완전탐색 + 메모제이션) O(n^2)의 시간복잡도를 가진다.

문제에서는 최대 n의 크기가 1000이기 때문에 시간 내에는 해결할 수 있지만 n의 크기가 커진다면 결코 효율적인 해결방법이 될 수 없을 것이다.

 

그러면 어떻게 효율적인 시간복잡도를 가지는 LIS해결방법이 존재할까? 

(https://jason9319.tistory.com/113)

[최장 증가 수열] LIS(Longest Increasing Subsequence)

정말 이해가 쏙쏙 되는 설명을 올려주신 분이 계신다. 위 블로그에서 설명하는 방법을 사용하면

O(nlogn)으로 해결이 가능하다.

 

하나 입력할 때마다 최신화 시켜주는 방법인데, 만약 부분 수열을 이루는 원소를 하나 변경해야할 때,

이분 탐색을 응용한 lower_bound를 이용해주는 것이다. 그럼 n의 길이를 가지는 수열의 최장 증가 부분 수열을 찾을 때 

for문(O(n)) * lower_bound(O(logn))에 의해 O(nlogn)이 되는 것이다.

 

위 블로그 설명을 보고 짜본 문제에 대한 코드이다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N;
	cin >> N;

	vector<int> Answer;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		if (Answer.empty()) Answer.push_back(x);
		else {
			int Data = Answer.back();
			if (Data < x) {
				Answer.push_back(x);
			}
			else {
				int pos = lower_bound(Answer.begin(), Answer.end(), x) - Answer.begin();
				Answer[pos] = x;
			}
		}
	}
	cout << Answer.size() << endl;

	
	return 0;
}