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

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

알고리즘 [접근 방법]

보통 이런 문제를 최장 증가 부분 수열(LIS)라고 한다. 말 그래도 주어진 수열에서 오름차 순으로 구성 가능한 원소들을 선택하여 최대 길이를 찾아내는 것이다. 잘 활용하면 O(N log N)의 시간 복잡도를 갖는다.

 

예제를 보자면 위 수열은 {10, 20, 10, 30, 20, 50} 이다. 이를 seq라고 하고, DP[]배열에 메모이제이션을 한다.

먼저 seq[0] = 10에 대한 수열을 찾아보자면 seq[0]보다 이전 값은 없으므로 10 자체 하나밖에 존재하지 않으므로 DP[0] = 1이된다. 그 다음 seq[1] = 20에 대한 수열을 찾아보면 seq[0] = 10으로 20보다 작기 떄문에 {10,20}이라는 부분 수열이 되고, 길이는 2로 DP[1] = 2가 되는 것이다. seq[2] = 10의 경우 이전 값들 중 작은게 없으므로 {10} 하나만 되므로 DP[2] = 1이되고 이런식으로 진행하는 것이다.

즉 각 dp[] 의 길이들은 다음 부분 수열을 의미하는 것이다.

 

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

 

구현하는 방법은 탐색하려는 인덱스(위치)에 대해서 이전 위치들을 찾아나가면서 해당값보다 작을 경우 재귀호출을 통해 탐색해나가면 된다.

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];
}

위 코드를 보며 이해해보자면,

 

먼저 n번째 값에 대해 이전에 탐색한 결과물이 있는지를 검사한다.

만약 없다면 탐색하지 않았다는 의미이므로 DP[N]을 1로 초기화하는 것이다. 이유는 모든 부분수열의 길이는 '최소한 1이상'이기 때문이다.

 

그리고 난 뒤, N-1 부터 0까지 N보다 작은 노드들을 탐색하면서 해당 노드의 값이 N번째 값보다 작은 경우를 찾는 것이다. 위 예시대로라면 N=4을 탐색하고자 할 때, 3~0까지 탐색하면서 작은 값들이 존재하는 경우는 seq[2] = 10 과 seq[0] = 10 밖에 없다. 즉, 반복문 i는 2에서 한번 재귀탐색을 시작하고, 0에서 재귀탐색을 시작하는 것이다.

 

i=2에서 현재 탐색하고자 하는 값 DP[4]와 LIS(2) + 1 재귀호출한 값 중 큰 값을 DP[4]에 갱신시키는 것이다. 여기서 당연히 +1을 하는 이유는 DP[N]이 이전 부분에 N번째 원소가 추가되었다는 의미이기 때문이다.

 

LIS(2) 재귀호출을 하면 DP[2]은 아직 탐색하지 않았을 경우 DP[2] = 1로 초기화되고, 또한 0~1까지 중 작은 값들을 찾아낸다. 이 때 이 부분에서 seq[2] = 10보다 작은 값은 없으므로 DP[N] = 1이 반환된다.

 

다시 돌아와 DP[4]와 LIS(2) + 1중, 큰 값은 LIS(2) + 1 (= 부분수열 {10, 20}), 즉 2이기 때문에 DP[4]는 2로 갱신된다. 그리고 반복문을 마저 탐색하면 i=0일 때 seq[0] < seq[4]를 만족하므로 재귀탐색을 하게 되는데 마찬가지로 LIS(0) 또한 1이므로 최대 길이가 2가 된다.

---

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가 된다.
		}
	}
}

반복문으로 구현할 수 있다. 방식은 이중반복문으로 0 ~ N-1 까지 각 원소보다 큰 값들을 카운팅해주는 것이다.

---

풀이 및 코드

- 방법 1 : [Scanner + Top-Down]

import java.util.Scanner;
 
public class Main {
	
	static int[] seq;
	static Integer[] dp;
	
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		seq = new int[N];
		dp = new Integer[N];
		
		
		for(int i = 0; i < N; i++) {
			seq[i] = in.nextInt();
		}
		
		// 0 ~ N-1 까지 모든 부분수열 탐색 
		for(int i = 0; i < N; i++) {
			LIS(i);
		}
		
		int max = dp[0];
		// 최댓값 찾기 
		for(int i = 1; i < N; i++) {
			max = Math.max(max, dp[i]);
		}
		System.out.println(max);
	}
	
	
	static int LIS(int N) {
		
		// 만약 탐색하지 않던 위치의 경우 
		if(dp[N] == null) {
			dp[N] = 1;	// 1로 초기화 
			
			// N-1 부터 0까지중 N보다 작은 값들을 찾으면서 재귀호출. 
			for(int i = N - 1; i >= 0; i--) {
				if(seq[i] < seq[N]) {
					dp[N] = Math.max(dp[N], LIS(i) + 1);
				}
			}
		}
		return dp[N];
	}
}

main 에서 LIS() 을 0~ N-1 까지 모든 값에 대하여 반드시 탐색해야 한다. 그래야 각각의 원소에 대한 부분 증가 수열을 모두 구할 수가 있다.

- 방법 2 : [Scanner + Bottom-Up]

import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		int[] seq = new int[N];
		int[] dp = new int[N];
		
		for(int i = 0; i < N; i++) {
			seq[i] = in.nextInt();
		}
		
		// dp
		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가 된다.
				}
			}
		}
		
		// 최댓값(최대 길이) 탐색 
		int max = -1;
		for(int i = 0; i < N; i++) {
			max = dp[i] > max ? dp[i] : max;
		}
		System.out.println(max);
		
	}
 
}