최장 증가 부분수열

최장 증가 부분수열_{longest increasing subsequence}(LIS) 문제는 수열 , , , 이 주어졌을 때, ‘강한 증가_{strictly increasing} 부분수열 중 가장 긴 것’을 찾는 것이 목표이다.

좀 더 형식적으로 말하면, 다음 조건을 만족하는 가장 긴 인덱스 수열 을 찾고자 하는 것이다.

DP를 이용한 풀이

동적 계획법을 이용하여 최장 증가 부분수열 문제를 해결해보자. 우선 ‘부분수열의 길이’를 찾는 방법을 설명하고, 이후에 실제 수열을 복원하는 방법을 알아보도록 하자.

길이 구하기

배열 ()을 로 끝나는 가장 긴 증가 부분수열의 길이로 정의하자.

예시

예를 들어, 로 끝나는 가장 긴 수열은 이고 길이는 3이다. 로 끝나는 가장 긴 수열은 또는 이며 길이는 5이다. 의 경우에는 로 길이 2이다.

부터 차례로 계산해 나간 뒤, 의 최댓값이 우리가 구하고자 하는 결과가 될 것이다.

각 에 대해 다음 두 경우로 나눌 수 있다.

부분수열이 만 포함한 경우
보다 앞에 보다 작은 가 존재하고¹, 로 끝나는 수열 뒤에 를 붙인 경우

구현

int lis(vector<int> const& a) {
  int n = a.size();
  vector<int> d(n, 1);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
      if (a[j] < a[i])
        d[i] = max(d[i], d[j] + 1);
    }
  }
  return *max_element(d.begin(), d.end());
}

수열 복원하기

길이뿐만 아니라 수열 자체도 알아내고 싶다면, 선행자 배열 ()를 만들어야 한다. 그러니까 는 로 끝나는 최장 증가 부분수열의 직전 원소의 인덱스가 된다.

이렇게 하면, 가 가장 큰 부터 시작하여 를 따라가며 전체 수열을 복원할 수 있다. 편의상 로 를 초기화하여 부분수열의 끝을 알 수 있도록 하자.

vector<int> lis(vector<int> const& a) {
  int n = a.size();
  vector<int> d(n, 1), p(n, -1);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
      if (a[j] < a[i] && d[i] < d[j] + 1) {
        d[i] = d[j] + 1;
        p[i] = j;
      }
    }
  }

  int ans = 0, pos = 0;
  for (int i = 0; i < n; i++) {
    if (d[i] > ans) {
      ans = d[i];
      pos = i;
    }
  }

  vector<int> subseq;
  while (pos != -1) {
    subseq.push_back(a[pos]);
    pos = p[pos];
  }
  reverse(subseq.begin(), subseq.end());
  return subseq;
}

수열을 복원하는 다른 방법

를 사용하지 않고도 수열을 복원할 수 있다. 가 가장 큰 부터 시작하여 왼쪽으로 가며 이면서 인 를 찾음으로써 가능하다. 메모리를 절약할 수 있지만 코드가 약간 길어진다.

vector<int> lis(vector<int> const& a) {
  int n = a.size();
  vector<int> d(n, 1), p(n, -1);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
      if (a[j] < a[i])
        d[i] = max(d[i], d[j] + 1);

  int ans = 0, pos = 0;
  for (int i = 0; i < n; i++) {
    if (d[i] > ans) {
      ans = d[i];
      pos = i;
    }
  }

  vector<int> subseq;
  for (int i = pos; i >= 0; i--) {
    if (a[i] < a[pos] && d[i] == d[pos] - 1) {
      subseq.push_back(a[pos]);
      pos = i;
    }
  }
  reverse(subseq.begin(), subseq.end());
  return subseq;
}

DP와 이진 탐색을 이용한 풀이

이 문제를 더 빠르게 해결하기 위해 동일하게 만큼 걸리지만 다른 방식으로 접근하는 방식을 소개하고, 이후에 으로 개선하는 방향으로 가도록 하자.

DP 배열 ()를 정의할 것인데, 이번에는 이 어떤 나 의 접미사에 대응되지는 않는다. 은 길이 의 증가 부분수열의 마지막 원소의 최솟값이다.

로, 1 이상의 에 대해서는 로 초기화하자.

부터 차례로 수를 처리하며 배열 를 갱신해보자.

예시

댜음은 배열 에 대해 이의 접미사 배열과 그에 대한 DP 배열 를 나타낸 것이다. 배열 의 원소가 매 단계마다 바뀌는 것은 아님을 알 수 있다.

원소 가 어떤 조건을 만족했을 때 배열 에 를 저장하게 될까? 를 길이가 인 증가 부분수열 뒤에 붙일 수 있을 때 (즉, 일때), 의 방식으로 갱신할 수 있을 것이다. 그러나 이 부분수열의 마지막 원소의 최솟값으로 정의하였으므로 기존 보다 작은지 검사해야 한다. 이렇게 하는 이유는 길이가 인 증가 부분수열에 대해 마지막 원소를 가장 작게 유지하지 않으면, 길이가 인 증가 부분수열을 만들 수 있음에도 최소가 아닌 보다 크지 않아 발견하지 못할 수 있기 때문이다.

끝으로, LIS의 길이는 인 최대의 를 통해 구하면 될 것이다.

int lis(vector<int> const& a) {
  int n = a.size();
  const int INF = 1e9;
  vector<int> d(n+1, INF);
  d[0] = -INF;

  for (int i = 0; i < n; i++)
    for (int l = 0; l < n; l++)
      if (d[l] < a[i])
        d[l+1] = min(d[l+1], a[i]);

  int ans = 0;
  for (int l = 0; l <= n; l++)
    if (d[l] < INF)
      ans = l;
  return ans;
}

여기서 다음과 같은 사실을 알 수 있다.

배열 는 항상 오름차순으로 정렬되어 있다. ()
- 초기 배열 는 오름차순으로 정렬되어 있다.
- 이 에서 로 갱신 될 때, 이므로 의 대소관계는 유지된다.
는 최대 1개의 에만 영향을 준다.
- 수직선에 각 에 점이 찍혀 있다고 할 떄, 는 항상 그 점들 위에 있거나 두 점 사이(, )에 위치할 것이다.
- 전자의 경우 은 변경되지 않고, 후자의 경우 가 된다.

그렇기에 인 최소 을 구하는 것을 이분 탐색으로 대체함으로써 알고리즘을 개선할 수 있다.

int lis(vector<int> const& a) {
  int n = a.size();
  const int INF = 1e9;
  vector<int> d(n+1, INF);
  d[0] = -INF;

  int ans = 0;
  for (int i = 0; i < n; i++) {
    size_t l = lower_bound(d.begin(), d.end(), a[i]) - d.begin();
    d[l] = min(d[l], a[i]);
    ans = max(ans, l);
  }

  return ans;
}

참고 문헌

jakobkogler, et al. Longest increasing subsequence. cp-algorithms.com.

그러니까 이면서 인 가 존재하고, ↩

최장 증가 부분수열

TOC

최장 증가 부분수열

DP를 이용한 풀이

길이 구하기

구현

수열 복원하기

수열을 복원하는 다른 방법

DP와 이진 탐색을 이용한 풀이

참고 문헌

주