[백준] 가장 긴 증가하는 부분 수열 (!) (11053번 JAVA) / 400 - 다이나믹 프로그래밍 1

[백준] 400 - 다이나믹 프로그래밍 1 : 가장 긴 증가하는 부분 수열 (!) (11053번 JAVA)

---

최장 증가 부분 수열 이란...?

(LIS : Longest Increasing Subsequence)

 

: 어떤 임의의 수열이 주어질 때, 이 수열에서 볓개의 수들을 제거해서 부분수열을 만들 수 있다.

이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.

 

cf) 동적 계획법으로 해결하는 유명한 알고리즘 문제 (알아놓자!)

 

[접근 방법]

1. O(N^2) 의 시간복잡도를 가지는 방법

 

★ 배열 10 20 10 30 20 50이 주어진 경우

index = 0은 원소 10이 자리하고 있다. 10 하나만 존재 하므로,

이때, LIS의 길이는 1 이다.

 

index = 1은 원소 20이 자리하고 있다. 이 경우 앞선 인덱스에 존재한 모든 원소보다 큼으로,

어느 경우에도 20을 마지막으로 하여 부분 증가 수열을 만들 수 있다.

따라서 가장 큰 LIS의 길이인 1에 +1을 하여,

이때, LIS의 길이는 2 이다.

 

이와 같은 방식으로 "LIS의 길이" 부분을 채워 가면 된다.

 

즉, 이전의 원소들을 탐색하며, 자신보다 작은 원소 중 가장 큰 "LIS의 길이" 값에 +1을 한다.

(여기서 "LIS의 길이"의 최소 값은 1이다. => 본인 보다 작은 원소가 없다면 1이다.)

 

 

 

하나의 예를 더 들어보자.

★ 배열 24 32 19 14 27 56 72 66 94 40 이 주어진 경우

 

현재 INDEX = 4를 탐색하고 있다.

원소는 27이다. 27 보다 작은 수는 

INDEX = 0 의 원소 24,

INDEX = 2 의 원소 19,

INDEX = 3 의 원소 14 가 있다.

이 중 가장 큰 "LIS의 길이" 를 가지고 있는 것은

INDEX = 0 의 원소 24, INDEX = 2 의 원소 19, INDEX = 3 의 원소 14가 모두 1을 갖으므로,

INDEX = 4 의 원소 27은 "LIS의 길이"로 2을 갖는다.

 

완성된 표

 

---

[JAVA 코드 - Top - Down 방식]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main{

    public static int[] arr;

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 1 <= N <= 1000
        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());
        }

        bw.write(LIS(arr)+"\n");


        bw.flush();
        bw.close();
    }

    public static int LIS(int[] arr){
        // LIS의 길이 저장
        int[] D = new int[arr.length];

        int result = 0;

        for(int i=0; i<arr.length; i++){
            D[i] = 1;

            // INDEX = i 이전의 값 탐색
            for(int j=0; j<=i; j++){

                // 현재 원소보다 작음 and 현재 LIS의 길이 보다 큼 => 갱신
                if (arr[i] > arr[j] && D[j] + 1 > D[i]){
                    D[i] = D[j] + 1;
                }
            }

            if(D[i] > result){
                result = D[i];
            }
        }

        return result;
    }
}

 

 

[JAVA 코드 - Botton - Up 방식]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 수열 A의 크기 N (1 ≤ N ≤ 1,000)
        int N = Integer.parseInt(br.readLine());

        int[] A = new int[N+1];
        int[] DP = new int[N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<N+1; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }       

        for(int i=1; i<=N; i++){
            DP[i] = 1;

            for(int j=1; j<i; j++){

                if(A[j] < A[i] && DP[i] < DP[j] + 1){
                    DP[i] = DP[j] + 1;
                }
            }
        }

        // 가장 긴 증가하는 부분 수열 길이 구하기

        // 삼항 연산자 활용
        int max_length = -1; 
        for(int i=1; i<=N; i++){
            max_length = DP[i] > max_length ? DP[i] : max_length;
        }

        bw.write(max_length + "\n");
        bw.flush();
        bw.close();
    }
}