[DP]LIS

LIS

Longest Increasing Subsequence, 최장 증가 부분 수열, 가장 긴 증가하는 부분수열

최장 증가 부분 수열은 수열 A의 부분 수열 중 증가 수열이 되는 가장 긴 수열을 의미한다.

수열 A에는 int가 들어가고, 서서히 증가하는 것을 조건으로 최장 증가 부분수열을 구한다.

...
int[] A; //수열 A
int[] D; //각 자리에서 수열의 개수를 저장하는 배열

for(int i=0; i<N; i++) {
	for(int j=0; j<i; j++) {
		if(A[j] > A[i]) { //이전보다 작으면 수열로 추가 안됨 = 비교 필요
			if(D[j] > D[i]){ //이전 것 보다 길이가 짧으면 이전 수열로 사용
				D[i] = D[j];
			}
		}
	}
	D[i]++;
}

int max = 0;
for(int i=0; i<N; i++) {
	if(max < D[i]) {
		max = D[i];
	}
}

System.out.println(max);

위 식에서 중요한 부분은 주석으로 적어두었다. 간단히 과정을 정리하면 다음과 같다.

과정

1. A의 배열을 하나씩 검사한다. 현재 인덱스(i) 이전의 인덱스(j)들 중 자신보다 작은 경우, 가장 긴 수열 D[j]>D[i]을 i 수열의 길이로 두고, 다음 index를 탐색한다.
2. 다음 index(i++) 전에 현재 값을 수열에 포함 시킨다. D[i]++;
3. 이렇게 다 진행되면, 최장 증가 수열의 길이가 D에 저장된다. D의 max 를 출력하면 가장 긴 수열의 길이가 출력된다.

나는 따로 for를 두어서 max를 찾았지만, D[i]++; 에서 max를 찾도록 둘 수도 있다.

또한, 해당 시간 복잡도가 O(N^2) 이기 때문에 좀 더 빠르게 하기 위해서 이분탐색을 이용할 수 있다.

이분탐색을 이용하는 경우 (N이 100,000이상이면 이분탐색)

num은 배열에 숫자를 담는다. cnt에 최대 수열의 길이를 담을 것이다. LIS는 길이에 따라 최대값을 둘 것이다. 즉, LIS[3]이라는 숫자에는 길이가 3인 수열 중 가장 큰 값이 들어간다.

...
import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int [] num = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			num[i] = Integer.parseInt(st.nextToken()); //num에 숫자들을 담는다.
		}
		int cnt=1; // 수열의 길이를 가진다.
		int[] LIS = new int[N+1];
		LIS[0]=num[0]; // LIS에 left의 숫자 값을 둔다.

		for(int i=0; i<N; i++) {
			if(LIS[cnt-1]<num[i]) { //현재 탐색 기준인 i 와 현재 길이-1 중 가장 큰 값을 비교한다.
				LIS[cnt] = num[i]; // 크다면 현재 값을 지금 길이에 둔다.
				cnt++; // 길이를 증가 시켜서 더 큰게 있는 지 진행한다.++;
			}
			else {
				int l = 0;
				int r = cnt;
				while(l<=r) {
					int mid = (l+r)/2;
					if(LIS[mid]<num[i]) {
						l = mid+1;
					}
					else {
						r = mid-1;
					}
				}
				LIS[l] = num[i];
			}
		}
		System.out.println(cnt);
	}

}

이분 탐색의 경우 다음과 같은 과정을 가진다.

과정

1. for문을 통해 탐색 기준이 될 i 숫자를 두고 길이가 cnt-1(현재 파악된 길이)인 값을 비교한다. 만약 값이 크다면, 현재 길이에 i 수열 값을 둔다.
2. 만약, 값이 작다면 이분 탐색을 통해서 0~현재 길이 까지 값이 현재 i의 수보다 작은 것 중 가장 큰 것을 찾는다.
3. 찾은 값의 길이에 현재 숫자를 둔다.

이 과정을 반복하면, i를 기준으로 현재 길이의 작은 것 중 가장 큰 값에 i 숫자를 두게 되고, 이러면 LIS 기준을 만족하면서 최대값을 찾을 수 있다.

결론은 cnt에 최대 길이가 저장된다.