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

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

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

 

1. 문제

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

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

---

2. 입력

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

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

6
10 20 10 30 20 50

---

3. 출력

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

4

---

4. 풀이

DP 문제인 만큼 이 문제 또한 Top-Down과 Bottom-Up 두 방식으로 풀이를 진행하였다.

 

<Top-Down 방식>

 

Lis함수는 v번째 원소까지의 부분배열 중에 가장 긴 길이를 측정해서 return해주는 함수이다. 이 점을 이용해서 재귀를 통해 현 위치를 포함해서 이전의 부분배열들 중 가장 긴 값을 dp에 저장하고 dp 배열에서 가장 긴 값을 결과 값에 넣는다. 

 

<Bottom-Up 방식>

 

역시나 이중 for문을 활용하여 초기 값을 1로 할당해주고나서 현 위치의 이전들 값 중에서 긴 값을 찾아냈다.

 

---

5. 소스코드

<Top-Down 방식>

 

import java.io.*;
import java.util.*;
 
public class Main {
	static Integer [] dp;
    static int [] arr;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
        arr = new int [N];
        
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=0; i<N; i++) arr[i] = Integer.parseInt(st.nextToken());

        dp = new Integer [N];

        for(int i=0; i<N; i++){
            Lis(i);
        }
        int result = Integer.MIN_VALUE;

        for(int i=0; i<N; i++) result = Math.max(result, dp[i]);

        System.out.println(result);
    }

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

<Bottom-Up 방식>

 

import java.io.*;
import java.util.*;
 
public class Main {
	static Integer [] dp;
    static int [] arr;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
        arr = new int [N];
        
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=0; i<N; i++) arr[i] = Integer.parseInt(st.nextToken());

        dp = new Integer [N];

        int result = Integer.MIN_VALUE;
        dp[0] = 1;
        for(int i=0; i<N; i++){
            dp[i] = 1;
            for(int j=0; j<i; j++){
                if(arr[j]<arr[i]) dp[i] = (int)Math.max(dp[i], dp[j]+1);
            }
            result = (int)Math.max(result, dp[i]);
        }
        System.out.println(result);
    }
}

---

6. 배운 것

 이 문제를 풀며 이제서야 DP의 Top-Down 방식과 Bottom-Up 방식의 큰 차이를 몇가지 익혀지는 것 같다.

먼저 크게는, TD방식은 재귀를, BU방식은 이중 for문을 활용한다는 점이 먼저 와닿았다.

 

 추가적으로, TD방식은 재귀 알고리즘을 쓰다보니 초기에 재귀에 들어가는 매개변수는 입력받은 가장 긴 길이이고 이 값을 계산하기 위해 재귀를 통해 결국 1까지가서 그 값을 활용해서 점차 올라와 가장 긴 길이의 재귀함수 리턴값을 받아내는 방식이었다.

 

 반면, BU방식은 처음부터 초기값을 설정해두는 것은 TD방식과 같았으나 작은 부분부터 해당 값들을 구하고 점차 길이를 늘려가서 최종적으로 전체 배열에 대한 값을 찾아내는 방식이었다.

 

 이 두 방식의 차이를 확실히 인지해두고 그 모양새를 아예 암기해둔다면 앞으로 DP문제들을 접근할 때 매크로를 쓰듯이 코드를 구현해낼 수 있을 것 같다.