BOJ 백준 11053 가장 긴 증가하는 부분 수열 <LIS>

https://www.acmicpc.net/problem/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

  

문제에 써 있는 그대로, {a1, a2, a3, .., an}의 집합이 있을 때 a1 < a2 < a3 < ... < an 을 만족하는 것을 증가하는 수열이라 하고

이 집합의 부분집합 중 원소가 가장 많을 때의 원소 수를 출력해주면 되는 문제이다.

  1. O(n^2)

dp문제로 이중for문을 돌면서 각 원소들이 마지막일 경우 증가하는 부분 집합의 원소 개수가 몇 개인지를 dp 배열에 저장해주면 된다.

for i = 0 ; i < n

dp[i] = 1;

for j = 0 ; j < i

if(arr[i] > arr[j] && dp[i] < dp[j] + 1) // i번째 원소(마지막이라고 가정하는 원소)가 j번째 원소보다 크고, j번째 원소까지의 부분수열에

dp[i] = dp[j] + 1;                    // i번째 원소를 추가해주는 것이므로 dp[i]에 dp[j] + 1을 넣어준다.

#include <iostream>
#define SIZE 1001

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int arr[SIZE] = {0};
	int dp[SIZE] = {0};
	
	int n, i, j;
	
	cin >> n;
	for(i = 0; i < n; ++i)
	{
		cin >> arr[i];
	}
	for(i = 0; i < n; ++i) 
	{
		if(dp[i] == 0) dp[i] = 1;
		for(j = 0; j < i; ++j)
		{
			if(arr[j] < arr[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
		}
	}
	int iMax = -1;
	for(i = 0; i < n; ++i)
	{
		if(dp[i] > iMax) iMax = dp[i];
	}
	cout << iMax << '\n';
	
	return 0;
}

 2.  O(NlogN)

위의 방법이 이중for문으로 O(N^2) 였다면 이번 방법은 이진 탐색을 N개의 원소를 대상으로 이루어지므로 O(NlogN)의 시간복잡도로 풀 수 있다.

vector<int> 를 하나 만들어주고, 가장 작은 값을 한 개 푸쉬해준다.

그 다음 값들을 입력받아올 때, 입력받아온 값이 vector의 마지막 원소와 비교해서, 만약 vector의 마지막 원소보다 큰 경우 push해주고,

마지막 원소보다 작은 경우에는 lower_bound를 통해 입력한 값보다 같은 값이나 큰 값 중에 가장 작은 값을 하나 찾아내어 그 곳에 입력한 값을

넣어준다.

이런 식으로 증가하는 수열의 집합을 vector에 저장해나가면서 push_back할 경우에만 원소 개수를 1씩 증가시켜주면 된다.

#include <iostream> 
#include <utility> 
#include <algorithm>
#include <vector>
#define SIZE 1001
#define INF	0xFFFF

using namespace std;

int main()
{
	vector<int> v;
	v.push_back(-INF);


	int n;
	cin >> n;
	int x;

	for (int i = 0; i < n; ++i)
	{
		cin >> x;
		if (x > v.back())
		{
			if (v.back() == -INF) v.clear();
			v.push_back(x);
		}
		else
		{
			auto it = lower_bound(v.begin(), v.end(), x);
			*it = x;
		}
	}

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

	return 0;
}