LIS 알고리즘이란?

❗ LIS(Longest Increasing Subsequence)는 불연속 상관없이 가장 길이가 긴 증가하는 부분 수열입니다.

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 합니다.

• 예를 들어, {6, 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 경우, LIS는 {2, 5, 7, 8}이 됩니다.
• {2, 5}, {2, 7}등 증가하는 수열은 많지만 그 중에서 가장 긴 것이 {2, 5, 7, 8}입니다.

풀이 방법

LIS를 구하는데 사용할 수 있는 방법에는 두가지가 있습니다.

• DP(Dynamic Programming)
• Binary Search

DP

일반적으로 최장 증가 부분 수열의 길이가 얼마인지 푸는 간편한 방법이 바로 DP를 이용하는 것입니다.

아래에서 length[i]는 i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이를 의미합니다.

for (int k = 0; k < n; k++){
	length[k] = 1;
    for (int i = 0; i < k; i++){
        if(arr[i] < arr[k]){
            length[k] = max(length[k], length[i] + 1);
        }
    }
}

주어진 배열에서 인덱스를 한 칸씩(k+= 1) 늘려가면서 확인합니다. 그리고 내부 반복문으로 k보다 작은 인덱스들을 하나씩 살펴 보면서 arr[i] < arr[k]인 것이 있을 경우, length[k]를 업데이트합니다.

업데이트 하는 기준은 다음과 같습니다.

• i번째 인덱스에서 끝나는 최장 증가 부분 수열의 마지막에 arr[k]를 추가했을 때의 길이와
• 추가하지 않고 기존의 length[k] 값
• 둘 중에 더 큰 값으로 length[k] 값을 업데이트합니다.

당연하겠지만, 마지막 요소의 크기가 제일 크다는 보장은 없습니다.

즉, length[]: [0, N-1]요소 중에서 length[N-1]이 제일 크다는 것이 아니기 때문에 반복문을 통해서 확인하는 과정이 필요합니다.

위 알고리즘의 시간복잡도는 $O(n^2)$입니다. Input Value의 갯수가 백만 개 정도만 되어도 $O(n^2)$의 알고리즘은 실행시간이 10초 이상 소요된다고 알려져 있습니다.

Binary Search

위와 같은 시간복잡도를 개선하기 위해서 LIS를 구성할 때 이분탐색을 활용합니다.

즉, LIS의 형태를 유지하기 위해 주어진 배열의 인덱스를 하나씩 살펴보면서 그 숫자가 들어갈 위치를 이분탐색으로 탐색해서 넣습니다.

이분탐색은 일반적으로 시간복잡도가 $O(logn)$이라고 알려져 있으므로, 이 문제의 시간 복잡도를 $O(nlogn)$으로 개선시킬 수 있게 됩니다.

해당 자료에도 설명이 자세히 적혀있지만, 다시 한번 풀어서 여기에 정리해 보겠습니다.

일단, 먼저 기존 배열과 크기가 같은 배열을 하나 생성해 줍니다.

그리고 이제 기존 배열(arr)의 첫번째 요소를 생성한 배열(lis)에 넣어주고 두번째 요소부터 마지막 요소까지 탐색을 시작합니다.

이때 선형 탐색을 하므로 시간 복잡도는 $O(n)$인 상태입니다.

탐색할 때 대소 비교를 하는데 첫번째 기준은 lis배열의 마지막 요소와 현재 탐색중인 arr[i]를 기준으로 합니다.

• lis의 마지막 요소 < arr[i]: arr[i]가 lis의 마지막 요소 뒤에 들어간다. (추가)
• lis의 마지막 요소 > arr[i]:
  • 이분 탐색을 이용하여 현재 요소가 어느 위치에 들어가야 되는지 확인한다.
  • Index값을 찾으면 lis배열의 해당 Index에 arr[i]를 넣어줍니다. (대체)

여기서 이분 탐색을 통해서 찾은 Index에 arr[i]를 넣어주는 것이 이해하기 어려운데 다음 예시를 한번 더 봐보자.

처음에 5 6 7을 넣어줄 때는 순서대로 memo배열에 요소값들이 들어갑니다.

하지만, 이후에 다음 요소들 1 2 3 4의 경우 값이 memo의 마지막 요소의 7보다 작기 때문에 이분 탐색을 통해서 위치를 찾아갑니다.

이때, 저렇게 대체하는 방식이 허용되는 이유는 두가지라고 생각됩니다.

1. 어차피 memo의 배열의 길이는 대체를 하더라도 커지지 않는다.
2. 요소가 대체 되고난 후 lis의 마지막 요소보다 큰 값이 나와서 추가되더라도 이전 요소보다 뒤에 있는 요소라서 문제가 없다.

예를 들어봅시다.

{5, 6, 7, 1, 8, 2, 3}이라고 하면 처음에

5 6 7 1 은 위에서와 동일하게 채워질 것입니다. 하지만, 8의 경우 lis의 마지막 요소인 7보다 큰 값이기 때문에 7 뒤에 붙을 것입니다.

따라서 현재 lis의 배열은 이와 같습니다.

arr	5	6	7	1	8	2	3
memo	1	6	7	8

배열의 현재 상태에 현혹되지 말고 len값에만 주목하자.

현재 len값은 4인 상태이고 5 6 7 8일 때와 같습니다. 또한, 8보다 큰 값이 나오는 것이 아니면 len값이 변경되지 않을 것입니다. 최종적으로는 다음과 같이 되겠죠.

arr	5	6	7	1	8	2	3
memo	1	2	3	8

즉, LIS는 4인 것입니다.

전체 코드를 살펴보면 다음과 같습니다.

static int binary_search(int[] lis, int left, int right, int target) {
  int mid;

  while (left < right) {
    mid = (left + right) / 2;

    if(lis[mid] < target) {
      left = mid + 1;
    }
    else {
      right = mid;
    }
  }

  return right;
}

static int lis_dp(int[] lis, int[] arr, int N) {
  lis[0] = arr[0];

  int len = 1;
  for (int i = 1; i < N; i++) {
    if (lis[len - 1] < arr[i]) {
      lis[len++] = arr[i];
    }
    else if (lis[len - 1] > arr[i]){
      int idx = binary_search(lis, 0, len - 1, arr[i]);
      lis[idx] = arr[i];
    }
  }
  return len;
}

---

Reference

• 알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘 | ChanBLOG
• [알고리즘] 가장 긴 증가하는 부분 수열 LIS - DP & 이진탐색 (Java)