동적계획법 (Dynamic Programming) - (2) 최장 증가 부분 수열 (LIS)

최장 증가 부분 수열

 

 

정수로 구성된 수열 S=(a1, a2, ... , an)가 주어졌을 때, S의 부분 수열이란 S에서 임의로 k개의 원소를 순서적으로 선택한 수열로서 인덱스가 1 ≤ i1 < i2 < ... < ik ≤ n 의 조건을 만족하는 수열(ai1, ai2, ... , aik) 을 말한다. 

 

증가 부분 수열(increasing subsequence)이란, 이러한 부분 수열 중에 ai1 < ai2 < ... < aik 의 조건을 만족하는 수열이다.

최장 증가 부분 수열 (longest increasing subsequence - LIS) 문제는 이러한 증가 부분 수열 중 길이가 가장 긴 수열과 그 길이를 구하는 것이다.

 

예를 들어서, S={25,12,18,6,13,16,29,17} 에서 최장 증가 부분 수열 중 하나는 {12,13,16,17}이며 길이는 4이다. 물론, 길이가 4인 다른 부분 수열들이 존재할 수도 있다. {12,13,16,29} 도 길이 4를 가진 최장 증가 부분 수열이다.

이 문제에서는, 최장 증가 부분 수열이 여러 개가 있더라도 임의의 답을 하나만 구한다고 가정한다.

 

Q. 만약 우리가 주어진 수열의 모든 부분 집합으로 구성된 수열을 다 고려하고, 각 수열이 증가 부분 수열인지를 체크하여 증가 부분 수열들 중에서 가장 긴 부분 수열을 고른다면? (exhaustive search)

A. 원소의 개수가 n인 수열의 부분 집합 개수는 적어도 2^n개이므로, 일일이 다 구한다면 O(2^n)의 이상의 시간이 걸림.

 

동적 계획법

그렇다면 이 문제를 동적 계획법으로 해결하고자 한다. 그러기 위해서 우선 재귀적인 공식을 수립해야 한다.

 

hi 를 원소 ai로 끝나는 최장 증가 부분 수열의 길이라고 정의하자.

그렇다면, 우리가 원하는 최장 수열 증가 부분 수열의 길이 h는 a1로 끝나는 최장 증가 부분 수열의 길이 h1, a2로 끝나는 최장 증가부분 수열의 길이 h2, ... , an으로 끝나는 최장 증가 부분 수열의 길이 hn 중 가장 큰 값이 될 것이다.

 

가상적인 아주 작은 값 a0이 있다고 가정하면, 다음과 같이 되기 때문에

최장 증가 부분 수열의 길이는 아래와 같다. 

---

간단한 예시를 보며 더 자세히 알아보도록 하겠다. S= {9,5,2,8,7,3,1,6,4}

i	0	1	2	3	4	5	6	7	8	9
수열 ai	- ∞	9	5	2	8	7	3	1	6	4
길이 hi	0	1	1	1	2	2	2	1	3	3
전 값 pi의 인덱스					2	2	3		6	6

우리가 구하는 최장 증가 부분 수열의 길이는 3이고, 그 수열은 (2,3,6), (2,3,4)가 될 것이다. (전 값의 인덱스를 따라감)

 

각 hi를 구하기 위해서는, ai와 그 앞에 있는 (i-1)개의 원소들 ai-1,...,a1과 비교해야 하므로 전체 시간 복잡도는 O(n^2)

임을 알 수 있다. 

 

int longest (int s[]) {
	int i,j;
	int h[MAX]={0,} ,p[MAX]; //h는 부분 수열의 길이, p는 전 값의 index
	int max=0,index;

	for(i=1;i<MAX;i++){
		for(j=0;j<i;j++){
			if(s[i]>s[j] && h[i]<h[j]+1){
				h[i]=h[j]+1;
				p[i]=j;
            }
	for(i=1;i<MAX;i++){ //최대 부분 수열의 길이 찾기
		if(max<h[i]){
			max=h[i];
			index=i;
		}
	int lis[MAX]; // 최대 부분 수열을 저장하는 배열
	i = max;
	while(index!=0) {
		lis[--i]=s[index];
		index=p[index];
	}
	printf("longest increasing subseq");
	for (i=0;i<max;i++) printf("%d ", list[i]);
	printf("\n");
	return max;
    }