[C/C++] 백준 12015번 - 가장 긴 증가하는 부분 수열 2 (LIS)

 

<코드>

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

int N, x;
vector<int> v;

int main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> x;

		if (v.empty() || v.back() < x)
		{
			v.push_back(x);
		}
		else
		{
			auto iterator = lower_bound(v.begin(), v.end(), x);
			*iterator = x;
		}
	}
	cout << v.size();
}

 

풀이 방법

 

가장 긴 증가하는 부분 수열 1

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

11053번의 경우 N은 최대 1000이고 DP를 통해 쉽게 풀이를 할 수 있었다. 그러나 이번 문제의 경우 N은 최대 1,000,000이고 O(N²)의 시간 복잡도를 가진 알고리즘은 시간 초과가 발생하게 된다.

알고리즘 분류를 보면 "이분 탐색"이라고 적혀있으며, 이분 탐색을 이용한다면 O(NlogN)의 시간 복잡도로 시간 초과 없이 통과를 할 수 있다.

<알고리즘>

1. 벡터를 생성한 후 첫 번째 수를 벡터에 넣는다. (v[0])
2. 두 번째 수를 입력받고 벡터의 마지막 원소(v.back(), 현재 마지막 원소는 v[0])를 두 번째 수와 비교한다.
   1. 두 번째 수가 벡터의 마지막 원소보다 크다면 벡터의 마지막에 두 번째 수를 추가한다.
   2. 두 번째 수가 벡터의 마지막 원소보다 작다면 벡터의 원소들 중에서 두 번째 수보다 다음으로 작은 원소의
      인덱스를 i라 할 때 i+1번째에 원소를 두 번째 수로 교체한다.
3. 이후의 입력받는 수들도 위와 같은 방식으로 진행한다. 

 

예를 들어 수열 A = {1, 2, 4, 6, 7, 5, 3, 8}이 있다고 한다면,

1. 1을 v에 push 한다. (v={1})
2. 2는 v.back() = 1 보다 크므로 v에 push 한다. (v={1, 2})
3. 다음 입력되는 4, 6 ,7도 마찬가지로 같은 방식으로 v에 push 한다. (v={1, 2, 4, 6, 7})
4. 5는 v.back() = 7보다 작으므로 5 다음으로 작은 수는 v[2] = 4이므로 v[3]를 5로 수정한다. (v={1, 2, 4, 5, 7}) 
5. 3은 v.back() = 7보다 작으므로 3 다음으로 작은 수는 v[1] = 2이므로 v[2]를 3으로 수정한다. (v={1, 2, 3, 5, 7}) 
6. 8은 v.back() = 7 보다 크므로 v에 push 한다.

 

하지만 위의 알고리즘으로 구한 수열은 "가장 긴 증가하는 부분의 수열"이 아닐 수 도 있습니다.

그러나 가장 긴 증가하는 부분의 수열 길이를 구할 때는 일치하게 됩니다.

 

 

www.acmicpc.net/problem/12015

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