JavaScript로 가장 긴 증가 부분 수열(LIS)의 개수 구하는 방법

문제 이해하기

숫자 배열 arr를 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수의 목표는 배열에서 만들 수 있는 가장 긴 증가 부분 수열(Longest Increasing Subsequence, LIS)이 총 몇 개 존재하는지 세어 반환하는 것입니다. 여기서 부분 수열은 원소들이 서로 인접하지 않아도 되며, 원래 배열의 순서만 유지하면 됩니다.

예시로 살펴보기

예를 들어 함수에 다음 배열을 입력한다고 가정해 보겠습니다.

입력

const arr = [2, 4, 6, 5, 8];

출력

const output = 2;

출력 설명

길이가 4인 가장 긴 증가 부분 수열은 두 개 존재합니다. 바로 [2, 4, 5, 8]과 [2, 4, 6, 8]입니다. 따라서 결과값은 2가 됩니다.

풀이 접근 방식

이 문제는 동적 계획법(Dynamic Programming)으로 해결할 수 있으며, 두 개의 보조 배열을 활용합니다.

• distance[i]: i번째 원소에서 끝나는 가장 긴 증가 부분 수열의 길이
• count[i]: 그 길이를 가지는 부분 수열의 개수

배열을 순회하면서 현재 원소보다 작은 앞선 원소들을 확인합니다. 새로운 더 긴 수열을 만들 수 있으면 distance와 count를 갱신하고, 이미 같은 길이의 경로가 존재하면 count를 누적합니다. 마지막에는 전체 최장 길이 max와 같은 distance 값을 가진 위치들의 count를 모두 더해 최종 답을 구합니다.

구현 코드

다음은 위 접근 방식을 구현한 전체 코드입니다.

const arr = [2, 4, 6, 5, 8];
const countSequence = (arr) => {
   const distance = new Array(arr.length).fill(1).map(() => 1)
   const count = new Array(arr.length).fill(1).map(() => 1)
   let max = 1
   for (let i = 0; i < arr.length; i++) {
      for (let j = i + 1; j < arr.length; j++) {
         if (arr[j] > arr[i]) {
            if (distance[j] <= distance[i]) {
               distance[j] = distance[i] + 1
               count[j] = count[i]
               max = Math.max(distance[j], max)
            } else if (distance[j] === distance[i] + 1) {
               count[j] += count[i]
            }
         }
      }
   }
   return distance.reduce((acc, d, index) => {
      if (d === max) {
         acc += count[index]
      }
      return acc
   }, 0)
}
console.log(countSequence(arr));

실행 결과

2

복잡도 분석

이 풀이는 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)입니다. 또한 길이와 개수를 저장하는 보조 배열 두 개를 사용하므로 공간 복잡도는 O(n)입니다. 배열의 크기가 수천 개 수준이라면 충분히 실용적인 성능을 기대할 수 있습니다.