가장 긴 증가하는 부분 수열 Longest Increasing Subsequence(LIS)

 

개인적으로 알고리즘은 즉각적으로 바로 구현할 수 있도록 몸에 베어야 하되 복습하는 데 너무나 많은 시간을 투자해서는 안 되고, 문제를 풀면서 실전으로 익혀야 한다고 생각한다. 학기가 시작되면서 바빠진 만큼 지난 잊힌 알고리즘 개념들을 핵심과 코드만 짧게 정리하여 평소에도 자주 보면서 익숙해지고자 한다. 기본적으로 코드는 특별한 설명이 없으면 C++를 기반으로 한다.

 

 

가장 긴 증가하는 부분 수열 Longest Increasing Subsequence(LIS)

 

정의

주어진 sequence의 모든 부분 수열(subsequence) 중 오름차순으로 정렬된 가장 긴 수열

 

문제

길이가 $N$인 임의의 수열 A의 Longest Increasing Subsequence(LIS) 길이를 구해보자.

 

방법

시간복잡도에 따라서는 크게 두 가지로, 구분할 수 있고, 사용하는 자료구조의 관점에서는 크게 세 가지 방법으로 요약할 수 있다.

 

1. 동적 계획법(DP)

(1) $O(N^2)$ 알고리즘

(2) 다음과 같은 메모이제이션 배열을 정의한다.

dp[i]: A[i]를 마지막 원소로 가지는 가장 긴 증가하는 부분 수열의 길이

(3) A[i]가 어떤 증가하는 부분 수열의 마지막 원소가 되기 위해서는 A[i]가 추가되기 전에 증가하는 부분 수열의 마지막 원소가 A[i]보다 작아야 한다.

 

반복적 동적 계획법

for (int i = 0; i < n; i++){
	dp[i] = 1;
    for (int j = 0; j < i; j++){
    	if (a[i] > a[j] && dp[i] < dp[j] + 1){
        	dp[i] = dp[j] + 1;
        }
    }
}

 

재귀적 동적 계획법

cache[i]: a[i]에서 시작하는 가장 긴 증가하는 부분 수열의 길이

int go(int start){
	int& ret = cache[start];
    
    if (ret != -1){
    	return ret;
    }
    
    ret = 1; 
    
    for (int i = start + 1; i < n; i++){
    	if (a[start] < a[i]){
        	ret = max(ret, go(i) + 1);
        }
    }
    
	return ret;
}

 

 

2. Binary Search

(1) $O(N \log N)$ 알고리즘

(2) 다음과 같은 배열을 사용한다.

s[i]: 길이가 i+1인 LIS 중에서 마지막 원소로 올 수 있는 가장 작은 수

(3) 앞에서 최대한 작은 수들로 LIS가 구성되어야 뒤에서 더 많은 수들로 더 긴 LIS를 형성할 가능성이 있으므로 lower_bound 사용

s.push_back(a[0]);

for (int i = 0; i < n; i++){
	auto iter = lower_bound(s.begin(), s.end(), a[i]);
    if (iter >= s.end()){
    	s.push_back(a[i]);
    }
    else {
    	*iter = a[i];
    }
}

printf("%d\n", s.size()); // LIS의 길이 출력

 

 

3. Segment Tree

(1) $O(N \log N)$ 알고리즘

(2) 다음과 같은 세그먼트 트리의 leaf에 대응되는 배열을 사용한다.

d[i]: a[i]를 마지막 원소로 가지는 가장 긴 증가하는 부분 수열의 길이

(3) 0번째부터 $N-1$번째 원소까지 loop를 실행하면서 매번 a[i]보다 작은 배열 d의 원소들 값 중에서 최댓값을 query로 구하고, d[i] = (찾은 최댓값) + 1로 계산한다.