📏

[JS] LIS (최장 증가 수열)


LIS(Longest Increasing Sebsequence)

최장 증가수열 문제는 어떤 배열에서 특정 부분을 지워 만들 수 있는 증가 부분수열 중 가장 긴 수열을 구하는 문제다.

배열이 [1, 4, 4, 6, 8, 3]이면 증가부분수열은 [1, 4, 6, 8], [4, 6, 8], [4, 8], [6, 8]이다. 여기서 가장 긴 증가 부분수열은 [1, 4, 6, 8]이다.

가장 쉬운 방법은 모든 증가부분수열을 구해 가장 긴 것을 찾는 것이지만, 같은 연산을 반복하기 때문에 O(2N)O(2^N)의 시간복잡도를 가진다.

이 문제를 효율적으로 해결하는 두 가지 방법을 살펴보겠다.

동적 계획법

깉은 연산을 반복하는 것을 막기 위해서는 이전에 계산했던 것을 저장해놨다가 사용해야한다.

이때 저장하는 값은 D[i]로, A[i]를 마지막 값으로 가지는 가장 긴 증가부분수열의 길이를 나타낸다.

A[i]가 어떤 증가부분수열의 마지막 값이 되기 위해서는 A[i]가 추가되기 전 증가부분수열의 마지막 값이 A[i]보다 작은 값이여야 한다. 따라서 A[i]를 마지막 값으로 가지는 가장 긴 증가부분수열의 길이는 A[i]보다 앞에 있는 증가부분 수열의 길이에 1을 더한 값이 된다.

이 규칙대로 첫 번째 원소부터 순회하며 D[i]를 갱신했을 때 D 배열의 최대값이 바로 가장 긴 증가부분수열의 길이가 된다.

1const arr = [1, 4, 4, 6, 8, 4];
2const dp = Array(6).fill(1);
3
4for (let i = 0; i < arr.length - 1; i++) {
5 for (let target = i + 1; target < arr.length; target++) {
6 if (arr[i] < arr[target]) {
7 dp[target] = Math.max(dp[i] + 1, dp[target]);
8 }
9 }
10}
11
12const lis = Math.max(...dp);

해당 길이를 가지는 수열을 찾고 싶으면, 해당 값을 가지는 원소부터 거꾸로 이어나가면 된다.

각 원소마다 다른 모든 원소를 훑어보기 때문에 O(N2)O(N^2)의 시간복잡도를 가진다. 완전 탐색보다 획기적으로 개선했지만, 이것보다 더 개선할 수 있다.

이분 탐색

이분 탐색을 사용한 아이디어는 다음과 같다.

LIS를 만드는 과정을 보면 LIS의 마지막 원소가 가능한 작을수록 더 긴 LIS를 생성할 수 있다는 것을 알 수 있다. 따라서 현재 생성된 LIS가 있는데 새로운 원소가 LIS의 마지막 원소보다 작은 경우, 들어갈 위치를 이분 탐색으로 찾은 후 대체시키며 LIS를 찾을 수 있다.

예를 들어 배열이 [1, 2, 3, 7, 5, 6]일 때 5까지 탐색한 경우, 가능한 LIS는 [1, 2, 3, 7][1, 2, 3, 5]다. 하지만 더 긴 LIS를 만들기 위해서는 [1, 2, 3, 5]가 더 유리하다.

따라서 [1, 2, 3, 7] 다음 5가 들어온다면 7과 바꿔주는 것이다.

1const arr = [1, 2, 3, 7, 5, 6];
2const lis = [];
3
4lis.push(arr[0]);
5for(let i = 1; i < arr.length; i++) {
6 // 이분 탐색으로 위치 찾기
7 let left = 0, right = lis.length;
8 while(left < right) {
9 const mid = Math.floor((left + right) / 2);
10 if(arr[i] > lis[mid]) left = mid + 1;
11 else right = mid;
12 }
13
14 if(right === lis.length) lis.push(arr[i]);
15 else lis[right] = arr[i];
16}

각 원소에 대해 이분 탐색으로 확인하기 때문에 O(NlogN)O(N\log N)의 시간복잡도를 가진다.

주의해야할 점은 lis 배열의 원소가 최장증가수열과 일치하지 않는다는 것이다. 오직 길이만을 알 수 있다.

최장증가수열을 알고싶다면 배열을 하나둬서 각 원소가 들어간 인덱스를 저장하면 된다. 이 배열을 사용해서 동적 계획법에서 한 것처럼 거꾸로 이어나가면 된다.


참조:
https://rebro.kr/33
https://chanhuiseok.github.io/posts/algo-49/