[백준알고리즘-JAVA]11053번 풀이(가장 긴 증가하는 부분 수열) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 11053번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 11053 (가장 긴 증가하는 부분 수열)

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 30, 50}이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

입력 예시

6
10 20 10 30 20 50

출력 예시

4

성공 코드

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

public class Main {

	static int N ;
	static Integer[] dp;
	static int[] arr;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		arr = new int[N];
		dp = new Integer[N];
		
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i = 0 ; i < N; i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		for(int i = 0; i < N; i++) {
			plus(i);
		}
		
		int max = 1;
		
		for(int i = 1; i < N; i++) {
			max = Math.max(max, dp[i]);
		}
		
		System.out.println(max);
}
	public static int plus(int d) {

		if(dp[d]==null) {
			dp[d]=1;
			
			for(int i = d-1 ; i >= 0 ; i--) {
				if(arr[d]>arr[i])
					dp[d]=Math.max(dp[d], plus(i)+1);
			}
		}
		return dp[d];
	}
}

가장 긴 증가하는 부분 수열 해당 알고리즘을 풀이하면서 결국 해결하지 못하여 다른 분의 코드를 참고해서 이해하는 형식으로 진행하였습니다.

 

동적계획법은 어떻게 풀이할지 생각하는 게 정말 어려웠습니다. 경우의 수를 다 파악하여 원하는 결과를 도출해야 되기 때문이죠.

 

동적 계획법에서 중요한 점은 어떻게 경우의 수를 다 파악하냐가 가장 중요한 점입니다.

 

이번 알고리즘에서 제가 생각하는 핵심은 어떻게 경우의 수를 다 파악하여 최댓값을 찾아내냐입니다. 이를 이해하기 위해서는 우선 큰 틀을 잡아놓고 시작해야 됩니다. STEP을 따라가 보도록 하죠

---

알고리즘 흐름도

 입력 받기 -> 반복 재귀 돌리기 -> 재귀를 통해 최대 부분 수열 갯수 파악하기 (dp 채우기) -> 반복문으로 dp 최댓값 찾기 -> 출력하기

---

STEP1 문제 이해하기

가장 긴 증가하는 부분 수열을 풀기 위해서는 어떻한 방식으로 접근해야 될지 생각해야 합니다.

 

입력 예시로 10 20 10 30 20 50 이렇게가 있죠 앞에 가장이라는 단어를 빼고 증가하는 부분 수열을 생각해 보도록 하죠

10 20 30 50

10 20 30

10 20

20 30 50

20 30

30 50

이런식으로 여러 가지 경우의 수가 나오게 되죠. 이중에 저희는 최댓값을 찾아야 합니다. 그렇다면 모든 경우의 수를 찾아야 합니다. 

 

만약 입력 예시가

10 20 100 30 40 50

이라고 가정한다면

 

중간에 가장 큰 값인 100이 있지만 가장 긴 부분 수열은

10 20 30 40 50 이기 때문이죠

 

이를 꼭 기억하고 다음 STEP으로 넘어가 보도록 하죠

---

STEP2 dp설정하기

 동적 계획법에서 정답이 되는 DP를 설정해야 합니다. 기본적으로 입력받은 크기만큼으로 선언해 줍니다.

dp = new Integer[N];

여기서 INT가 아닌 INTEGER로 선언한 이유는 메모 이제이 션 기법을 사용하기 위해서 기본값이 NULL인 INTEGER을 사용한답니다.

 

또한 여기서 꼭 집고 넘어가야 하는 점 DP가 의미하는 것은 무엇인지 꼭 기억해야 합니다.

DP에 저장되는 값은 해당 인덱스에 있는 숫자가 가질 수 있는 최대의 부분 수열입니다.

 

즉 DP [0]은 ARR [0] 이 가질 수 있는 가장 큰 부분 수열의 개수입니다. 표로 정리해서 보자면

arr	10	20	10	30	20	50
dp	1	2	1	3	2	4

이런 식으로 dp에 저장이 되다는 점을 꼭 상기하셔야 합니다. dp에 무엇을 넣어야 할지 모른다면 다음 재귀를 구현하는데 이해하기 어렵죠

---

STEP 3 재귀 구현하기

이번 재귀의 핵심은 바로 반복!

왜냐, 바로 모든 경우의 수를 따져야 하기 때문이죠. 주어진 입력과 다르게 중간에 엄청 큰 수가 있을 수도 있기 때문이죠

public static int plus(int d) {

		if(dp[d]==null) {
			dp[d]=1;
			
			for(int i = d-1 ; i >= 0 ; i--) {
				if(arr[d]>arr[i])
					dp[d]=Math.max(dp[d], plus(i)+1);
			}
		}
		return dp[d];
	}

 첫 번째 if문 : 메모이제이션을 활용하기 위한 조건 (null은 재귀를 하지 않았으니 값을 구하라는 의미

 

dp [d]=1; : 해당 코드는 dp를 초기화시켜주기 위한 과정 기본적으로 모든 값들은 자기 자신을 포함하기 때문에 아무리 적어도 1의 값을 가질 수 있기 때문입니다.

(해당 초기화를 하지 않을 시 null 오류가 나게 됩니다.)

 

for문 : 모든 경우의 수를 탐색하기 위한 반복문

 

두 번째 if문 : 값이 크다면, 이전에 계산했던 수열의 길이와 비교하여 더 긴 값을 dp에 넣어주는 코드

 

자 이렇게만 설명하면 이해하지 못하실 수 있습니다.

언제나 그렇듯이 입력 예시를 따라가며 다시 한번 이해를 도와드리겠습니다.

 

arr	10	20	10	30	20	50
dp	null	null	null	null	null	null

입력이 이런 식으로 들어와 있게 됩니다.

 

 - 재귀 인자로 0을 넣어준다.

 - 첫 번째 if문에 거린다. 

 - dp [0]에 1을 넣는다.

 - for문 조건을 만족하지 못하여 for문을 통과한다 dp[0] = 1을 반환한다.

arr	10	20	10	30	20	50
dp	1	null	null	null	null	null

 - 재귀 인자로 1을 넣어준다.

 - 첫 번째 if문에 거린다. 

 - dp [1]에 1을 넣는다.

 - for문 수행한다. (int i = 0)

 - arr [1] > arr [0]을 만족함으로 for문안의 if문을 수행한다.

 - dp [1] = Math.max(dp[1],plus(1)+1)을 비교한다. (dp[1]=1 // plus(1)+1 = dp[0]+1 = 1 + 1 = 2)

 - dp[1] = 2를 넣어준다.

arr	10	20	10	30	20	50
dp	1	2	null	null	null	null

 

이런 식으로 쭉 끝까지 재귀 인자로 0 ~ 5까지 넣어준다면 dp에는 각 인덱스에 맞는 부분 수열의 최대 개수를 담고 있게 됩니다.

---

이런 식으로 구해진 dp를 for문을 통해 최댓값을 뽑아내면 끝!

int max = 1;
		
		for(int i = 1; i < N; i++) {
			max = Math.max(max, dp[i]);
		}
		
		System.out.println(max);

 

 

어떻게 보면 굉장히 쉬운 알고리즘이지만, 동적 계획법을 자주 풀어보아야 쉽게 풀 수 있던 문제였습니다.