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

jaemin·2021년 7월 6일
2

알고리즘

목록 보기
7/7
post-thumbnail

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

📌최장 증가 부분 수열이란?

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

예를 들어 다음 수열이 있다고 가정합시다.

[3, 5, 7, 9, 2, 1, 4, 8]

위 수열에서 몇 개의 수를 제거해 부분수열을 만들 수 있습니다. (여기서 한 가지 헷갈렸던 점은, 꼭 공차가 존재하지 않아도 부분수열로 본다는 점입니다. 수열 [1, 3, 5, 7]같이 공차가 존재하지 않더라도 부분수열입니다.)

[3, 7, 9, 1, 4, 8] (5, 2제거)
[3, 5, 7, 8] (9, 1, 4제거)
[1, 4, 8] (3, 5, 7, 9, 2제거)
... 등등

이들 중 두 번째와 세 번째 수열은 오름차순으로 정렬되어 있습니다. 이를 증가 부분 수열이라고 합니다.
그리고, 이런 증가 부분 수열 중에서 가장 긴 수열을 최장 증가 부분 수열(LIS) 라고 합니다. 예제 수열에서 LIS는 [3, 5, 7, 8] 입니다.

📌LIS를 구하는 방법

🔍 1. DP 이용하기 : O(N^2)

D[i]는 i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이를 의미합니다. 부분수열 A의 i번째 요소가 어떤 증가 부분 수열의 마지막 값이 되기 위해서는 A[i]가 추가되기 전 증가부분수열의 마지막 값이 A[i]보다 작은 값이어야 합니다. 따라서 A[i]를 마지막 값으로 가지는 가장 긴 증가 부분 수열의 길이는 A[i]가 추가될 수 있는 증가 부분 수열 중 가장 긴 수열의 길이에 1을 더한 값이 됩니다.

for (let i = 0; i < n; i++) {
  D[i] = 1;
  for (let j = 0; j < n; j++) {
    D[i] = Math.max(D[i], D[j] + 1);
  }
}

이 알고리즘은 n개의 수들에 대해 모든 수들을 다 훑어봐야 하므로 O(N^2)의 시간복잡도를 가집니다. 만약 n이 백만 개 정도만 되어도 실행시간이 10초 이상 소요됩니다.

🔍 2. 이분탐색 이용하기 : O(NlogN)

1번 방법의 시간복잡도를 개선하기 위해 이분탐색을 활용할 수 있습니다. 1번은 n개의 수가 모든 수를 훑어봤지만 이분탐색을 활용하면 모든 수를 탐색하지 않고 해결할 수 있습니다.

이분탐색으로 타겟수가 배열안 mid에 해당하는 수보다 크다면 start point를 mid + 1로 옮기고, 작거나 같다면 end point를 mid - 1로 옮깁니다. 이런 작업을 반복해 타겟수가 배열 안에 어디에 넣을지 결정할 수 있습니다.

function binary_search(arr, val) {
  start = 0;
  end = arr.length - 1;
  
  while (start <= end) {
    mid = (start + end) / 2;
    
    if (arr[mid] > val) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  
  return start;
}

num_arr = [3, 7, 9, 1, 4, 8];
D = [];

for (const num of num_arr) {
  if (D.length === 0 || D[D.length - 1] < num) {
    D.push(num);
  } else {
    D[binary_search(D, num)] = num
  }
}

📎 Reference

profile
프론트엔드 개발자가 되기 위해 공부 중입니다.

0개의 댓글