최장 증가 부분 수열(LIS, Longest Increasing Subsequence), 자바스크립트로 구현하기

 

 

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

 

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

 

방법

 

A[i] : 수열의 i 번째 수

D[i] : A[i]를 마지막 값으로 가지는 가장 긴 증가 부분 수열의 길이

 

수열 A = [3, 5, 7, 1]

 

첫 번째 방법은 i=0 부터 D[i]를 계산하는데, 각각의 D[i]를 계산할 때마다 앞에 위치한 수들을 모두 확인하여 자신보다 작은 숫자들의 D 값 중 최댓값을 찾고 1을 더해 D[i]를 계산한다. 

 

i	0	1	2	3	4
A[i]	0	3	5	7	1
D[i]	0

 

배열 A에 수열을 다음과 같이 저장하고 알고리즘의 규칙성을 위해 A[0]은 0으로 설정한다. A[0]은 수열에 포함된 수가 아니므로 D[0]은 0이 된다.

 

i	0	1	2	3	4
A[i]	0	3	5	7	1
D[i]	0	1

 

i가 1일 때: 

A[1] = 3, 3은 A[0] 뒤에 붙을 수 있기에 D[1] = D[0] + 1 인 1이 된다.

 

i	0	1	2	3	4
A[i]	0	3	5	7	1
D[i]	0	1	2

 

i가 2일 때: 

A[2] = 5, 3은 A[0], A[1] 뒤에 붙을 수 있다. 이들 중 최댓 값인 D[1] 에 1을 더해 D[2]는 2가 된다.

 

i	0	1	2	3	4
A[i]	0	3	5	7	1
D[i]	0	1	2	3

 

i가 3일 때: 

A[3] = 7, 3은 A[0], A[1], A[2] 뒤에 붙을 수 있다. 이들 중 최댓 값인 D[2] 에 1을 더해 D[3]는 3가 된다.

 

i	0	1	2	3	4
A[i]	0	3	5	7	1
D[i]	0	1	2	3	1

 

i가 4일 때: 

A[4] = 1, 3은 A[0] 뒤에 붙을 수 있다. D[0] 에 1을 더해 D[4]는 1이 된다.

 

배열 D 에 값을 다 채우면 [0, 1, 2, 3, 1] 이 완성된다. 이 중 가장큰 값이 최장 증가 부분 수열의 길이가 된다. 

 

코드로 구현

const LIS = function (arr) {
  //TODO: 여기에 코드를 작성합니다.

  const dp = new Array(arr.length).fill(0);

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

  return Math.max(...dp);
};