LIS 알고리즘

Tags
Algorithm

개요

LIS(Longest Increasing Subsequence, 최장 증가 부분 수열) 알고리즘에 대해 정리한 페이지입니다.

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

개념

LIS(Longest Increasing Subsequence, 최장 증가 부분 수열) 알고리즘은 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 알고리즘입니다.

수열: [10, 20, 10, 30, 20, 50]

-----------------------------

LIS: [10, 20, 30, 50]
길이: 4

구현

DP 방법

다음과 같이 DP 방법으로 LIS를 구할 수 있습니다. arr[i]를 마지막으로 하는 LIS의 길이를 구해서 전체에서 최댓값을 찾는 방식으로 LIS의 길이를 구할 수 있습니다. 시간 복잡도는 O(N^2)입니다.

const arr = [10, 20, 10, 30, 20, 50];
const dp = Array(arr.length).fill(1);

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

console.log(Math.max(...dp)); // 최장 증가 부분 수열의 길이

만약 길이뿐만 아니라 실제 수열까지 필요한 경우 다음과 같이 구현할 수 있습니다.

const arr = [10, 20, 10, 30, 20, 50];
const dp = Array(arr.length).fill(1);

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

console.log(Math.max(...dp)); // 최장 증가 부분 수열의 길이

let result = [];
let count = Math.max(...dp);
let index = arr.length - 1;

while (count > 0) {
  if (dp[index] === count) {
    result.push(arr[index]);
    count--;
  }

  index--;
}

console.log(result.reverse()); // [10, 20, 30, 50]

이분 탐색 방법

다음과 같이 이분 탐색 방법으로 LIS를 구할 수 있습니다. 시간 복잡도는 O(N log N)입니다.

const arr = [10, 20, 10, 30, 20, 50];
const lis = [arr[0]];

for (let i = 1; i < arr.length; i++) {
  if (arr[i] <= lis[0]) {
    lis[0] = arr[i];
  } else if (arr[i] > lis[lis.length - 1]) {
    lis.push(arr[i]);
  } else {
    let left = 0;
    let right = lis.length - 1;

    while (left + 1 < right) {
      let mid = Math.floor((left + right) / 2);

      if (arr[i] <= lis[mid]) {
        right = mid;
      } else {
        left = mid;
      }
    }

    lis[right] = arr[i];
  }
}

console.log(lis.length); // 최장 증가 부분 수열의 길이

만약 길이뿐만 아니라 실제 수열까지 필요한 경우 다음과 같이 구현할 수 있습니다.

const arr = [10, 20, 10, 30, 20, 50];
const lis = [arr[0]];
const length = Array(arr.length).fill(0);
length[0] = 1;

for (let i = 1; i < arr.length; i++) {
  if (arr[i] <= lis[0]) {
    lis[0] = arr[i];
    length[i] = 1;
  } else if (arr[i] > lis[lis.length - 1]) {
    lis.push(arr[i]);
    length[i] = lis.length;
  } else {
    let left = 0;
    let right = lis.length - 1;

    while (left + 1 < right) {
      let mid = Math.floor((left + right) / 2);

      if (arr[i] <= lis[mid]) {
        right = mid;
      } else {
        left = mid;
      }
    }

    lis[right] = arr[i];
    length[i] = right + 1;
  }
}

console.log(lis.length); // 최장 증가 부분 수열의 길이

let result = [];
let count = lis.length;
let index = arr.length - 1;

while (count > 0) {
  if (
    length[index] === count &&
    (result.length === 0 || result[result.length - 1] > arr[index])
  ) {
    result.push(arr[index]);
    count--;
  }

  index--;
}

console.log(result.reverse()); // [10, 20, 30, 50]

Example

2631번: 줄세우기

const path = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = require("fs").readFileSync(path).toString().split("\n");
const N = Number(input[0]); // 아이들의 수, 2 <= N <= 200
const arr = [];

for (let i = 1; i <= N; i++) {
  arr.push(Number(input[i]));
}

const lis = [arr[0]];

for (let i = 1; i < N; i++) {
  if (arr[i] <= lis[0]) {
    lis[0] = arr[i];
  } else if (arr[i] > lis[lis.length - 1]) {
    lis.push(arr[i]);
  } else {
    let left = 0;
    let right = lis.length - 1;

    while (left + 1 < right) {
      let mid = Math.floor((left + right) / 2);

      if (arr[i] <= lis[mid]) {
        right = mid;
      } else {
        left = mid;
      }
    }

    lis[right] = arr[i];
  }
}

console.log(N - lis.length);

참고 자료

• 최장 증가 부분 수열 - 나무위키