[Algorithm] 11053 - 가장 긴 증가하는 부분 수열(JAVA)

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

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

---

알고리즘 

LIS(Longest Increasing Subsequence) 문제이다. 원소가 N개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 그 길이가 최대인 부분 수열을 최장 증가 부분 부분 수열(LIS)라고 한다. {10, 20, 10, 30, 20, 50 } 의 LIS 는 10,20,30,50이 최장이므로 4가 된다. LIS는 이분 탐색을 다루면 시간복잡도가 O(NlogN)을 가질 수 있으며, DP를 사용해도 O(N^2)이 나올 수 있다. 

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

dp[0] = {10}, dp[1] = {10, 20}, dp[2] = {10}, dp[3] = {10, 20, 30}, dp[4] = {10, 20}, dp[5] = {10, 20, 30, 50} 와 같이 만들면된다. DP 알고리즘에는 Top-Down(재귀), Bottom-Up(반복문) 방식이 있다. 

Top-Down 방식 (재귀)

private static int LIS(int N) {
        if (dp[N] == null) {
            // 수열의 최소 길이는 1
            dp[N] = 1;
            // 이전 노드를 탐색하며 현재 원소보다 값이 작으면서 최댓값을 탐색
            for (int i = N - 1; i >= 0; i--) {
                if (arr[i] < arr[N]) {
                    dp[N] = Math.max(dp[N], dp[i]+1);
                }
            }
        }
        return dp[N];
    }

DP 배열을 Integer(객체 배열)로 생성하여 초기값을 null로 만든다. 입력 받은 N의 값이 null 즉, 탐색하지 않은 원소이면 1로 만든다. 최소 길이는 1이기 때문. N 이전의 노드를 탐색해보며 현재 arr[N] 보다 작은 arr[i] 중 dp[i]가 가장 큰 원소를 찾아 dp[N]에 dp[i]+1을 넣어준 다음 dp[N]을 반환한다.

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

public class Main {
    static int[] arr;
    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());
        dp = new Integer[N];
        arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
        int result = 0;
        for (int i=0; i<N; i++) result = Math.max(result, LIS(i));
        System.out.println(result);
    }

    private static int LIS(int N) {
        if (dp[N] == null) {
            dp[N] = 1;
            for (int i = N - 1; i >= 0; i--) {
                if (arr[i] < arr[N]) {
                    dp[N] = Math.max(dp[N], dp[i]+1);
                }
            }
        }
        return dp[N];
    }
}

Bottom-Up (반복문)

for (int i=0; i<N; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i] && dp[i] < dp[j] + 1) dp[i] = dp[j] +1;
            }
        }

TopDown 방식의 재귀 방법을 for문으로 풀어낸 방법이다. 

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

public class Main {
    static int[] arr;
    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());
        dp = new Integer[N];
        arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
        Arrays.fill(dp, 1);

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