LIS문제 -DP

LIS문제: 최장 증가 부분 수열

배열의 일부분을 순서대로 추출했을 때 크기가 커지는 배열들의 집합 중에서 가장 길이가 긴 수열 찾기

문제의 답은 여러개가 될 수 있다.

[8, 2, 6, 5, 4, 9, 2, 7, 5, 1] 배열이 있다면 [2, 4, 9] 배열은 정답 후보에 있을 수 있다.

생각해보면 커지는 것을 발견하면 선택하는 식으로 해결한다면?

[1,2,9, ~~~] 에서 9를 선택했는데 ~~~부분이 3,4,5,6,7 이렇게 더 긴 조합을 생성할 수 있으므로 유의해야 한다.

 

DP

[8, 2, 6, 5, 4, 9, 2, 7, 5, 1]

8이 배열의 마지막인 배열들 중 가장 길이가 긴 것은 [8] 하나밖에 없다.

[8, 2, 6, 5, 4, 9, 2, 7, 5, 1]

2가 배열의 마지막인 부분배열들 중 가장 길이가 긴 것도 마찬가지로 [2]하나이다.

[8, 2, 6, 5, 4, 9, 2, 7, 5, 1]

9가 제일 끝인 경우에서 9이전에 선택한 숫자들을 생각해보자.

[~4,9] 이런 형태의 배열이 정답 후보에 있을 것이고 이때 모든 경우를 생각할 필요없이 DP개념을 생각해볼 수 있다.

9를 붙일 수 있는 부분수열 집합들 중에서 가장 긴 수열끝에 9를 붙이면 해결이 된다.

[~~]+[9] -> [~~]는 9를 붙일 수 있는 부분수열 집합들이고 [~~]또한 마찬가지로 마지막 요소를 제외하고 남은 부분수열 집합들 중에서 가장 긴 것을 선택한 것이라 보면 된다. 이 과정에서 많은 반복작업이 있기 때문에 DP를 쓰는 것이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class LIS {

	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		st = new StringTokenizer(bf.readLine());

		int[] arr = new int[st.countTokens()];
		int[] LIS = new int[st.countTokens()];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int max = 0;
		for (int i = 0; i < arr.length; i++) {
			LIS[i] = 1;
			for (int j = 0; j < i; j++) {
				if (arr[j] < arr[i] && LIS[i] < LIS[j] + 1) {//자신이 뒤에 붙을 수 있는 경우 + 붙을 수 있는 것들 중 가장 긴 것을 선택
					LIS[i] = LIS[j] + 1;
				}
			}
			max = Math.max(max, LIS[i]);
		}
		
		
		System.out.println(Arrays.toString(arr));
		System.out.println(Arrays.toString(LIS));
		System.out.println(max);

	}

}

코드 결과

 

DP 이진 탐색

[1, 3, 4, 5, 2, 6, 8, 2, 5, 3]배열이 주어지고 순서대로 탐색을 시작한다.

[1,3,4,5]까지 순서대로 들어가게 되었다. 2는 5를 만나서 다음에 넣을 수는 없다.

이때 2를 버리는 것이 아니라 앞에서 자신이 들어갈 수 있는 공간 중에서 가장 뒤에 있는 위치에 찾아 대체한다.

2는 1, 3 위치를 대체할 수 있게되고 3 위치가 가장 뒤에 있기 때문에 3을 2로 바꾼다.

이런 경우 문제가 되지 않을까? -> 2다음에 탐색할 6은 5와 비교하는 것이 아니라 삽입된 2랑 비교해서 크면 다음 숫자를 대체한다.

 

최근 사용한 숫자위치에 커서가 있다고 생각하면 편하다. 대체하고 다음 숫자를 대체하더라도 목표는 최대 길이라서 유효한 숫자들로 구성된 최종 배열길이를 선택하면 끝이다. 삽입된 숫자는 뒤에있는 숫자들은 이후 대체될 숫자들이기 때문에 길이가 늘어날 경우는 대체가 전부 이루어졌고 추가로 더 붙일 수 있을 때다. 

 

생각해보면 자신의 위치를 찾는데 처음부터 자신 앞부분까지 탐색을 하게 될텐데 일반 DP문제와 시간 복잡도가 같은데?

->이를 개선하는 방법은 이진탐색을 통해 logN 시간복잡도로 자신의 위치를 찾을 수 있다. 

원리를 이해하면 DP개념보다는 구현 느낌이 든다.

		int[] arr = new int[st.countTokens()];//
		int[] LIS = new int[st.countTokens()];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int max = 0;
		
		int size=0;
		for(int i = 0 ; i < arr.length ;i++) {
			
			int idx = Arrays.binarySearch(LIS, 0,size,arr[i]);//들어갈 공간
			if(idx>=0) continue; //같은 수 있으면 패스
			
			int insert = Math.abs(idx)-1;
			LIS[insert] = arr[i];
			
			if(insert==size) size++;
			
			System.out.println(Arrays.toString(arr));
			System.out.println(Arrays.toString(LIS));
			System.out.println(size);
            }