2022/05/13) 3. 최대부분증가수열(LIS) [Dynamic programming(동적계획법)]

1. 문제

<최대부분증가수열(LIS : Longest Increasing Subsequence)>
: N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰수로) 원소들의 집합을 찾는 프로그램을 작성한다. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길이가 5인 최대 부분 증가수열을 만들 수 있다. 부분증가수열의 최대 길이를 출력한다.
(첫째 줄은 입력되는 데이터의 수(N)를 의미하고, 둘 째줄은 N개의 입력데이터들이 주어진다.)

2. 해결 방법

1. 최대부분증가수열 개념을 한 번 더 짚고 넘어가자. 최대 부분 증가 수열은, 수열의 순서를 유지하되, 갈 수록 증가(오름차순)하는 원소들로만 구성된 수열이다.
2. arr[0]부터 탐색해보자. arr[0]을 증가수열의 마지막항이라고 생각하고 앞의 인덱스값들을 탐색하면 된다. 그런데 수열의 순서를 유지해야 하므로, arr[0]가 제일 앞에 위치한 인덱스이기 때문에, 탐색할 필요도 없이 arr[0]의 최대길이는 1이 된다.
3. 그리하여 위에서 구한 arr[0]의 최대길이 값을 dy[0]에 저장해주면 된다.
   dy[i]의 의미를 정리하면, arr의 i번째 인덱스에 들어있는 값이, 증가수열의 마지막 항이라고 했을 때 구한 수열의 최대 길이값이 들어간다.
4. 증가수열의 마지막항을 구해주는 for문과 증가수열의 최대길이를 구해주는 for문 총 2개의 for문이 있다. 증가수열의 최대길이를 구해주는 for문에서 j는 (i-1)~0까지 돌건데, 만약 j탐색 시 해당되는 값(arr[])들이 여러 개라면 그 중에서 가장 큰 값(dy[])을 선택한다. 작은값을 선택하면 최대길이가 될 수 없기 때문이다.i가 3일 때(arr[3]=8), arr[0]=5 / arr[1]=3 / arr[2]=7 총 세개가 올 수 있다. 그러면 dy값을 확인해서(dy[0]/dy[1]/dy[1]), 가장 큰 값을 선택해준다.
5. i도 수열에 속하게 되므로, 가장 큰 값 + 1(i)를 해준다.

3. 정답

        <script>
            function solution(arr){  
                let answer = 0;
                let dy = Array.from({length:arr.length}, ()=>0);
                dy[0]=1; //인덱스 0 이전엔 값이 아예 존재하지 않으므로, 최대 길이는 0이 될 수 밖에 없음
                for(let i = 1; i < arr.length; i ++){
                    let max = 0; //밑의 if문 조건에 맞는 게 없을 시, 최대 길이는 0이 되어야 하므로, max를 0으로 초기화해둠
                    for(let j = i-1; j >= 0; j --){
                        if(arr[j] < arr[i] && dy[j] > max){
                            max = dy[j];
                        }
                    }
                    dy[i] = max + 1;
                    answer = Math.max(answer, dy[i]);  
                }
                return answer;
            }
            let arr=[5, 3, 7, 8, 6, 2, 9, 4];
            console.log(solution(arr));
        </script>