최장 증가 부분 수열 LIS(Longest Incresing Sequence)

본론에 들어가기 앞서

작성자는 기존의 LIS를 구하는 법을 알려주던 블로그에서 알려주지 않았던 내용에 대해 한 번 데고 분노하여 직접 LIS에 대해 다루기로 했다.

 

평소였으면 이런 글에는 사족을 달지 않으나 어떤 문제에 대해 큰 충격을 받고 잠을 설쳤기에 블로그에서라도 하소연을 하고 싶었다.

 

어찌 되었든 이 게시글은 읽는 사람이 어느 정도 수준의 DP, lower bound, 세그먼트 트리, 펜윅 트리를 알고 있다고 가정하고 작성하였으며 LIS와 관련된 토픽을 내가 알고 있는 범위에서 방대하게 다룰 것이다.

 

물론 위에서 언급한 것들의 일부를 몰라도 되며, 모르는 것을 사용하는 때가 오면 잠시 건너뛰어도 될 것이다. 하지만 나와 같은 일을 겪으면 매우 억울할 것이니 모르는 토픽은 공부하고 와서 다시 이 글을 읽도록 하자.

LIS의 정의

LIS는 어떤 수열이 존재할 때, 각 원소들 중 선형적으로 순증가 하는 조각들로만 모아 만들어진 가장 긴 수열로 볼 수 있다.

 

보다 쉬운 이해를 위해 다음 수열을 보자.

 

9

2

7

4

6

7

9

8

 

이 수열의 LIS는 다음과 같이 색으로 칠해진 부분이 된다.

 

9

2

7

4

6

7

9

8

 

LIS는 [2, 4, 6, 7, 9]가 되며 그 길이는 5가 된다. 이것 말고도 9 대신 8을 선택한 [2, 4, 6, 7, 8]도 LIS임을 주목하라. 이처럼 LIS는 여러 경우가 존재할 수 있다.

 

문제풀이 분야에서 LIS도 특수한 한 부분을 차지하고 있다고 간주되어 알고리즘 분류에서 LIS가 따로 있는 것을 목격할 수 있다.

 

이처럼 solved.ac 태그에도 가장 긴 증가하는 부분 수열이라는 이름으로 분류되어 있다.

자 이제 이 LIS의 길이를 구하는 법을 알아볼 것이다.

DP로 LIS의 길이 구하기: $O(N^{2})$

1차원 테이블을 다음과 같이 정의한다.

 

dp[i] := i번째 원소까지 살펴봤을 때 LIS의 길이

 

그러면 모든 원소는 1로 초기화를 할 수 있다.

 

i번째 원소를 볼 때 1 ~ i - 1번째 원소까지 살펴보면서(이 index는 j라고 하자) sequence[i] > sequence[j]를 만족할 때 max(dp[i], dp[j] + 1)을 계산하면 $O(N^{2})$의 시간 복잡도로 LIS의 길이를 구할 수 있다.

 

다음은 BOJ 11053을 DP로 해결하는 파이썬 코드이다.

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

N = int(input())
L = input().split()
D = []

for i in range(len(L)):
    L[i] = int(L[i])
    D.append(1)
    
for i in range(len(L)):
    if i == 0:
        continue
    
    for j in range(i):
        if L[i] > L[j] and D[j] >= D[i]:
            D[i] = D[j] + 1
            
print(max(D))

 

이중 반복문을 돌면서 i번째 원소와 j번째 원소의 대소비교를 통해 DP 테이블을 갱신하는 것을 볼 수 있다.

 

N의 제한이 10000 미만일 때 효과적으로 LIS의 길이를 구할 수 있다.

 

다만 DP를 사용해 LIS의 길이를 구하는 것은 처음에 언급한 토픽을 전부 알고 있는 경우에는 쓸 이유가 없어진다.

 

아래 언급할 내용들로 LIS를 구하면 단 $O(N \log N)$ 만에 해결이 가능하기 때문이다. 따라서 DP의 감각을 키운다는 느낌으로만 살펴보고 넘어가도록 하자.

Lower bound로 LIS의 길이 구하기: $O(N \log N)$

이진 탐색을 사용하여 LIS의 길이를 구하는 법을 알아본다.

 

다음과 같은 과정으로 LIS의 길이를 알 수 있는 리스트를 생성한다.

 

1. 어떤 리스트를 하나 생성한다. 이 리스트는 처음에 수열의 첫 번째 값이 들어있다.

 

2. 수열의 두번째부터 순회하면서 다음 두 가지 분기를 처리한다.

 

3-1. 수열의 현재 원소가 리스트의 마지막 원소보다 클 경우 리스트에 현재 원소를 삽입한다.

 

3-2. 그렇지 않을 경우 리스트에서 해당 원소를 기준으로 lower bound를 수행하여 찾아낸 원소랑 교체한다.(이 과정을 통해 리스트의 원소들은 순증가 하므로 이진 탐색을 수행할 수 있다.)

 

4. 이를 반복하면 리스트의 길이는 LIS의 길이가 된다.

 

lower bound로 원소를 교체하는 이유는 LIS에 포함된 원소들 중 가능한 한 작은 원소만 남겨서 LIS에 포함될 수 있는 원소의 하한을 낮추기 위함이다.

 

위에서 처음 언급한 수열에서 LIS의 길이를 lower bound로 구해보자.

처음에는 9가 들어있다.

2를 봤을 때 lower bound로 찾아낸 9보다 작으므로 9와 교체한다.

7을 봤을 때 LIS의 마지막 원소인 2보다 크므로 7을 리스트에 삽입한다.

4를 봤을 때 lower bound로 찾아낸 7과 교체한다.

6은 4보다 크므로 리스트에 삽입한다.

7은 6보다 크므로 리스트에 삽입한다.

9는 7보다 크므로 리스트에 삽입한다.

8을 봤을 때 lower bound로 찾아낸 9와 교체한다.

 

모든 원소를 다 살펴봤을 때 리스트의 길이는 5로 LIS의 길이가 된다.

 

이 방법은 C++에서 std::lower_bound를 사용해 매우 간단하게 구현할 수 있다.

 

시간 복잡도는 수열의 길이를 N이라 했을 때 이진 탐색을 N번 수행하므로 $O(N \log N)$이 된다.

 

DP를 사용하는 방법과 비교하여 시간 복잡도의 큰 개선을 이루어냈다.

 

다만 이 방법은 그림에서도 알 수 있듯이 이진 탐색 과정에서 원소들의 index가 뒤섞이기 때문에 생성된 리스트는 LIS가 아님을 유의하도록 한다.

 

다음은 BOJ 12015를 lower bound로 해결하는 C++ 코드이다.

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    vector<int> table(n), res;
    
    for (int i = 0; i < n; ++i)
    {
        cin >> table[i];

        if (res.empty() || res.back() < table[i])
            res.push_back(table[i]);
        else
            *lower_bound(res.begin(), res.end(), table[i]) = table[i];
    }
    
    cout << res.size();
}

LIS 응용: 전깃줄

지금부터 LIS를 응용하는 문제를 풀면서 나를 분노케 한 토픽으로 이어가도록 하겠다. 사실 지금까지 알아본 LIS의 길이를 구하는 구현에서 중요한 내용이 빠져있고 그것을 이야기할 것이다.

 

https://www.acmicpc.net/problem/2565

2565번: 전깃줄

KOI에 나왔던 문제다. "이게 왜 LIS?"라는 생각이 들 수 있지만 전봇대에 연결된 숫자 쌍에서 한 쪽을 기준으로 오름차순 나열하면 놀라운 발견을 할 수 있다.

 

그림에서 왼쪽을 기준으로 오름차순하여 나열해보자.

 

1 2 3 4 6 7 9 10

8 2 9 1 4 6 7 10

 

뭔가 찾았는가? 아래에서 나타난 수열에 대해 LIS의 길이가 5 임을 확인할 수 있다.

 

반대로 LIS에 속하지 않은 원소를 살펴보면 다음을 발견할 수 있다.

 

전깃줄을 LIS에 속한 원소와 속하지 않은 원소로 나누어 생각하면 LIS에 속하지 않은 원소가 연결된 전깃줄은 LIS에 속한 원소가 연결된 전깃줄과 무조건 교차한다.

 

그렇다! 이 문제는 연결된 전깃줄 페어를 한쪽을 기준으로 정렬한 후 반대쪽의 원소들에 대해 순회하면서 전체 수열의 길이 - LIS의 길이를 계산하기만 하면 되는 문제로 바뀐 것이다.

 

이 발견을 하게 되었으면 아주 간단하게 LIS의 길이를 찾아 문제를 해결할 수 있다.

 

이를 뒤집어서 생각하면 교차하지 않는 전깃줄의 최대 크기는 바로 LIS의 길이가 되는 것이다.

 

이렇게 건너편과 연결한 상황이 문제로 나오는 경우는 Inversion Counting과 같이 LIS의 대표 유형이니 반드시 숙지하는게 좋다. Inversion counting에서는 몇 개가 교차하는지를 구하는 문제로 나오게 된다.

 

다만 이 문제는 어떤 조건이 상식적으로는 당연하게도 걸려있다. 그리고 그 조건이 사라지면 작성자를 절망으로 빠트렸던 문제로 바뀐다.

 

어떤 조건을 뺄 수 있을까?

LIS 응용: 전깃줄과 비슷한데...

이 내용은 다른 곳에서는 거의 볼 수 없는 내용이다! 주의깊게 볼 것을 강력히 권한다!

 

우리는 다음 문제를 생각해볼 것이다. 지금부터 언급할 지문이 KOI 전깃줄의 지문과 비교하여 어떤 차이가 있는지 살펴보자.

 

1부터 N까지 번호가 붙은 노드가 2개씩 N쌍이 다음과 같이 배치되어 있다고 생각해보자.

1 2 3 ... N
1 2 3 ... N

여기서 같은 번호의 노드를 (i, 0) (i, 1)로 구분할 수 있다.

이때 M개의 간선이 노드 x, y에 대해 (x, 0), (y, 1)을 서로 연결한다.

이때 교차하지 않는 간선의 최대 개수를 구하라. 단, 같은 노드에 여러 개의 간선이 연결된 것도 교차한 것으로 간주한다.

 

둘을 비교해보면 차이를 어렵지 않게 발견할 수 있다.

 

같은 위치에 두 개 이상의 간선이 연결될 수 없다는 조건이 없으며, 그에 따라 같은 노드에 연결된 간선들은 서로 교차한 것으로 간주한다는 조건이 새로 생기게 되었다.

 

즉, 어떤 쪽을 기준으로 하든 2번 이상 출현하는 노드가 생긴다는 의미다.

 

"그냥 전깃줄 풀듯이 하면 안되나요?" 라는 물음이 충분히 생길 수 있다. 그리고 그렇게 통수를 당했다.

 

다음 경우를 보자.

 

 

이런 경우에서 무작정 LIS의 길이를 구하면 5라는 결과가 나온다. 하지만 위 지문에서는 같은 노드에 연결한 것도 교차한 것으로 간주한다고 했으니 답은 4가 되어야 한다.

 

이를 나열하면

 

1 1 2 3 4

1 2 3 4 5

 

이렇게 되는데 1 2 3 4 5에서 1 또는 2를 빼야 되는 방법을 찾아야 한다.

 

이를 해결하기 위한 방법을 lower bound 기준으로 설명하도록 하겠다.

 

정렬할 때 다음 기준으로 정렬하도록 한다.

 

정렬 기준으로 삼은 쪽에서 같은 원소를 만날 경우 반대편 원소를 서로 비교하여 큰 것이 먼저 오도록 정렬한다.

 

위 기준을 적용하면 앞서 말한 예시는 다음과 같이 배열된다.

 

1 1 2 3 4

2 1 3 4 5

아! 누가 봐도 문제 조건을 충족하도록 정렬되었음을 파악할 수 있다!

 

이대로 LIS의 길이를 구하기만 하면 된다.

 

이렇게 정렬 함수를 수정하여 중복 노드에 대해 효과적으로 처리할 수 있게 된다.

 

https://atcoder.jp/contests/arc126/tasks/arc126_b

B - Cross-free Matching

 

이게 작성자를 잠 못 이루게 한 그 문제다. 내용도 앞서 이야기한 지문과 동일하다.

 

여러분은 이런 상황에 대해 대처할 수 있게 되었으니 본인처럼 분에 잠을 설치는 참사 없이 스무스하게 문제를 해결하도록 하자.

LIS 최적해 역추적

https://www.acmicpc.net/problem/2568

2568번: 전깃줄 - 2

그렇다. 전깃줄 2는 전깃줄 1과 달리 실제 해도 출력해야 한다!

 

하지만 N의 상한이 10만이라서 필시 lower bound를 사용해야 할 것인데 앞에도 이야기했듯이 이진 탐색을 이용한 LIS는 실제 LIS를 찾을 수 없다는 문제가 존재한다.

 

어떻게 해결해야 할까?

 

우리는 LIS의 실제 해를 찾기 위해 LIS 알고리즘을 수행하는 과정 중 배정된 index를 해당 원소와 페어로 묶어 스택에 push 할 것이다.

 

이렇게 되면 알아낸 LIS의 길이가 x이고 스택의 top부터 살펴봤을 때 x -> x - 1 -> x - 2 -> .. -> 1 이런 식으로 LIS의 뒤부터 처음까지 역추적을 하여 실제 LIS가 될 수 있는 수열을 복원할 수 있게 된다.

 

이때 우리가 원하는 것은 LIS가 될 수 없는 원소들이므로 LIS에 해당하는 원소를 map이나 배열에 표시를 해뒀다가 수열을 출력하면서 LIS에 해당하는 원소만 빼고 출력하면 된다. A 전봇대를 기준으로 출력한다는 점을 유의하자.

 

자세한 구현은 다음 소스를 참고하라.

http://boj.kr/bd38a6aa0d6c4420988ec0ce812657ad

세그먼트 트리로 LIS 길이 구하기: $O(N \log N)$

이번엔 DP를 세그먼트 트리로 최적화 하여 $O(N \log N)$으로 LIS의 길이를 구해보도록 하자.

 

세그먼트 트리로 각 구간에 대해 LIS의 길이를 저장할 것이다.

 

그러면 최댓값 연산을 통해 i번째 원소에 대해 [1, i - 1] 구간의 LIS 길이를 $O(N \log N)$으로 구할 수 있고 이렇게 구한 구간 최댓값 m에 1을 더한 m + 1을 구간 [1, i]에 대해 최댓값을 갱신할 수 있게 된다.

 

다만 이를 실천에 옮기기 위해선 주어진 수열에 전처리가 필요하다.

 

앞서 말한 연산을 하기 위해서는 수열을 오름차순으로 정렬할 필요가 있다.

 

작은 수가 있는 구간에서 큰 수가 있는 구간으로 값 +1을 해서 전이를 시키기 때문이다.

 

"전이를 한다니? 이게 무슨 소리야?" 침착하고 이 문제의 예시에 대해 스텝을 밟아보자.

 

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

 

테스트 케이스로 주어진 수열은 다음과 같다.

 

10 20 10 30 20 50

 

이에 대해 index도 같이 매기면(1-based)

10	20	10	30	20	50
1	2	3	4	5	6

 

이 수열을 한번 정렬해보자. 이때 정렬 기준은 위에서 언급한 중복 원소가 존재하는 경우에 맞춰서 큰 index가 앞으로 오게 해야 한다는 것을 유의하라.

10	10	20	20	30	50
3	1	5	2	4	6

 

처음 10부터 보자. 이때 index가 3인 10이 속하지 않은 구간 [1, 2]에는 아무것도 없으므로 LIS의 길이도 당연히 0이다.

 

따라서 이렇게 얻어낸 LIS의 길이 0에 1을 더한 값 1을 세그먼트 트리로 구간 [1, 3]에 갱신해준다.

 

이렇게 되면 구간 [1, 3]의 LIS의 길이는 1이 된다.

 

다음 10을 보자. index가 2인 10이 속하지 않은 구간 구간 [1, 1]에도 역시 아무것도 없다. 구간 [1, 1]에서 LIS의 길이는 0이므로 여기에 1을 더한 값 1을 구간 [1, 2]에 갱신해준다.

 

이렇게 되면 10이 속해있는 구간 [1, 3]의 LIS 길이는 1이 된다. 만약 index 순서조차 오름차순으로 배치했으면 구간 [1, 3]에서 LIS의 길이가 2가 되는 참사가 일어났을 것이다.

 

다음 20을 보자.

 

이때 구간 [1, 4]의 LIS 길이는 1이 된다. 이를 구간 [1, 5]에 반영하여 구간 [1, 5]에서 LIS의 길이는 2가 된다.

 

그다음 20도 마찬가지로 반영하여 구간 [1, 2]의 LIS 길이를 2로 만들 수 있다.

 

이런 식으로 작은 수에서 큰 수로 쌓아가면 마침내 전체 구간의 LIS 길이를 생성할 수 있는 것이다.

 

12015 문제를 세그먼트 트리로 푸는 코드는 아래를 참조하라.

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/rope>

using namespace std;
using namespace __gnu_cxx;
using ll = long long;
using pii = pair<int, int>;

int n;
pii ar[1000001];

inline int mid(int s, int e) { return s + (e - s) / 2; }

int query(vector<int> &tree, int node, int start, int end, int l, int r)
{
  if (end < l || start > r) return 0;
  if (l <= start && end <= r) return tree[node];
  int m = mid(start, end);
  return max(
    query(tree, node * 2, start, m, l, r),
    query(tree, node * 2 + 1, m + 1, end, l, r)
  );
}

int update(vector<int> &tree, int node, int start, int end, int idx, int val)
{
  if (idx < start || idx > end) return 0;
  if (start == end) return tree[node] = max(tree[node], val);
  int m = mid(start, end);
  int cmp = max(
    update(tree, node * 2, start, m, idx, val),
    update(tree, node * 2 + 1, m + 1, end, idx, val)
  );
  return tree[node] = max(cmp, tree[node]);
}

void solve()
{
  cin >> n;
  for (int i = 1; i <= n; ++i)
  {
    cin >> ar[i - 1].first;
    ar[i - 1].second = i;
  }

  sort(ar, ar + n, [](pii &l, pii &r) {
    if (l.first != r.first) return l.first < r.first;
    return l.second > r.second;
  });

  vector<int> segtree(n * 4);

  for (int i = 0; i < n; ++i)
  {
    int idx = ar[i].second;
    int maxval = 0;
    if (idx != 1)
      maxval = query(segtree, 1, 1, n, 1, idx - 1);
    
    update(segtree, 1, 1, n, idx, maxval + 1);
  }

  cout << segtree[1];
}

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

  solve();
}

 

다만 LIS 문제를 세그먼트 트리로 푸는 것은 별로 추천하지 않는데 이진 탐색 구현법에 비해 속도가 상당히 느리기 때문이다.

 

 

위가 std::lower_bound, 아래가 세그먼트 트리 구현이다. 같은 시간 복잡도임에도 불구하고 코드 길이와 실행 시간 사이좋게 4배가량 차이가 나는 것을 볼 수 있다.

 

LIS를 세그먼트 트리로 풀어보는 의의는 LIS를 구하기 위한 용도보다는 세그먼트 트리로 이런 전이를 수행할 수 있다는 시각을 얻기 위해서다.

 

세그먼트 트리를 사용할 수 있는 문제를 보다보면 생각지도 못한 방법으로 구간 쿼리를 수행하는 경우가 나오는데 LIS는 이런 문제 풀이 시각을 넓히는데 도움이 된다.

 

지금까지 LIS에 대해 알아보고 LIS의 길이를 구하는 방법 2가지, 노드에 중복이 생겼을 때 대응하는 방법, LIS의 최적해 역추적과 세그먼트 트리로 LIS의 길이를 구하는 방법을 알아보았다.

 

LIS는 생각보다 깊게 배워야 하는 토픽이기에 LIS를 공부하는 여러분이 이 블로그 게시글에서 좋은 공부를 하고 갔으면 좋겠다.