가장 긴 증가하는 부분 수열(Longest Increasing Subsequence)

• 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수를 제거하여 부분 수열을 만들 수 있다. 이때 만들어진 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 가장 긴 증가하는 부분 수열(LIS)라고 한다.

\( O(N^2) \) 알고리즘

• 배열의 i번째 값으로 끝나는 가장 긴 증가하는 부분 수열의 길이를 dp[i]에 저장한다.
• dp[i] 값을 계산하기 위해 dp[0] ~ dp[i-1] 값을 모두 확인해야 하므로 \( O(N^2) \)의 시간 복잡도를 가진다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)

using namespace std;

int main(void) {
    fastio;

    int N;
    cin >> N;
    int arr[N], dp[N];
    int ans = 1;
    for(int i=0;i<N;i++) {
        cin >> arr[i];
        dp[i] = 1;
    }

    for(int i=1;i<N;i++) {
        for(int j=0;j<i;j++) {
            if (arr[i]>arr[j]) {
                dp[i] = max(dp[i], dp[j]+1); // dp[i] = A[i]보다 작은 A[j] (0<=j<i) 중 가장 큰 dp[j] 값 + 1
                if (ans<dp[i]) ans=dp[i];
            }
        }
    }
    cout << ans;
}

\( O(N\log N) \) 알고리즘

• \( O(N^2) \) 알고리즘에서 dp[i]를 갱신하는 데 필요한 시간 복잡도가 \( O(N) \)인데, 이진 탐색을 활용하여 이를 \( O(\log N) \)으로 줄인다.
• 기존 방식에서 dp 배열은 오름차순이 아니므로 이진 탐색을 사용할 수 없지만, dp 배열의 정의를 길이가 i인 증가하는 부분 수열 중 끝값의 최소값으로 정의하면 오름차순이 되어 이진 탐색을 활용할 수 있다.
  • 동일한 길이의 증가하는 부분 수열의 경우 끝점의 값이 더 작은 경우가 유리하기 때문이다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)

using namespace std;

int main(void) {
    fastio;

    int N;
    cin >> N;
    int arr[N+1]={0,}, dp[N+1]={0,};
    int idx = 1;
    for(int i=1;i<=N;i++) {
        cin >> arr[i];
        int result = lower_bound(dp, dp+idx, arr[i])-dp;
        if (result==idx) {
            dp[idx++] = arr[i];
        }
        else {
            dp[result] = min(dp[result], arr[i]);
        }
    }
    cout << idx-1;
}