[백준] 11053번 : 가장 긴 증가하는 부분 수열

글 작성자: ST_

www.acmicpc.net/problem/11053

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

(제목이 꽤 길다...)

문제

이전 포도주 시식 또는 계단오르기 문제를 해결했다면 오히려 쉽게 접근 할 수 있는 문제다.

알고리즘 [접근 방법]

앞서 말했듯 포도주 시식, 계단오르기 같은 문제랑 같은 계열의 문제다.

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

단 여기서 설명 할 것은 시간복잡도가 O(N²) 알고리즘이다. 이유는 일단 이분탐색을 알아야 하는데, 백준의 카테고리별 문제들은 난이도가 점진적으로 상승하는 구성이고, 이분탐색은 그 뒤에 나온다. 즉, 카테고리를 다루지 않았기 때문에 이 부분은 나중에 다룰 일이 생긴다.

DP로 구현해도 N²인가요? 라고 묻는다면 대답은 YES.

다만 혹여 모르니 마지막 부분에 이분탐색을 이용한 코드도 보여주겠다. (단 설명은 안하겠다.)

한 번 예제를 토대로 뜯어보자. 위 예제의 수열은 {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

그러면 이를 어떻게 알고리즘으로 풀어내야 할까? 물론 Top-Down(재귀)방식이 있고, Bottom-Up(반복문) 방식이 있으니 먼저 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];
}

위 코드를 자세히 보며 이해해보자.

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

이와 같은 원리로 동작하면 된다.

두 번째로는 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가 된다.
		}
	}
}

눈치가 조금 빠른 분들은 알겠지만 위 재귀 방법은 바로 두 번째 for문에 대한 원리를 재귀로 재구현한 내용인 것이다.

그럼 전체 코드를 보도록 하자.

4가지 방법을 사용하여 풀이한다.

이전 포스팅과 여타 다를 바 없이 아래와 같이 4가지 방법을 통해 성능을 비교하겠다.

1 . Scanner + Top-Down

2. BufferedReader + Top-Down

3 . Scanner + Bottom-Up

4. BufferedReader + Bottom-Up

풀이

- 방법 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 : [BufferedReader + Top-Down]

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

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

public class Main {
	
	static int[] seq;
	static Integer[] dp;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		seq = new int[N];
		dp = new Integer[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for(int i = 0; i < N; i++) {
			seq[i] = Integer.parseInt(st.nextToken());
		}
		
		// 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];
	}
}

이제는 아마 여러분들도 BufferedReader을 쓰는데 익숙해하시지 않을까...

- 방법 3 : [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);
		
	}

}

어쩌면 여러분이 보시기에는 이게 더 익숙하고 이해하는데 더 편하지 않을까 생각이 든다. 원래 추상한 뒤 구체적으로 설계하는게 쉬운 것은 아니니.. 어쩌면 그렇게 배워왔기 때문에 작은 것부터 일단 풀고보려는 습성도 한 몫 하지 않을까..?(뇌피셜)

- 방법 4 : [BufferedReader + Bottom-Up]

입력 방법만 Scanner 대신 BufferedReader 을 사용한 풀이방식이다.

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

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[] dp = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		
		for(int i = 0; i < N; i++) {
			seq[i] = Integer.parseInt(st.nextToken());
		}
		
		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);
		
	}

}

성능

채점 번호 : 22247204 - 방법 4 : BufferedReader + Bottom-Up

채점 번호 : 22247197 - 방법 3 : Scanner + Bottom-Up

채점 번호 : 22247188 - 방법 2 : BufferedReader + Top-Down

채점 번호 : 22247185 - 방법 1 : Scanner + Top-Down

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다. 그리고 알고리즘상 약간 차이가 나는데, 흠.. 유의미할 수도 아닐수도 있다는 말 밖엔,,, 그래도 동등한 처리 과정을 거친다면 재귀보다 반복문이 성능이 조금 더 빠른 것은 사실이다.

정리

이 문제는 그리 어렵지 않았을 것이다. 무엇보다 다음 문제를 위해 적어도 완벽하게 파악해야 한다는 점이다. 그러니 혹여 모르거나 이해가 안되는 부분이 있다면 댓글 남겨주시는대로 최대한 빠르게 답변드리도록 하겠다.

그리고 이분탐색을 통한 풀이법은 따로 채점은 안보여줬고 코드만 보여주겠다. 기회가 된다면 이에 대해 따로 포스팅을 하겠다.

[LIS O(NlogN) 풀이법]

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

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

또한 이런 풀이 뿐이 아닌 세그먼트 트리 등 다양하게 활용할 수 있다는 점을 알아두셨으면 한다. 언젠가는 다룰 내용들이니 맛보기라 생각하고 보자.

저작자표시 비영리 변경금지

'JAVA - 백준 [BAEK JOON] > 동적 계획법 1' 카테고리의 다른 글

[백준] 2565번 : 전깃줄 - JAVA [자바] (11)	2020.09.04
[백준] 11054번 : 가장 긴 바이토닉 부분 수열 - JAVA [자바] (8)	2020.09.04
[백준] 2156번 : 포도주 시식 - JAVA [자바] (20)	2020.08.31
[백준] 10844번 : 쉬운 계단 수 - JAVA [자바] (46)	2020.08.29
[백준] 1463번 : 1로 만들기 - JAVA [자바] (35)	2020.08.28

[백준] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA [자바]

'JAVA - 백준 [BAEK JOON] > 동적 계획법 1' 카테고리의 다른 글

댓글

이 글 공유하기

티스토리툴바

'JAVA - 백준 [BAEK JOON] > 동적 계획법 1' 카테고리의 다른 글

댓글

이 글 공유하기

다른 글

[백준] 2565번 : 전깃줄 - JAVA [자바]

[백준] 11054번 : 가장 긴 바이토닉 부분 수열 - JAVA [자바]

[백준] 2156번 : 포도주 시식 - JAVA [자바]

[백준] 10844번 : 쉬운 계단 수 - JAVA [자바]

티스토리툴바