LIS(최장 증가 수열)

주어진 수열에서 원소들의 값이 증가하는 순서를 유지하는 최장의 부분 수열을 찾는 알고리즘

1. DP 방식

 

알고리즘:

1. dp 배열을 1로 초기화(최소값, 1개로 이루어진 수열)
2. 현재 요소보다 작은 요소들 중에서 가장 긴 dp 값을 찾아 현재의 dp 값을 업데이트

시간 복잡도: O(n^2)

 

function lis(arr) {
  const dp = Array(arr.length).fill(1);
  for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
      if (arr[i] > arr[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  return Math.max(...dp);
}

2. Binary Search 방식

알고리즘:

1. 빈 배열 sub를 준비
2. 입력 배열의 각 요소에 대해, sub 배열에서 자신보다 크거나 같은 요소 중 가장 작은 요소를 찾아 대체
3. 이분 탐색을 사용하여 대체할 위치를 탐색
4. 만약 모든 요소가 현재 요소보다 작다면, 현재 요소를 sub 배열에 추가

시간 복잡도: O(n log n)

function binarySearch(arr, left, right, key) {
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === key) {
            return mid;
        } else if (arr[mid] > key) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

function LIS(nums) {
    const sub = [];
    for (let i = 0; i < nums.length; i++) {
        let pos = binarySearch(sub, 0, sub.length - 1, nums[i]);
        if (pos < sub.length) {
            sub[pos] = nums[i];
        } else {
            sub.push(nums[i]);
        }
    }
    return sub.length;
}