LIS구현하기

코드스테이츠 문제를 풀다가 좀 잘 이해가 되어서 따로 정리를 해본다.

const LIS = function (arr) {
  const N = arr.length;

  const lis = Array(N).fill(1);
  let a = []
  for (let i = 1; i < N; i++) {
    for (let j = 0; j < i; j++) {
      if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
        lis[i] = lis[j] + 1;
        if (a.indexOf(arr[j]) === -1) {
          a.push(arr[j]);
        }
        if (a.indexOf(arr[i]) === -1) {
          a.push(arr[i]);
        }
        console.log(a);
      }
    }
  }
  return Math.max(...lis);
};

LIS([3, 10, 2, 1, 20]);

문제는 연속되지 않는 부분 배열중에 완전 오름차순일 경우 가장 큰 길이를 도출해라 라는 문제이다.

즉 보기가 저렇게 주어지면 정답의 배열은 [3,10,20]이 될 것이다.

• 왜냐하면 오름차순도 이루어 져야 하기 떄문에

이 해결법 같은 경우에는 DP를 활용하였다.

• 개인적으로 DP는 문제가 시각적으로 보이지 않아서 많이 어려운것 같다 ㅠㅠ

lis가 수를 누적해서 가지는 값이다.

i는 1부터 시작하여 그 뒤에있는 값을 비교하고 해당 값이 if문 안에 들어오면 lis의 값을 갱신해 준다.

예를들어보면

i가 1이면 10을 가르키고 그 뒤에있는 값은 3밖에 없다.

그러면 lis의 1번쨰 인덱스의 값은 2가 될 것이다.
- 왜냐면 if문안에 들어가기 떄문에

우리는 이 2라는 값이 [3,10]배열을 가르킨다는 것을 인지하여야 한다.
- 이러한 경우가 DP가 어렵게 느껴지는 이유 같다.

이후 계속 진행이 되다가 i가 20을 가르킬떄 뒤에 있는 값들은 3,10,2,1이 될 것이고

if문안에는 모든 값이 들어갈수 있게 될 것이다.

그럼 단순하다 계속 갱신을 해주면 된다.

처음에 j가 3을 가르키면 lis배열은 [1,2,1,1,2]가 될 것이다.

이후 j가 10을 가르키면 lis는 두번쨰 인덱스를 가르킬 것이고 그러면 lis의 배열은 [1,2,1,1,3]이 될 것이다.

그후의 과정은 진행이 되지 않는다.
- 왜냐하면 arr의 if문 조건은 성립하지만 lis의 if문 조건이 성립하지 않기 떄문이다.

a라는 배열 변수는 어떤 부분배열이 도출되었는지를 확인하고자 설정을 해주었다.

• [3,10,20]이라는 배열이 도출이 된다.