최장 증가 부분 수열 - LIS(Longest Increasing Subsequences)

개요

주어진 수열에서 최장 증가 부분 수열(이하 LIS)를 구하는 방법을 알아보자.

어떠한 수열이 주어졌을 때, 일부를 뽑아 새로 만든 수열을 “부분 수열”이라고 한다.
이 수열이 오름차순을 유지하면 “증가 부분 수열”이다.
우리는 증가 부분 수열 중에서 가장 긴 증가 부분 수열(LIS)를 찾고자 한다.

LIS를 구하는 문제 유형은 네가지가 존재한다.

1. 동적 계획법(Dynamic Programming)을 이용한 O(N^2) 알고리즘

2. 동적 계획법을 이용하고 실제 LIS까지 구하는 알고리즘

3. 이분 탐색(Binary Search)를 이용한 O(NlogN) 알고리즘

4. 이분 탐색을 이용하고 실제 LIS까지 구하는 알고리즘

여기서 1, 3번은 LIS의 길이만 구할 수 있고, 실제 LIS는 구하지 못한다.

1번 - 동적 계획법(Dynamic Programming)을 이용한 O(N^2) 알고리즘

가장 간단하게 LIS를 구하는 방법은 DP를 이용하는 것이다.
수열과 길이가 똑같은 dp배열을 생성한다. dp배열에 들어가는 값 dp[i]는 수열의 i번째 원소가 끝에 존재하는 LIS의 길이이다. 수열의 모든 원소를 반복문으로 돌며 (현재위치를 i라하고 j를 i 앞의 수라 하면) Arr[j] < Arr[i] 를 만족하는 j중에 dp[j]가 가장 큰 j에 1을 더하면 dp[i] 이다. 말로 설명하는 것보다 코드를 보면 바로 이해할 수 있다.

문제 : 백준 11053번 - 가장 긴 증가하는 부분 수열

#include <iostream>

using namespace std;

int N, ans;
int Arr[1010];
int dp[1010];

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

  cin >> N;
  for (int i = 0; i < N; i++) cin >> Arr[i];

  for (int i = 0; i < N; i++) {
    dp[i] = 1;
    for (int j = 0; j < i; j++) {
      if (Arr[j] < Arr[i]) dp[i] = max(dp[i], dp[j] + 1); 
    }
    ans = max(ans, dp[i]);
  }

  cout << ans << "\n";

  return 0;
}

반복문을 진행하면서 dp배열의 최대값을 기억하면 LIS의 길이를 구할 수 있다.
수열의 모든 원소에 대해 확인하므로 O(N)이 걸리고, 각각 자신의 앞에 존재하는 모든 수들의 dp[j]값을 확인해야 하므로 O(N)이 걸려 최종 O(N^2)의 시간복잡도를 갖는다.

2번 - 동적 계획법을 이용하고 실제 LIS까지 구하는 알고리즘

다만 1번의 방법으로는 LIS의 길이만 구할 수 있고, LIS가 어떤 수들로 이루어져 있는지는 알 수 없다. LIS가 어떤 수들로 이루어져 있는지를 알기 위해서는 추가적인 배열이 필요하다. 먼저 코드를 보자.

문제 : 백준 14002번 - 가장 긴 증가하는 부분 수열 4

#include <iostream>
#include <vector>

using namespace std;

int N, maxIndex;
int Arr[1010];
int dp[1010];
int trace[1010];
vector<int> ans;

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

  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> Arr[i];
    trace[i] = -1;
  }

  for (int i = 0; i < N; i++) {
    dp[i] = 1;
    for (int j = 0; j < i; j++) {
      if (Arr[j] < Arr[i]) {
        if (dp[i] < dp[j] + 1) {
          dp[i] = dp[j] + 1;
          trace[i] = j; 
        }
      }
      if (dp[maxIndex] < dp[i]) maxIndex = i;
    }
  }

  while (maxIndex != -1) {
    ans.push_back(Arr[maxIndex]);
    maxIndex = trace[maxIndex];
  }

  cout << ans.size() << "\n";
  for (int i = ans.size() - 1; i >= 0; i--) cout << ans[i] << " ";
  cout << "\n";

  return 0;
}

trace배열을 추가적으로 만든 것을 볼 수 있다. trace배열에 들어가는 값은 해당 원소가 붙은 원소의 위치이다. 만약 Arr[j] < Arr[i] 를 만족하면 dp[j] + 1과 dp[i]를 비교해 dp[j] + 1이 더 크다면 Arr[j]가 마지막 원소로 존재하는 LIS뒤에 Arr[i]를 붙히게 되므로 trace[i]의 값은 j 가 된다.
이렇게 trace배열을 채우고 거꾸로 찾아가며 출력하면 LIS가 어떤 원소들로 이루어져 있는지 확인할 수 있다.
주의할 점은 수열의 0번째 수를 가리킬 수도 있으므로 trace배열을 0이아닌 -1과 같은 값들로 미리 초기화를 해놓아야 한다는 것이다.

3번 - 이분 탐색(Binary Search)를 이용한 O(NlogN) 알고리즘

1, 2번의 dp를 이용한 방법은 O(N^2)의 시간복잡도로 시간이 오래걸린다는 단점이 있다. 이것은 자신 앞에 존재하는 모든 dp[j]값을 확인해야한다는 것으로부터 비롯되는데, 이를 해결한 방법이 이분탐색을 활용한 방법이다.
이 방법의 핵심은, LIS를 만들어 나갈 때 LIS의 마지막 원소가 가능한 작을수록 더 긴 LIS를 생성 할 수 있다는 것이다.
만약 현재 원소가 지금까지 만들어진 LIS의 마지막 원소보다 작으면 이분탐색을 통해 LIS에 현재 원소가 들어갈 위치를 찾아 삽입한다. LIS는 오름차순이므로 이분탐색을 활용할 수 있고, O(logN)의 시간이 걸리므로 최종 알고리즘의 시간복잡도를 O(NlogN)으로 줄일 수 있다.

문제 : 백준 12015번 - 가장 긴 증가하는 부분 수열 2

#include <iostream>

using namespace std;

int N;
int Arr[1'000'010];
int LIS[1'000'010];

int binarySearch(int size, int target) {
  int l = 0;
  int r = size - 1;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (LIS[mid] == target)
      return mid;
    else if (LIS[mid] > target)
      r = mid - 1;
    else
      l = mid + 1;
  }
  return l;
}

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

  cin >> N;
  for (int i = 0; i < N; i++) cin >> Arr[i];

  LIS[0] = Arr[0];
  int size = 1;
  for (int i = 1; i < N; i++) {
    if (Arr[i] > LIS[size - 1]) {
      LIS[size] = Arr[i];
      size++;
    } else {
      int index = binarySearch(size, Arr[i]);
      LIS[index] = Arr[i];
    }
  }

  cout << size << "\n";

  return 0;
}

포인트는 LIS[0]에 Arr[0]의 값을 먼저 넣어 놓고 시작하는 것과 size변수(현재 LIS의 길이)를 통해 LIS에 접근하는 것이다. 뒤에 붙일 때(Arr[i]가 현재 LIS의 마지막 원소보다 클 때)는 size가 증가하지만 뒤에 붙이는 것이 아닌 이분탐색을 통해 위치를 찾아 삽입한 경우에는 size가 증가하지 않는다.
모든 원소에 대해 확인하므로 O(N)의 시간이 걸리고, 이분탐색을 통해 위치를 찾으므로 O(logN)의 시간이 걸려 최종 O(NlogN)의 시간복잡도를 갖는다.

4번 - 이분 탐색을 이용하고 실제 LIS까지 구하는 알고리즘

3번에서 구한 LIS 배열에 들어가는 값들을 출력해보면 순서가 뒤죽박죽인 것을 확인할 수 있을 것이다. 따라서 3번 방법으로는 LIS의 길이만 구할 수 있을 뿐 LIS의 구성 원소들까지는 알 수 없다. 이를 해결하기 위해서는 추가 배열이 필요하다. 코드를 보자.

문제 : 백준 14003번 - 가장 긴 증가하는 부분 수열 5

#include <iostream>
#include <vector>

using namespace std;

int N;
int Arr[1'000'000];
int LIS[1'000'000];
int trace[1'000'000];
vector<int> ans;

int binarySearch(int size, int target) {
  int l = 0;
  int r = size - 1;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (LIS[mid] == target)
      return mid;
    else if (LIS[mid] > target)
      r = mid - 1;
    else
      l = mid + 1;
  }
  return l;
}

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

  cin >> N;
  for (int i = 0; i < N; i++) cin >> Arr[i];

  LIS[0] = Arr[0];
  int size = 1;
  for (int i = 1; i < N; i++) {
    if (LIS[size - 1] < Arr[i]) {
      LIS[size] = Arr[i];
      trace[i] = size;
      size++;
    } else {
      int index = binarySearch(size, Arr[i]);
      LIS[index] = Arr[i];
      trace[i] = index;
    }
  }

  for (int i = N - 1; i >= 0; i--) {
    if (trace[i] == size - 1) {
      ans.push_back(Arr[i]);
      size--;
    }
  }

  cout << ans.size() << "\n";
  for (int i = ans.size() - 1; i >= 0; i--) cout << ans[i] << " ";
  cout << "\n";

  return 0;
}

2번 알고리즘에서 봤던 trace와는 조금 다른 점이 있는데, 이번에는 내 앞의 원소의 위치를 저장하는 것이 아니라 내가 삽입된 위치를 저장한다.
알고리즘이 끝나고 trace의 배열의 뒤에서부터 size - 1 과 같은 값을 size를 줄여가며 벡터에 넣고 해당 벡터를 뒤에서부터 출력하면 LIS의 구성 원소를 확인할 수 있다.
만약 trace에 [1, 2, 2, 1, 3, 1, 4] 가 존재했다고 하면 뒤에서 부터 4, 3, 2, 1에 해당하는 값을 읽어온다고 생각하면 쉽다.