자꾸 까먹는 LIS 한번 정리해보기

LIS

Longest Increase Sequence 의 약자. 최장 증가 수열 로도 불린다.

아래와 같은 수열이 있다고 하자.

이 경우, 가장 길게 증가하는 sequence는 2 -> 3 -> 4 -> 7이며, 길이는 4가 된다. LIS는 이러한 가장 긴 경우를 찾는 알고리즘이라고 할 수 있다.

이를 풀이하는 방법을 찾아보자.

DP Solution

DP[j]를 j번째에서의 LIS라고 정의하면, DP의 일반항을 아래와 같이 세울 수 있다. 아래에서 i번째는 i < j인 조건에서 확인이 되어야 한다.

if (A[i] < A[j])
    DP[j] = max(DP[j], DP[i] + 1);

여기서 j는 i보다 커야 한다. (증가하는 순서이므로) 루프를 포함한 전체 코드는 아래와 같다.

DP[0] = 1; // 첫번째 원소는 무조건 1의 LIS를 가진다.
for(int j = 1; j < sz; ++j) { // j번째를 채울 때, [0, j)까지 확인해서 max 값을 사용한다.
    for(int i = 0; i < j; ++i) { // i < j
        if (A[i] < A[j]) 
            DP[j] = max(DP[j], DP[i] + 1);
    }
}

여기서 LIS 결과값은 DP[] 의 최대값 + 1이다. 그리고, 시간복잡도는 O(n^2)가 될 것이다.

Binary Search Solution

살짝 Tricky한 방식이다. 위에서 2중 포문을 도는 이유가 무엇인가? 그것은 DP 배열의 업데이트 순서가 중요하기 때문이다. 만약 경우의 수를 세는 방식에서 벗어나서, A[i] < A[j]인 조건을 직접적으로 DP 배열에 저장할 수 있다면? 그 경우에는 최종적으로 DP 배열의 사이즈가 답이 될 것이다.

구체적인 구현 방식은 Binary Search를 사용한다. 각 원소에 대해서 Binary Search를 수행하면서 DP 배열에 넣으면 되고, 이 경우 전체 배열을 1회만 scan 하면 된다. 따라서 시간복잡도는 O(n log n)이 된다. 이정도 시간복잡도는 O(n^2)에 비해 상당히 합리적이라고 할 수 있다.

vector<int> DP;
for(int i = 0; i < sz; ++i) {
    auto it = lower_bound(DP.begin(), DP.end(), A[i]);
    if (it == DP.end()) {
        DP.push_back(A[i]);
    } else {
        *it = A[i];
    }
}

여기서 LIS 결과값은 DP 배열의 size가 된다. 이렇게 DP의 관점을 바꾸는 것만으로 시간복잡도가 크게 개선될 수 있다.

만약 이 방법에서 실제 LIS를 이루는 배열을 알아야 한다고 한다면, push_back 되는 시점의 원소들로 구성하면 된다. 그러나 모든 경우를 구하는 것은 아니다.