최장 증가 부분 수열(LIS) 알고리즘

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

예를 들어, [6, 2, 5, 1, 7, 4, 8, 3]이라는 배열이 있을 경우, LIS는 [2, 5, 7, 8]이 됩니다.

일반적으로 간편한 방법은 DP을 이용하는 것입니다.

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

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

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

i번째 인덱스에서 끝나는 LIS의 마지막에 arr[k]를 추가했을 때의 LIS 길이와
추가하지 않고 기존의 length[k]값

중 더 큰 값을 length[k]값을 업데이트합니다.

하지만 위 알고리즘의 경우 O(n^2)입니다. 인풋 값이 백만 개만 되어도 실행시간이 10초 이상 소요됩니다.

따라서 이분탐색으로 해결하는 방법도 있습니다.

이분탐색 LIS 알고리즘

이 알고리즘을 위해서는 lower_bound를 이용합니다.

LIS의 핵심 아이디어는 LIS의 마지막 원소가 가능한 작을수록 더 긴 LIS를 생성할 수 있다는 것입니다. 그러므로 원소가 들어올 때, 만약 현재 생성된 LIS의 마지막 원소보다 작은 경우, LIS에 들어갈 위치를 찾은 후 원소를 대체합니다.

간단한 예시로, [1, 2, 3, 7, 5, 6] 수열이 있을 때, 5까지 탐색을 한 경우 가능한 LIS는

[1, 2, 3, 7], [1, 2, 3, 5] 두가지가 만들어 집니다.

이 때, 우리가 구하고자 하는 것은 최장 길이를 가지기만 하면 되므로 둘 다 LIS를 만족하는데, 더 긴 LIS를 만들기 위해서는 [1, 2, 3, 7] 보단 [1, 2, 3, 5]가 적합하다.

실제로 마지막 원소 6이 들어올 때에는 [1, 2, 3, 7]로는 생성할 수 없고, [1, 2, 3, 5]에 붙어 [1, 2, 3, 5, 6]을 만들 수 있습니다.

하지만 이 알고리즘을 이용하면 길이만 구할 수 있습니다.

const origin = [3, 5, 2, 6, 1]
const arr = [];
let idx = 0;
for(let i = 0 ; i < n ; i++) {
  if(!idx) arr[idx++] = origin[i];
  else {
    if(arr[idx - 1] < origin[i]) arr[idx++] = origin[i];
    else arr[lower_bound(0, idx - 1, origin[i])] = origin[i];
    // arr배열에서 origin[i]보다 최초로 같거나 큰 위치를 찾는다.
  }
}

[3, 5, 2, 6, 1] 배열은 다음과 같이 진행됩니다.

[3]
[3, 5]
[2, 5]
[2, 5, 6]
[1, 5, 6]

실제로 LIS는 [3, 5, 6]이지만 [1, 5, 6]이 만들어집니다. 이러한 원리로 LIS의 길이는 구할 수 있지만, 실제 LIS의 수열을 구하기 위해서는 추가적인 작업이 필요합니다. 주어진 수열의 각각의 원소들이 K 배열에 들어가는 index를 배열로 별도로 저장합니다. 그리고 나서 마지막원소부터 LIS의 길이를 감소시켜 가면서, 처음으로 해당 길이의 index가 나오는 원소만 뽑아냅니다.

[3, 5, 2, 6, 1] 배열을 예로 들면,

[3]
[3, 5]
[2, 5]
[2, 5, 6]
[1, 5, 6]

이므로 3은 1번째, 5는 2번째, 2는 1번째, 6은 3번째, 1은 1번째 index에 들어가게 됩니다. 즉, index 배열은 [0, 1, 0, 2, 0]이 되는 것입니다.

LIS의 길이는 현재 3이므로 index 배열의 뒤에서부터 처음으로 2(index) + 1이 나오는 원소는 6이며, 그 다음 처음으로 1(index) + 1가 나오는 원소는 5, 그 다음 처음으로 0(index) + 1이 나오는 원소는 3이 된다. 따라서 이를 역으로 정렬하면 [3, 5, 6] 으로 우리가 구하고자 하는 LIS가 나오게 됩니다.

const origin = [3, 5, 2, 6, 1]
const arr = [];
const indexArr = [];
const ans = [];
const n = 5;
let idx = 0;

for(let i = 0 ; i < n ; i++) {
  if(!idx) {
    arr[idx++] = origin[i];
    indexArr[i] = 0; // 최초 위치
  }
  else {
    if(arr[idx - 1] < origin[i]) {
      indexArr[i] = idx;
      arr[idx++] = origin[i];
    }
    else {
      indexArr[i] = lower_bound(0, idx - 1, origin[i]);
      arr[lower_bound(0, idx - 1, origin[i])] = origin[i];
      // arr배열에서 origin[i]보다 최초로 같거나 큰 위치를 찾는다.
    }
  }
}

let t = 0;
for(let i = n - 1 ; i >= 0 ; i--) {
  if(idx === index[i] + 1) {
    ans[t++] = origin[i];
    idx--;
  }
}
console.log(ans.reverse());