---
id: "imported/ps/algorithm/dp/lis"
title: "LIS"
description: "자꾸 까먹는 LIS 한번 정리해보기"
kind: "record"
published: "2023-05-23T00:00:00.000Z"
tags: ["LIS","DP","binary search"]
url: "https://www.readiz.com/notes/algorithm/dp/lis/"
markdownUrl: "https://www.readiz.com/notes/algorithm/dp/lis/index.md"
---

# LIS

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

## LIS

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

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

| index     |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
| :-------- | :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| **value** |  2  |  3  |  1  |  4  |  7  |  5  |  3  |

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

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

## DP Solution

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

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

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

```cpp
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)`에 비해 상당히 합리적이라고 할 수 있다.

```cpp
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` 되는 시점의 원소들로 구성하면 된다. 그러나 모든 경우를 구하는 것은 아니다.