[11053] 가장 긴 증가하는 부분 수열

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

입력 1

6
10 20 10 30 20 50

출력 1

4

1. 문제 설명

• 크게 2가지 방법으로 풀 수 있다.

1-1. DP방식으로 해결하는 방법 (시간복잡도 : \(O(n^2)\))

(사진 출처 : 우투리와 툴툴님 블로그)

• MAX라는 변수를 두고 이중 for문으로 값을 비교해가며 푸는 방법이다.
  과거의 값들을 참고하여 그 중 최대값으로 현재의 값을 정한다. 그래서 각 부분마다 이전에 저장했던 배열값을 검색해야한다. 바로 위 사진이 이해하기 쉽게 보여주고있다.

1-2. Vector & STL을 사용하는 방법 (시간복잡도 : \(O(NlogN)\))

• 이진 탐색을 사용하는 STL(lower_bound)을 이용해서 푸는 방법이다.
  (벡터의 사용법은 기본적이니 설명은 생략하며 그림의 *pos는 lower_bound의 리턴값이다.)

• lower_bound란?
• 이진탐색 기반의 탐색 방법을 사용하는 STL이다. (배열 또는 리스트가 정렬되어 있어야 한다.)
• 입력된 값과 같은 값이나 큰 값 중 가장 작은 값을 찾아내어 준다.

• 이 방법은 3가지 특징이 있다.
  1. dp배열의 제일 마지막 값보다 새로 들어올 값이 클 경우에는 push_back을 사용하여 제일 끝에 추가시킨다.
  2. dp배열의 마지막 값보다 작을 경우에는 lower_bound를 사용하여 해당 자리에 넣어준다.
  3. 배열의 길이는 곧 가장 긴 부분 수열의 길이이다.

2. 소스코드

[1-1]방식의 소스코드

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

using namespace std;

int main() {
	int n, MAX = 0;

	cin >> n;

	vector<int> a(n + 1, 0);
	vector<int> dp(n + 1, 0);

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	for (int i = 1; i <= n; i++) {
		int temp = 0;
		for (int j = 0; j < i; j++) {
			if (a[j] < a[i]) {
				temp = max(temp, dp[j]);
			}
		}

		dp[i] = temp + 1;
		MAX = max(MAX, dp[i]);
	}

	cout << MAX << endl;

	return 0;
}

[1-2]방식의 소스코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
	int n, num;
	vector<int> dp;
	dp.push_back(-1);

	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> num;

		if (num > dp.back()) {
			if (dp.back() == -1) {
				dp.clear();
			}
			dp.push_back(num);
		}
		else {
			auto pos = lower_bound(dp.begin(), dp.end(), num);
			*pos = num;
		}
	}

	cout << dp.size() << endl;

	return 0;
}