[ 자바스크립트(JavaScript) ] section10 - 3 - 최장 부분 증가수열(LIS)

📍 section10 - 3 - 최대 부분 증가수열(LIS)

문제: N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내고 길이가 5인 최대부분증가수열을 만들 수 있다.

 

이 문제는 LIS 문제인데, 저번에 현대카드 코딩테스트에서 LIS를 사용하는 문제가 나왔었다. (물론 그때는 몰라서 못 풀었다. 🥲 ) 이번기회에 배우고 다음에 LIS 문제가 나오면 말끔하게 풀어버리자. LIS문제도 마찬가지로 DP를 사용하는데, DP의 특징 중 하나인 각 단계별로 쪼갠 다음, 이전의 결과를 그대로 사용한다.

 

1. dy[j]: arr[i]를 제일 마지막에 둘 때 만들 수 있는 수열의 최대 길이
2. 맨 처음 1가지의 수로 만들 수 있는 최대 수열의 길이는 1이다. (dp[0]=1)
3. 예를 들어 i===3 일 때, dy[3]을 구하려면 arr[3]을 기준으로 i-1~0까지 반복문을 돌면서 arr[3]과 arr[j]의 대소관계를 비교한다. 만약, arr[i] > arr[j]라면, dp[j] 중 제일 큰 값에 +1을 해서 dp[i]에 넣어줘야 한다. (+1을 해주는 이유는 나를 제외한 현재 최대 수열의 길이가 dp[j]이므로 여기에 나를 붙이면 수열의 길이는 1 증가하기 때문이다.) 그리고 바로 이전의 dp[j]만 비교하는 것이 아니고 i-1~0까지 모든 dp[j]를 조사하므로 dp[j]>max 조건을 같이 넣어주어 max 변수를 최대 값으로 갱신하는 방법을 사용했다.(dp[j] > max면 max=dp[j])
4. arr[3]일 때는 8을 가리키는데, 8보다 작은 값 중 제일 큰 값은 7(이때 dp[j]=2), 7 뒤에 8을 두면 최장 증가 수열을 갱신 할 수 있다. (이때 2가지의 경우가 생기는데 5 7 8, 3 7 8이고 수열의 길이는 3이다.)

 

 

 

728x90

 

 

// 입력
8
5 3 7 8 6 2 9 4

// 코드
let n = 8;
let arr = [5, 3, 7, 8, 6, 2, 9, 4];

console.log(solution(n, arr));

function solution(n, arr){
  if (n === 1) return 1;
  let dp = Array.from({length: n}, () => 0);
  let answer = 0;

  dp[0]=1;

  for (let i=1; i<n; i++){
    let max=0;
    for (let j=i-1; j>=0; j--){
      if (arr[i] > arr[j] && dp[j] > max) max = dp[j]
    }
    dp[i]=max+1;
    answer = Math.max(answer, dp[i]);
  }
  return answer;
}

👉🏽 4