연관된 문제

[11053] 가장 긴 증가하는 부분 수열

최장 증가 부분 수열이란?

최장 증가 부분 수열이란 말그대로 주어진 수열에서 오름차순으로 구성 가능한 원소들을 선택해서 최대 길이를 찾아내는 것이다.
이분탐색 활용하면 O(NlogN)의 시간복잡도를 갖는다.

예를들어 수열 {10,20,10,30,20,50} 을 보자.
이를 arr[] 배열에 저장하고 dp[] 배열에서 다이나믹프로그래밍 값을 저장한다.

이 때 dp[n]은 n번째 인덱스까지의 값을 탐색했을 때 나올 수 있는 최장 증가 부분 수열의 길이이다.

dp[0] = {10} : 길이 1
dp[1] = {10, 20} : 길이 2
dp[2] = {10} : 길이 1
dp[3] = {10, 20, 30} : 길이 3
dp[4] = {10, 20} : 길이 2
dp[5] = {10, 20, 30, 50} : 길이 4

따라서 dp를 완성하면 위와 같은 결과가 나와야 한다.

알고리즘 구현

Top-Down(재귀) 방식

단순하게 생각하면 쉽다.
탐색하려는 인덱스에서 이전 위치들을 찾아가면서 해당 값보다 작을 경우 재귀호출을 통해 탐색해나간다.

static int LIS(int N) {
		
	// 만약 탐색하지 않던 위치의 경우 
	if(dp[N] == null) {
		dp[N] = 1;	// 1로 초기화 
			
		// N 이전의 노드들을 탐색 
		for(int i = N - 1; i >= 0; i--) {
			// 이전의 노드 중 seq[N]의 값보다 작은 걸 발견했을 경우
			if(seq[i] < seq[N]) {
				dp[N] = Math.max(dp[N], LIS(i) + 1);
			}
		}
	}
	return dp[N];
}

Bottom-UP(반복문) 방식

그냥 이중반복문으로 0~N-1까지 각 원소보다 큰 값들을 카운팅해준다.

for(int i = 0; i < N; i++) {
	dp[i] = 1;
    
	// 0 ~ i 이전 원소들 탐색
	for(int j = 0; j < i; j++) {
    
		// j번째 원소가 i번째 원소보다 작으면서 i번째 dp가 j번째 dp+1 값보다 작은경우
		if(seq[j] < seq[i] && dp[i] < dp[j] + 1) {
			dp[i] = dp[j] + 1;	// j번째 원소의 +1 값이 i번째 dp가 된다.
		}
	}
}

위의 방법들은 모두 시간복잡도 O(N^2)을 갖는다.
아직 이분탐색을 사용하지 않았기 때문이다!

이분탐색 방식

이 아이디어는 아예 부분수열을 build해가는 과정이다.

• index 포인터를 둬서 target수가 부분수열의 어느 위치에 들어갈지를 가리키게 한다.
• 순차적으로 주어진 값들을 방문하며 포인터가 가리키는 위치보다 한칸 전의 값과 비교해서 크면 포인터가 가리키는 위치에 해당 값을 넣는다.
• 만약 포인터가 가리키는 위치보다 한칸 전의 값과 비교했을 때 해당 값이 더 작다면 부분수열의 맨 앞수와 비교해서 작으면 맨 앞으로 넣는다.
• 부분수열의 맨 앞수보다는 큰 경우 부분수열 중간에 넣어주어야 한다는 뜻이므로 이분탐색으로 들어갈 위치를 찾아 넣어준다.

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int[] seq = new int[N];
		int[] LIS = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for(int i = 0; i < N; i++) {
			seq[i] = Integer.parseInt(st.nextToken());
		}
		
		LIS[0] = seq[0];
		int idx = 1;
 
		for(int i = 1; i < N; i++) {
			if(LIS[idx - 1] < seq[i]) {
				LIS[idx++] = seq[i];
			}
			else if(LIS[0] > seq[i]) {
				LIS[0] = seq[i];
			}
			else {
				int temp = Arrays.binarySearch(LIS, 0, idx, seq[i]);
				LIS[temp < 0 ? -(temp + 1) : temp] = seq[i];
			}
		}
		System.out.println(idx);
	}
}