Algorithm JS - 최대 부분 증가수열

jiny·2023년 3월 19일
0

JavaScript Algorithm

목록 보기
22/23
post-thumbnail

문제

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

입력 설명

첫째 줄은 입력되는 데이터의 수 N(1≤N≤1,000, 자연수)를 의미하고, 둘째 줄은 N개의 입력데이터들이 주어진다.

출력 설명

첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.

입력예제

8
5 3 7 8 6 2 9 4

출력예제

4

최대 부분 증가 수열(LIS)

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

과정

arr를 2중 for문으로 순회 하는데, 가장 첫 번째 값의 경우 비교 할 대상이 없으므로 dy에 초기화 한다.

그 다음 arr 요소 부터 arr의 i번째와 arr의 j번째와 비교하고, i가 더 크고, 만약 max값보다 dy[j]가 더 크다면 dy[j]를 max 값에 추가 시킨다. 하지만, 현재는 5보다 3이 더 작고, 더 이상 비교 대상이 없으므로 1이 된다.

7의 경우 {3,7}, {5,7} 2가지 경우의 수가 존재하므로, max 값 + 1이 되어 2가 된다.

9의 경우 {3,7,8,9}, {5,7,8,9} 총 4가지 경우의 수가 존재하므로 기존 max 값인 3의 1을 더한 4가 된다.

모두 순회 후 dy에서 가장 큰 값인 4가 정답이 된다.

코드

function solution(arr) {
  let size = arr.length;
  // dynamic array 생성
  let dy = Array.from({ length: size }, () => 0);
  let answer = 0;
  // dy 첫번째 요소 1로 초기화
  dy[0] = 1;
  // 전체 요소 순회
  for (let i = 1; i < size; i++) {
    // max 초기화
    let max = 0;
    for (let j = 0; j <= i; j++) {
      // 만약 오름 차순 수열이 가능하고, dy[j]이 max보다 크다면
      if (arr[i] > arr[j] && dy[j] > max) {
        // max에 dy[j] 할당
        max = dy[j];
      }
    }
    // dy[j]가 돌면서 arr[i]가 포함되지 않은 최대 오름 차순 수열의 길이 = max
    // 즉, 기존 max값에 자신이 포함된 길이가 새로운 max값이 된다.
    dy[i] = max + 1;
    // 기존 answer값과 dy[i] 비교 하며 큰 값을 answer에 할당
    answer = Math.max(answer, dy[i]);
  }
  return answer;
}

console.log(solution([5, 3, 7, 8, 6, 2, 9, 4]));

0개의 댓글