[C/C++] 백준 12015: 가장 긴 증가하는 부분 수열2 (O(logn) 알고리즘)

ㅣhttps://www.acmicpc.net/problem/12015

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

풀이!

이 문제를 기존의 11503: 가장 긴 증가하는 부분 수열 푼 방식으로 풀 경우에는 해결이 불가능하다. 그 이유는 11503 문제의 알고리즘은 시간복잡도가 O(n^2)로 구현해도 해결이 가능했지만 이 문제는 수열의 크기가 10^6이므로 똑같이 시간복잡도가 O(N^2)가 되어 시간초과가 발생하게 된다. 그렇기 때문에 새로운 아이디어를 생각해야한다. 일단 가장 기본적인 알고리즘은 11503 문제에 설명이 되어있기 때문에 이것을 공부하고 싶은 분은 아래 포스팅을 참고하면 된다!

https://donggul-godsang.tistory.com/23

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

O(log n) 알고리즘

 따라서 이 문제는 시간복잡도를 줄여 nlog n의 알고리즘을 찾아 이용해야한다. 사실 위 알고리즘에서 시간복잡도가 O(n^2)이 된 이유는 dp[]배열에 탐색에서 가장 큰 수를 찾는 과정 때문이었다. 따라서 이 "탐색"을 다른 방법을 이용하여 시간 복잡도를 줄이면 된다.

  이 과정에서 생각한 방법은 dp[i]배열은 "arr[i](1~n)번째 index까지의 증가하는 부분 수열의 길이"를 구하는 것이 아니라 "i번째 index에 부분 수열의 길이가 i인 수"를 저장하도록 바꾼다. 

 

동작 방법!

간단하게 요약하면 dp[i]= 부분 수열의 길이가 i인 수 중 가장 작은 값이 된다. 

 arr[i]에서 새로운 수가 들어왔을 때 dp배열에 어떻게 들어가게 되는지 생각을 해보자. tmp=arr[i]라고 했을 때 tmp는 가능한 가장 긴 부분 수열의 길이를 만들어줘야하므로 dp[] 배열에서 탐색을 하다가 자기보다 큰 수(big_index) 바로 밑(big_index-1)에 위치를 하게 된다. 그리고 이 탐색은 lower_bound를 이용했다. 이렇게 된다면 dp배열의 0부터 big_index-2까지의 저장되어 있는 수는 tmp보다 작게 되어 부분 수열의 길이가 big_index라는 것을 쉽게 알 수 있다.

 

 이때 주의해야할 점이 2가지가 있다.

 

 1. 새로 들어온 수가 가장 클 때 

 새로 들어온 수가 가장 클 때는 dp배열의 마지막 index 위에 저장하게 된다. 이렇게 될 경우 dp배열의 크기를 저장하고 있는 변수 max_index의 값을 하나 늘려줘야한다. 그래야만 현재까지 이루고 있는 가장 긴 증가하는 부분 수열의 길이를 쉽게 알 수 있다.

 

 2. 새로 들어온 수의 index값에 이미 배열의 값이 존재할 때

 이 같은 경우에는 새로 들어온 수와 기존의 배열 값을 비교하여 더 작은 수를 dp[]배열에 넣어준다. 이렇게 하는 이유를 간단한 예로 들어서 설명을 하면

 

ex) max_index=2이고 dp[0]=0 dp[1]=3이라고 해보자. 이때 남은 arr[]배열의 값이 순서대로 1와 2라고 하자.

step 1. 1은 dp[1]에 위치해야하고 기존의 dp[1] 값보다 작기 때문에 dp[1]=1이 된다.

step 2.이후 2가 들어모녀 dp[]배열에서 가장 큰 수 이므로 max_index를 3으로 늘리고 dp[2]=2가 들어온다.

if. 처음 step1에서 1과 dp[1]의 비교에서 dp[1]를 그대로 남겨두었다면 step 2가 들어와도 dp[]배열에서 가장 큰 수가 되지 않아 max_index의 값이 2로  유지되어 답이 다르게 된다.

 즉, 더 작은 수를 dp[]배열에 넣어야만 가장 긴 부분 수열을 만들 수 있는 가능성이 커지게 된다. 

 

lower_bound 완전 정복 (STL)

lower bound란?

 동작 방법은 위와 같이 되고 이 문제에서 시간복잡도를 줄인 가장 중요한 컨셉이 lower_bound를 이용한 탐색이기 때문에 이에 대해서 자세하게 다뤄보고자 한다. 

auto k=lower_bound(arr+first,arr+last,value)

 //first: 첫번째 원소를 나나태는 반복자, last:마지막 원소 바로 다음을 가르키는 반복자

 

 위와 같이 상세하며 범위 [first,last)안의 원소들 중, value보다 크거나 같은 첫번째 원소의 주소를 리턴한다. 만약 그런 원소가 없다면(모든 원소들이 자신보다 작다면) last를 리턴한다. lower_bound 함수를 사용하기 위해서는 arr 배열안의 범위 안에 있는 원소들이 모두 정렬되어 있어야 한다.

 

주의해야할점! 

 여기서 주의해야할 점은 lower_bound 안에 들어가는 변수들은 arr배열에서 몇번째 index를 가지는지를 적어줘야하지 몇번째 index에 주소를 적어주면 안된다. 또한 last는 arr 배열에 포함이 되어 있지 않는 인덱스인 것을 알고 있어야하고 lower_bound의 return 값은 주소이기 때문에 int값으로 바로 받을 수 없다.

 이 lower_bound의 시간복잡도는 O(log(last-first))가 되는데 그 이유는 lower_bound가 이진 탐색을 통해 자신보다 크거나 같은 원소를 찾기 때문이다.

 

 Lower_bound를 이용하여 index 구하기

  Lower_bound의 return값은 arr배열에서의 index가 아닌 주소가 된다. 그렇기 때문에 lower_bound return 값만을 통해 직접 이 위치로 이동하여 값을 알아내거나 바꿀 수 없다. 그렇기 때문에 arr배열에서의 위치를 찾기 위해서는 return한 주소값에서 arr배열의 첫번째 원소의 주소를 빼서 알 수 가 있다.

int j=lower_bound(dp,dp+max_index,arr[i])-dp;

위와 같은 코드를 통해 index를 구하여 이 문제에서 dp배열에 몇번쨰 index에 값을 추가하거나 바꿀지 정할 수 있다 

 

 

 

정답 소스코드!

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<limits.h>
#include<math.h>
#include<cmath>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
int arr[1000002];
int dp[1000002];

int main() {    
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>arr[i];
  }
  dp[0]=arr[0];
  int max_index=1;
  for(int i=1;i<n;i++){
    int j=lower_bound(dp,dp+max_index,arr[i])-dp;        
    dp[j]=arr[i];
    if(j==max_index)
      max_index++; 
  } 
 
  cout<<max_index;  
  
}

 

 

 

 

<O(n^2) 알고리즘>

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<limits.h>
#include<math.h>
#include<cmath>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
int arr[1000001];
int dp[1000001];

int main() {    
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>arr[i];
  }
  dp[1]=arr[1];
  int max_index=1;
  for(int i=2;i<=n;i++){
    int j;
    for(j=1;j<=max_index;j++){
      if(dp[j]>arr[i]) //만약 새로 들어온 수가 기존 배열의 수보다 작을 때 그 자리에 들어가야함
        break;
    }
    dp[j]=arr[i];
    if(j==max_index+1)
      max_index++;
  } 
   
  cout<<max_index;
  
  
}