LIS알고리즘

최장 증가 부분 수열 LIS(Longest Increasing Subsequence)

최장 증가 부분수열이란 ?

임의의 수열이 주어질 때, 이수열에서 만들 수 있는 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분수열이라 한다. -나무위키-

예를 들어보자

3 5 7 9 2 1 4 8이란 수열있다.

위 수열에서 몇가지의 수를 선택하여 부분수열을 만들 수 있다.

이때 오름차순이면서 가장 긴 수열은

3 5 7 8 또는 3 5 7 9이다.

 

동적 계획법으로 최장 증가 부분 수열을 구해보겠다.

새로운 배열을Dp를 만들고 정의는 다음과 같다.

Dp[i]는 배열의 [i]를 마지막 값으로 가지는 수열의 lis이다.

 

index	0	1	2	3	4	5	6	7
A	3	5	7	9	2	1	4	8
Dp

 

index=0일때 Dp[0]=1이다.

index	0	1	2	3	4	5	6	7
A	3	5	7	9	2	1	4	8
Dp	1

 

index=1일때를 확인해 보자

A[1]은 A[0]보다 커 증가수열을 이룬다.

즉 Dp[0]에서 뒤에 A[1]이어서 만들었다고 볼 수 있다.

따라서 Dp[1]=Dp[0]+1=2

 

여기서 LIS를 구하는 첫번재 방법을 알 수 있다.

현제 index까지의 최대 증가 부분 수열은 A[index]>A[i] (index>i)이면서

현재 index보다 낮은 index중에 최대 증가 부분수열이 가장 큰값에서 1을 더한 값이다.

index	0	1	2	3	4	5	6	7
A	3	5	7	9	2	1	4	8
Dp	1	2

 

index=2일 때를 확인해 보자

A[2]=7이다. D[0]이나 D[1]뒤에 붙어서 증가수열을 이룰 수 있다. 

이때 최대 증가 부분 수열은 Dp[1]=2이다.

따라서 Dp[2]=Dp[1]+1=3이다.

index	0	1	2	3	4	5	6	7
A	3	5	7	9	2	1	4	8
Dp	1	2	3

 

index=3일 때를 확인해 보자

A[3]=9이다. D[0],D[1],D[2]뒤에 붙어서 증가수열을 이룰 수 있다. 

이때 최대 증가 부분 수열은 Dp[2]=3이다.

따라서 Dp[3]=Dp[2]+1=4이다.

index	0	1	2	3	4	5	6	7
A	3	5	7	9	2	1	4	8
Dp	1	2	3	4

 

index=4일 때를 확인해 보자

A[4]=2이다. D[0],D[1],D[2],D[3] 뒤에 모두 붙을 수 없다. 

따라서 Dp[4]=1이다.

index	0	1	2	3	4	5	6	7
A	3	5	7	9	2	1	4	8
Dp	1	2	3	4	1

 

index=5일 때를 확인해 보자

A[5]=1이다. D[0],D[1],D[2],D[3],Dp[4] 뒤에 모두 붙을 수 없다. 

따라서 Dp[5]=1이다.

index	0	1	2	3	4	5	6	7
A	3	5	7	9	2	1	4	8
Dp	1	2	3	4	1	1

 

index=6일 때를 확인해 보자

A[6]=4이다. D[0],Dp[4],Dp[5] 뒤에 모두 붙을 수 있다. 모두 1로 값이 같다.

따라서 Dp[6]=1+1=2이다.

index	0	1	2	3	4	5	6	7
A	3	5	7	9	2	1	4	8
Dp	1	2	3	4	1	1	2

 

index=7일 때를 확인해 보자

A[7]=8이다. D[3]을 빼고 모두 뒤에 모두 붙을 수 있다. 이중에 최대 값은 Dp[2]=3이다.

따라서 Dp[7]=Dp[2]+1=4이다.

index	0	1	2	3	4	5	6	7
A	3	5	7	9	2	1	4	8
Dp	1	2	3	4	1	1	2	4

 

주어진 배열 3 5 7 9 2 1 4 8에서 최장 증가 부분 수열의 크기는 4이다.

위 방법을 활용하여 백준 11053문제를 풀어보자

 

public static int Lis(int n) {
		if(dp[n]==null) {
			dp[n]=1;
			for(int i =0;i<n;i++) {
				if(arr[i]<arr[n]) {
					dp[n]=Math.max(Lis(i)+1,dp[n]);
				}
			}
		}
		return dp[n];
	}

동적 계획법 Top&Down 형식으로 풀 때 핵심적인 재귀 함수 부분이다. 

현재 배열의 index에서 낮은 index의 배열의 값을 비교하여 최대 증가 부분 수열을 업데이트 한다.