[Algorithm] 최장 증가 수열 (LIS)

최장 증가 수열(LIS)

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

 

푸는 방법

DP

• dp[x] : x번째 수를 마지막 원소로 가지는 list의 길이
• 라고 점화식을 두면 O(N^2)의 시간복잡도로 구현할 수 있음
• 하지만 N이 10만이 넘으면 이걸로 풀수 없음 -> 이분탐색으로 시간을 단축시키자

for (int k = 0; k < n; k++){
	length[k] = 1;
    for (int i = 0; i < k; i++){
        if(arr[i] < arr[k]){
            length[k] = max(length[k], length[i] + 1);
        }        
    }
}

이분탐색

• 시간 복잡도: O(NlogN)
• 다음으로 선택된 값이 감소하는 값이면 이분탐색으로 lower bound를 구해 해당 위치에 삽입
• 증가하는 값이면 맨 뒤에 새롭게 넣음

arr[2] -> arr[3], arr[3] -> arr[4]

참고

https://chanhuiseok.github.io/posts/algo-49/