[DP] Longest Increasing Subsequence (LIS)

Dynamic Algorithm을 응용하여 풀 수 있는 문제중에 최장 증가 부분수열 문제가 있다.

해당 문제는 주어진 수열에서 가장 긴 부분 수열을 찾는 문제이다.

보통 오름차순,내림차순 등의 조건이 주어지니 Bottom-Up 방식으로 판별해나가면된다.

 

백준에서 풀이해볼 수 있는 문제는 11053번 문제이다.

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

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

 

내가 풀이한 방법은 다음과 같다.

N^2의 시간복잡도를 가진다.

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

int main() {
	int n
	cin >> n;
	vector<int>v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	//수열의 길이를 count하기 위한 vector
	vector<int>s(n);

	//n^2의 시간복잡도
	//0부터 판별중인 수까지 순회하며 가장 큰 부분수열을 진행중인수에서 +1
	for (int i = 1; i < n; i++) {
		s[i] = 1;
		for (int j = 0; j < i; j++) {
			if (v[j] < v[i] && s[i] < s[j]+1) {
				s[i] = s[j] + 1;
			}
		}
	}
	int answer = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] > answer) {
			answer = s[i];
		}
	}
	cout << answer;
	return 0;
}

 

포스팅을 작성하며 다른 풀이를 찾는 중 

내 풀이방법(N^2)보다 더 빠른 성능(N log N)의 풀이방법을 발견하였다.

i번째 수를 찾기위해 j를 모두 순회하는것보다 i를 만족하는 j를 계속해서 저장해놓는 방식이다.

해당 과정은 나무위키에 잘 정리되어있다. 두번째 NlogN 알고리즘 참조

 

 

https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4