문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.
풀이
기본적으로 가장 긴 증가하는 부분수열문제는 N^2의 자명한 풀이 방법이 있다.
특정 원소를 기준으로 잡고, 따로 저장해놓은 이전 노드들의 부분수열의 개수를 체크하면서 나아가는 방식이다.
하지만 특정 원소를 기준으로 잡는데 N, 이전 노드들의 가장 긴 증가하는 수열을 체크하는 시간이 N이므로 N의 제한범위가 이 문제와 같이 큰 수가 나온다면, 다항시간으로는 풀 수 없게된다.
그러므로 이 문제는 흔히 알려진 NlogN LIS 알고리즘을 사용해야 한다.
각각의 노드를 기준으로 삼아야 하는 것은 똑같고, 이전노드들의 가장 긴 증가하는 수열을 체크하는 시간을 줄여야 한다.
줄이기 위해서는 하나의 벡터를 만들어 주면 된다.
그 안에 LIS의 크기가 1일 경우에 가장 작은수, 2일경우에 가장 작은수 등등을 저장해나가는 방식으로 만약 10 20 50 30 40 이라는 수열이 나왔을떄
10을 체크할때는 벡터가 비어있으므로 1, 10을 넣어주면 되고
20을 체크할때는 벡터의 back이 1, 10이고, 10보다는 20이 크므로 2, 20을 넣어준다.
50을 체크할때는 마찬가지로 벡터의 back보다 50이 더 크므로 3, 50을 넣어준다.
30을 체크할때는 벡터의 back보다 30이 작으므로, 벡터의 수 중 30보다 작은 수를 찾아야한다. 그러면 이 문제의 경우에서는 2, 20이 나오게 된다. 그러므로 30의 경우에 LIS는 3이라는 것을 알 수 있고, 벡터의 3에 해당하는 수인 50보다 30이 작으므로 50 -> 30을 해준다.
40을 체크할때는 이전에 갱신해준 벡터의 back인 3, 30보다 40이 크므로 4, 40을 넣어준다.
그러므로 각각의 원소의 LIS의 개수는
1, 2, 3, 3, 4 가 나오게 되고
체크하기 위한 벡터는
{1, 10}, {2,20}, {3,30}, {4.40}이 된다.
위에 상기한 탐색 과정을 이분탐색을 이용하면, NlogN으로 문제를 풀 수 있다.
주의
수열을 이루고 있는 숫자가 abs(1000000000)보다 작은 정수이다.
그러므로 초기값을 처리해줄때( v.push_back(작은값)) 0이 아닌 -1000000000보다 작은 값을 넣어주어야 한다.
정답 코드
#include <iostream>
#include <vector>
using namespace std;
int N, arr[1000001], dp[1000001], ans, idx;
vector<int>v;
void func(int a, int n, int c){
if(a == 0)
return;
if(n == ans){
func(a-1, n-1, c);
cout<<arr[a]<<' ';
}else if(n == dp[a] && arr[a] < c){
func(a-1,n-1, arr[a]);
cout<<arr[a]<<' ';
}else{
func(a-1,n,c);
}
}
int main(){
cin>>N;
v.push_back(-1000000001);
for(int i=1; i<=N; i++){
cin>>arr[i];
}
for(int i=1; i<=N; i++){
if(arr[i] > v.back()){
dp[i] = v.size();
v.push_back(arr[i]);
}else{
int left = 0, right = v.size()-1;
while(left <= right){
int mid = (left+right)/2;
if(v[mid] < arr[i])
left = mid+1;
else
right = mid-1;
}
dp[i] = (left+right)/2+1;
v[(left+right)/2+1] = min(arr[i],v[(left+right)/2+1] );
}
}
for(int i=1; i<=N; i++){
if(dp[i] > ans){
ans = dp[i];
idx = i;
}
}
cout<<ans<<'\n';
func(idx,ans,arr[idx]);
}