최대 증가 수열(LIS) - DP

처음엔 무식하게 풀어본다. 이때 해당 문제가 최적 부분 구조를 만족한다는 것을 쉽게 알 수 있다. 예를 들어 임의의 위치에 있는 수 A를 LIS의 첫 숫자로 골랐다고 가정하면 A부터 시작한 LIS 개수는 A보다 뒤에 있고 큰 원소부터 시작한 LIS 개수(B) + 1이라는 것을 알 수 있다. B를 구할 때 이전에 선택한 수 A는 알 필요가 없다. 최적 부분 구조를 만족하므로 DP를 적용해 중복되는 부분 문제를 제거한다.

 

백준 11053번 가장 긴 증가하는 부분 수열 문제이다. 함수 f는 start_idx 위치의 수를 시작으로 하는 LIS 개수를 리턴한다. 함수 f를 호출 할 때마다 최대 n개의 부분 문제가 발생하고 함수 f를 n번 반복 호출하므로 O(n²)의 성능을 보인다.

import java.lang.*;
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[] number = new int[N];
        int[] dp = new int[N];

        st = new StringTokenizer(br.readLine()," ");
        for(int i=0; i<N; i++) {
            number[i] = Integer.parseInt(st.nextToken());
            dp[i] = -1;
        }

        int answer = 0;
        for(int i=0; i<number.length; i++) {
            answer = Math.max(answer, f(i,dp,number));
        }
        System.out.println(answer);
    }

    static int f(int start_idx, int[] dp ,int[] number) {
        if(dp[start_idx] != -1) return dp[start_idx];

        int answer = 1;
        for(int i=start_idx + 1; i<number.length; i++) {
            if(number[start_idx] < number[i])
                answer = Math.max(answer, f(i,dp,number) + 1);
        }
        dp[start_idx] = answer;
        return answer;
    }
}

main 문에서 n번 f 함수를 호출하는 것이 귀찮을 수 있다. 이때 문제를 약간 변형하면 이 코드를 없앨 수 있다. number[-1] 수가 존재하고 이 수는 -∞라고 가정한다. 따라서 문제 f(-1,dp,number)는 -∞ 을 시작으로 하는 LIS 개수를 리턴한다. dp[0]은 f(-1,dp,number)의 답을 메모이제이션 하므로 dp 배열의 개수가 하나 더 늘었다. answer을 구할 시 LIS 맨 앞의 -∞를 제거해야 되기에 -1한다.

import java.lang.*;
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[] number = new int[N];
        int[] dp = new int[N + 1];

        st = new StringTokenizer(br.readLine()," ");
        for(int i=0; i<N; i++) { number[i] = Integer.parseInt(st.nextToken()); }
        for(int i=0; i<N+1; i++) { dp[i] = -1; };

        int answer = 0;
        answer = f(-1,dp,number) - 1;
        System.out.println(answer);
    }

    static int f(int start_idx, int[] dp ,int[] number) {
        if(dp[start_idx + 1] != -1) return dp[start_idx + 1];

        int answer = 1;
        for(int i=start_idx + 1; i<number.length; i++) {
            if(start_idx == -1 || number[start_idx] < number[i])
                answer = Math.max(answer, f(i,dp,number) + 1);
        }
        dp[start_idx + 1] = answer;
        return answer;
    }
}