[BOJ] 12738, 14003 LIS(가장 긴 증가하는 수열, 이분탐색) - 2

https://www.acmicpc.net/problem/12738

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

 

n이 100만이므로 O(nlogn)의 풀이를 택해야 합니다.

이번엔 이분탐색을 이용해서 풀어보도록 하겠습니다.

 

참고로 이분탐색은 빠르게 개수는 찾을 수 있지만, LIS가 항상 올바른 순서로 있다고 장담할 순 없습니다.

 

lower_bound함수를 이용하면 t보다 같거나, 큰 가장 최소의 인덱스를 반환해줍니다.

예를들면 arr[3] = {1,5,6} 일때 lower_bound(arr, arr+3, 3) - arr 을 하면 1이 나옵니다.

또한 lower_bound(arr, arr+3, 5)를 해도 1이 나옵니다. 만약 7처럼 완전 큰 수면 arr의 size를 반환합니다.

c++ reference를 찾아보시길 바라겠습니다. 물론 직접 구현한것도 있습니다.

 

예시는 저번과 같이 arr[6] = {1,5,6,2,3,4} 로 해보겠습니다.

 

vector<int> v 로 두겠습니다.

이 v는 항상 오름차순으로 정렬되기 때문에 lower_bound를 수행할 수 있습니다.

왜 오름차순인가? 는 이제 보면 됩니다.

 

v[0] = 1이 들어갑니다.

 

i = 1일때, lower_bound(v.begin(), v.end(), arr[1])-v.begin()을 하면 arr[1]은 5이기 때문에

v의 최댓값인 1을 반환할 것 입니다.

 

lower_bound가 항상 같거나 큰 위치를 반환해주므로 오름차순을 보장할 수 있습니다.

 

v[1] = 5입니다.

이제 v = {1,5}가 들어가있습니다.

 

i = 2일때 6을 찾으면 3을 반환합니다. (가장 큰 수이므로)

v = {1,5,6} 이 됩니다.

 

i = 3일때, 여기부터 바뀝니다.

lower_bound를 하면 1을 반환하게 됩니다.

그러면 그냥 바꿔줍니다. v = {1,2,6} 이렇게요.

 

i = 4일때, lower_bound를 하면 2를 반환합니다.

그냥 바꿔줍니다. v = {1,2,3}

 

i = 5일때 lower_bound를 하면 맨 끝인 4를 반환합니다. (v.end() 위치를 반환하므로)

그러면 추가합니다. v = {1,2,3,4}

 

이렇게 하면 정답에 v.size()를 하면 손쉽게 찾습니다.

일단 코드를 보고나서 이게 왜 맞음?에 대해서 생각해봅시다.

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,t;
    vector<int> v;
    cin >> n;
    
    for(int i = 0; i < n; i++)
    {
        cin >> t;
        auto it = lower_bound(v.begin(),v.end(),t);
        if(it == v.end()) v.push_back(t);
        else v[it-v.begin()] = t;
    }
    cout << v.size();
    return 0;
}

lower_bound를 직접 구현할 수도 있습니다.

vector<int> v;
int lower_bound(int key)
{
    int st = 0, en = v.size()-1;
    while(st <= en){
       int mid = (st + en) / 2;
       if(v[mid] > key)
       {
           en = mid - 1;
       }else if(v[mid] < key)
       {
          st= mid + 1;
       }else{
          return mid;
       }
    }
    return st;

}

 

제가 막상 설명을 하려니까 음 .. 어떻게 말해야 할지 몰라서, 제가 생각한 규칙을 적겠습니다.

 

1. arr[i]가 v에 있는 모든 숫자보다 큰 경우 추가한다. ( 증가 수열이 무조건 되므로)

2. 그 외의경우 (lower_bound의 결과가 v.end()가 아닌경우) 그냥 교체한다.

-> {1,3,6,4} 일때 arr[i]가 4면 v = {1,3,6}에서 lower_bound를 하면 2가 나오므로, v = {1,3,4}로 바꾼다는 뜻입니다.

 

arr = {1,5,6,3} 으로 제가 세운 규칙대로 해보겠습니다.

 

v = {1,3,6} 이 최종적으로 나오게 됩니다.

그러면 v가 LIS는 아니지만, 개수는 맞게 됩니다.

 

이게 왜 되냐면.. 아.. 뭔가 경험적으로 느낀건데

가장 큰 숫자는 나중에 들어올때 항상 맨 뒤로 가기 때문에 전체적인 개수에 영향을 안 줄 것이고, 안에서 변경되는 경우는 숫자가 더 작아지는 경우에만 바뀌기 때문에 ( 1,3,6,이 1,3,4가 되듯) 영향을 안준다고 생각했습니다.

 

그리고 최종 나온 v = {1,3,6}에도 한가지 참인게 있습니다.

v[i]는 v[0]~ v[i-1] 의 원소보다 arr에서 실제로 뒤에있다.

 

arr = {1,5,6,3}을 예시로 봅시다.

만약 arr[2] = 6 까지 진행을 했으면

v = {1,5,6}이 나오게 됩니다.

 

arr[3]을 여기서 집어넣으면 v = {1,3,6}이 나옵니다.

LIS는 만족하지 않지만, v[1] = 3을 예시로 보면

3앞에 있는 원소 1은 실제로 배열이 앞에 있습니다.

 

하;; 이게 저도 속이 터집니다. 나중에 들어와서 v에서 값이 변경되는 원소들은 당연히 lower_bound때문에 크거나 같은 위치만 알려줘서, 자기보다 앞에있는(먼저 들어온) 수보다는 항상 크기 때문입니다. 설명을 잘 못하겠어요.

 

그럼 이제 진짜 LIS는 어떻게 찾을까요?

https://www.acmicpc.net/problem/14003

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

 

이 문제를 해결하기 위해서는 O(nlogn)을 사용하면서 복원을 해야합니다.

 

DP를 이용했을때 복원한게 기억 나시죠?

DP[] = {1,2,2,3,2,4} 이런식의 테이블이 있었는데, 이걸 이용했잖아요?

 

lower_bound에서 저걸 어떻게 찾아낼까 정말 고민을 많이했습니다.

분명 앞에껄 봐야하는거 아닌가? 생각을 했고 -> nlogn에 불가능하다고 판단.

 

여러 방법을 했는데 결국 못풀었습니다.

근데 다익스트라에서 경로복원을 할때 pre[i] = k (i번째 노드는 k번째 노드 다음이다) 이런식으로 했잖아요?

 

실제로 배열이 하나가 더 필요하겠다는 생각은 했는데..

real_LIS[i] = k; // LIS배열에서 i번째 원소는 실제 배열의 k번째에 있다. 는 생각을 가지고 했습니다.

 

이게 뭔소리냐?

예시를 봅시다

 

arr[] = {1,5,6,2,3,4} 입니다.

 

i = 0 일때

LIS[] = 1;

my_LIS[] = 0;

 

i = 1 일때

LIS[] = 1 5;

my_LIS[] = 0 1;

 

 

i = 2 일때

LIS[] = 1 5 6;

my_LIS[] = 0 1 2;

 

 

i = 3 일때

LIS[] = 1 2 6 ;

my_LIS[] = 0 1 2 1;

 

 

i = 4 일때

LIS[] = 1 2 3 ;

my_LIS[] = 0 1 2 1 2;

 

 

i = 5 일때

LIS[] = 1 2 3 4;

my_LIS[] = 0 1 2 1 2 3;

 

이렇게 할 수 있습니다.

이러면 복원할때 3,2,1,0 거꾸로 출력하면 되겠죠?

 

my_LIS가 왜 작동할까? 에 대해서 생각해보면, lower_bound의 특징때문이 아닌가 싶습니다.

 

lower_bound가 특정 k를 반환했을때, 0~ k-1까지는 무조건 나보다 작은수가 있는것이므로, 이미 내가 몇번째 증가하는 수열인지 알게 됩니다.

 

DP에서는 그걸 이분탐색이 아닌 순차탐색처럼 구한것이고요.

 

이해를 못할 수 있습니다. 경험적으로 여러 예시를 접하면서 체화를 했습니다. 저는...

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 1000005
int arr[MAX];
int dp[MAX];
vector<int> v;
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,t;
    int v_idx = 1;
    cin >> n;
    vector<int> ans;
    
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    dp[0] = 0; // dp[idx] = x , arr[idx]는 LIS의 x번째에 위치한다.
    v.push_back(arr[0]);
    for(int i = 1; i < n; i++)
    {
        int it = lower_bound(v.begin(),v.end(),arr[i]) - v.begin();
        if(it == v.size()) v.push_back(arr[i]);
        else{
            v[it] = arr[i];
        }
        dp[i] = it;
    }
    int res = v.size();
    cout << res << "\n";
    for(int i = n-1; i >= 0; i--)
    {
        if(dp[i] == res-1){
            ans.push_back(arr[i]);
            res--;    
        }
    }
    reverse(ans.begin(),ans.end());
    for(auto i : ans){ cout << i << " ";}
    return 0;
}

 

풀이입니다.

 

 

이분탐색 풀이를 통해서

https://www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

 

이것도 해결할 수 있습니다.

upper_bound를 쓰는것이 아니고,

 

1. 숫자가 가장 작으면, 맨 끝 v.end()를 반환한다.

ex) 60 50 30에서 20이 들어오면 3을 반환합니다.

2. 거기 있는 숫자들보다 크거나 같다면 상한숫자를 반환한다.

ex) 60 50 30 에서 70이 들어오면 0을 반환하고, 50이 들어오면 1을 반환합니다.

 

이걸 토대로 직접 만들면 됩니다.

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> v;
int my_bound(int t)
{
    int st = 0;
    int en = v.size()-1;
    int mid;
    // 30 10   20을 넣으면
    while(st <= en)
    {
        mid = (st+en)/2;
        if(v[mid] > t){
            st = mid+1;
        }else if(v[mid] < t){
            en = mid-1;
        }else{
            return mid;
        }
    }
    return st;
}
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,t;
    int v_idx = 1;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> t;
        if(i == 0){
            v.push_back(t);
            continue;
        }
        int idx = my_bound(t);
        if(idx == v.size()) v.push_back(t);
        else v[idx] = t;
    }
    cout << v.size();
    
 
    return 0;
}

 

끝입니다.

 

맨날 구몬학습지 B단계 풀다가, F단계 이런거 푸니까 뭔가 뇌를 쓴다는 생각이 듭니다.

좋습니다^^