BAEKJOON 11053:가장 긴 증가하는 부분 수열 O(nLogn) for C++(DP)

LIS를 해결하는 시간 복잡도 O(nLogn)의 알고리즘

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

---

코드

#include <iostream>

using namespace std;

int main() {
	int n;
	cin >> n;
	int* input, * dp;
	input = new int[n];
	dp = new int[n + 1]{};
	for (int i = 0; i < n; ++i)cin >> input[i];

	int maxLength = 1;
	for (int i = 0; i < n; ++i) {
		if (dp[maxLength - 1] < input[i]) {
			dp[maxLength++] = input[i];
		}
		else {
			int left, right;
			left = 1;
			right = maxLength - 1;
			while (left < right) {
				if (dp[(left + right) >> 1] < input[i]) {
					left = ((left + right) >> 1) + 1;
				}
				else {
					right = ((left + right) >> 1);
				}
			}
			dp[left] = input[i];
		}
        /*
		for (int i = 0; i < maxLength; ++i) {
			cout << dp[i] << " ";
		}
		cout << "\n";
        */
	}
	cout << maxLength -1;
	return 0;
}

 

설명

 이 알고리즘의 핵심은 증가 수열 중 각 길이별 최대 값이 가장 작은 수를 찾는 것이라 볼 수 있겠다. 각 수열의 마지막 요소의 값이 작을 수록 더 긴 수열을 만들 확률이 높아진다. 또한, 마지막 요소의 값을 알고 있다면 굳이 그 이전의 값을 알 필요는 없다.

 배열 dp에는 각 길이별 마지막 요소의 가장 작은 값을 저장하도록 코드가 구성되어 있다. 또한, dp[i]는 절대적으로 dp[i+1]보다 작을 수밖에 없다. 만일 dp[i]가 dp[i+1]보다 큰 값을 가지고 있다면 dp[i+1]은 이전 탐색 과정에서 dp[i]보다 큰 값을 발견했어야하나 발견되지 않았기 때문이라 볼 수 있다. dp[i+1]보다 큰 값이 있다면 dp[i+2]로 정해질 수 있으므로 길이가 1만큼 더 긴 증가 수열이 발견된 것으로 볼 수 있다.

---

함께 보기.

O(n²)로 해결하는 알고리즘

BAEKJOON 11053:가장 긴 증가하는 부분 수열 O(n²) for C

 

# index