LIS 알고리즘

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

해당 문제에 가장 유명한 문제는 가장 긴 증가하는 부분 수열이다. 실제로 LIS 알고리즘을 알게 된 계기도 이와 유사한 문제를 풀다가 알게 되었다.

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);
		}
	}
}

해당 문제의 가장 간단한 풀이 방식은 다음과 같이 DP를 이용하여 풀이하는 방법이 있다. 하지만 이 문제의 시간복잡도는 O(n^2)가 되어 비효율적이게 된다.

이를 개선하기 위해 이분 탐색 방법을 이용해 LIS 문제를 해결할 수 있게 된다.
LIS를 기록하는 배열을 하나 더 두고, 원래 수열에서의 각 원소에 대해 LIS 배열 내에서의 위치를 찾는다.
즉, LIS의 형태를 유지하기 위해 주어진 배열의 인덱스를 하나씩 살펴보면서 그 숫자가 들어갈 위치를 이분탐색으로 탐색해서 넣는다.

이를 JavaScript로 구현하면 다음과 같이 구현할 수 있다.

function lengthOfLIS(nums) {
    let lis = [];

    for (let num of nums) {
        // lis 배열에서 num의 위치를 찾기 위해 이분탐색 수행
        let left = 0, right = lis.length;
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (lis[mid] < num) left = mid + 1;
            else right = mid;
        }
        
        // left는 num이 들어갈 위치
        // 만약 left가 lis 길이와 같다면, 새로운 원소를 추가
        if (left === lis.length) lis.push(num);
        // 아니면 기존 원소를 대체
        else lis[left] = num;
    }
    return lis.length;
}

참고 자료

최강 증가 부분 수열(LIS) 알고리즘