LIS (Longest Increasing Subsequence)

💡 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)란?

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다.

예를 들어, [ 6, 2, 5, 1, 7, 4, 8, 3] 이라는 배열이 있을 경우, LIS는 [ 2, 5, 7, 8 ] 이 된다.

아래 두 문제를 통해 LIS를 구현하는 방법에 대해 알아보자.

💡 가장 긴 증가하는 부분 수열 2

💻 코드

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

int N, arr[1000004], temp[1000004];
vector<int> v;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    // 배열 입력
    cin >> N;
    for(int i = 0; i < N; i++) cin >> arr[i];
    
    // LIS 생성을 위한 기록
    for(int i = 0; i < N; i++){
        int lowerIdx = (int)(lower_bound(v.begin(), v.end(), arr[i]) - v.begin());
        if(v.size() == lowerIdx) v.push_back(arr[i]);
        else v[lowerIdx] = arr[i];
    }
    
    // LIS 길이 출력 
    cout << v.size() << "\n";
    
    return 0;
}

📖 해설

작성 예정..

⏱ 시간복잡도

$O(Nlog_2N)$

💡 가장 긴 증가하는 부분 수열 5

💻 코드

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

int N, arr[1000004], temp[1000004];
vector<int> v;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    // 배열 입력
    cin >> N;
    for(int i = 0; i < N; i++) cin >> arr[i];
    
    // LIS 생성을 위한 기록
    for(int i = 0; i < N; i++){
        int lowerIdx = (int)(lower_bound(v.begin(), v.end(), arr[i]) - v.begin());
        if(v.size() == lowerIdx) v.push_back(arr[i]);
        else v[lowerIdx] = arr[i];
        temp[i] = lowerIdx;
    }
    
    // LIS 길이 출력
    cout << v.size() << "\n"; 
    
    // LIS 생성
    int len = v.size() - 1; stack<int> stk;
    for(int i = N - 1; i >= 0; i--){
        if(temp[i] == len){
            stk.push(arr[i]);
            len--;
        }
    }
    
    // LIS 출력
    while(!stk.empty()){ cout << stk.top() << " "; stk.pop(); }
    
    return 0;
}

📖 해설

작성 예정..

⏱ 시간복잡도

$O(Nlog_2N)$

참고자료..