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

최장 증가 부분 수열(LIS, Longest Increasing Subsequence)

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

방법 1 : DP

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

const arr = [6, 2, 5, 1, 7, 4, 8, 3];

이런 배열이 존재할 때, dp[4]은 7이 마지막인 증가 부분 수열의 길이가 저장된다. (3이다.)

const arr = [6, 2, 5, 1, 7, 4, 8, 3];  
const dp = new Array(arr.length).fill(0);

for (let i = 0; i < arr.length; i++) {
  // 자기자신 1
  dp[i] = 1;
  // 첫번째 요소부터 i까지 비교
  for (let j = 0; j < i; j++) {
    if (arr[j] < arr[i]) {
      dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
}

console.log(dp); // [1, 1, 2, 1, 3, 2, 4, 2];
// 4가 최장 증가 부분 수열의 길이인데, 2, 5, 7, 8 인 경우이다.

외부 반복문은 0부터 끝까지, 내부 반복문은 0부터 i까지 탐색한다.

dp가 업데이트 되는 기준은,
1. i번째 인덱스에서 끝나는 최장 증가 부분 수열의 마지막에 arr[i]를 추가했을 때
2. 추가하지 않고 기존 길이가 유지될 때

로 나뉜다.

말로써 좀 더 설명하면, 자신의 뒤를 살피면서 더 작은 값이 있다면 그때의 dp값에 +1을 자신의 dp값으로 갱신한다. 단 이때 원래의 값보다 큰 경우에만 갱신한다.

이 방법은 시간복잡도가 O(n^2)이 나오기 떄문에, 입력이 많아지면 많이 무거워 진다.

방법 2 : 이분 탐색

주어진 배열의 인덱스를 하나씩 살펴보면서 그 숫자가 들어갈 위치를 이분탐색으로 탐색해서 넣는다.

const binarySearch = (list, left, right, target) => {
  while (left < right) {
    let mid = Math.floor((left + right) / 2);

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

const arr = [6, 2, 5, 1, 7, 4, 8, 3];

const LIS = (arr) => {
  const lis = [];

  // 배열의 첫번째 값을 lis배열 처음에
  lis.push(arr[0]);

  // i= 1부터, lis의 마지막 값보다 arr[i] 크다면 그냥 삽입.
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > lis[lis.length - 1]) {
      lis.push(arr[i]);
    } else {
      // 그렇지 않다면 이진탐색으로 위치를 찾아 삽입
      let idx = binarySearch(lis, 0, lis.length - 1, arr[i]);
      lis[idx] = arr[i];
    }
  }
  return lis.length;
};

console.log(LIS(arr));

이진 탐색을 이용해서 O(nlogn)의 시간 복잡도를 갖는다.
lis 배열에 배열을 첫번째 값을 넣는다. 반복문을 돌며 배열의 요소와 lis의 마지막 값을 비교한다. 주석에 설명을 적어두었다.

lis 배열의 변화와 출력값이다. lis에 들어있는 최종 값은 우리가 알고있는 답과는 다르다.

[2,5] 다음이 [1,5] 인데 이때 사실 1은 무시하고 넘어가야한다. 하지만 이진탐색으로 자리는 계속 찾아가기 때문에 이런 결과가 나오는 것이다. 다만 최장 증가 부분 수열의 길이는 유지 되기 된다.