LIS(Longest Increasing Subsequence, 최장 증가 수열)

[devLupin]

백준 DP문제의 해설을 보다가 우연히 LIS의 존재를 알게 되었다.

• 아래 코드가 LIS의 핵심

if (arr[j] < arr[i] && dp[i] < dp[j] + 1)

• 전체 코드

#include <iostream>
using namespace std;

const int sz = 1003;
int arr[sz], dp[sz];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;

    fill_n(arr, sz, 0);
    fill_n(dp, sz, 0);

    for (int i = 1; i <= n; i++)
        cin >> arr[i];

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        for (int j = 1; j < i; j++) {
            if (arr[j] < arr[i] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
        ans = (ans > dp[i]) ? ans : dp[i];
    }

    cout << ans;
    return 0;
}

[devLupin]

[회고]

이전에 풀었던 문제들은 갱신된 DP값 + 현재 위치의 arr 가중치를 더하는 방식의 문제 였는데, 갱신된 DP값에 1만 더하는 문제는 나에게 새로웠음.

[devLupin]

• NlgN 시간에 탐색 가능한 LIS

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

const int SZ = 1000000;
int N;
vector<int> A, LIS;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    A.assign(N, 0);
    for (int i = 0; i < N; i++) cin >> A[i];

    LIS.push_back(A[0]);
    for (int i = 1; i < N; i++) {
        if (LIS.back() < A[i]) LIS.push_back(A[i]);
        else {
            int idx = lower_bound(LIS.begin(), LIS.end(), A[i]) - LIS.begin();
            LIS[idx] = A[i];
        }
    }

    for (int x : LIS) cout << x << ' ';

    return 0;
}