최대 증가 부분 수열

풀이

완전 탐색 알고리즘

우선 단순한 완전 탐색 알고리즘으로 구현해 봅시다. 완전 탐색 알고리즘으로 구현하려면 부분 문제를 정의해야 합니다. 이 문제에서 부분 문제는 수열의 특정 위치에서 시작하는 최대 증가 부분 수열을 찾는 것입니다. 따라서 int lis(int start) 함수를 만들면 됩니다. 이 함수에 어디에서 시작할지 인자로 정하면 start 뒤에 있는 숫자 각각 수열에 넣을지 말지 선택해야 합니다. 물론 수열 $A$의 start위치에 있는 숫자보다 더 큰 숫자만 고려 대상입니다. 이 동작을 점화식으로 쓰면 다음과 같습니다.
$lis(start)=1+\max_{i=start +1}^{n}(lis(i))$ (단, A[start] < A[i]인 것만 고려함)
아래는 이 점화식을 구현한 코드입니다.

// 최장 증가 부분 수열의 길이를 반환하는 메소드
public static int lis(int start) {
    // 기저 사례: start가 수열의 맨 끝일 경우 1을 반환
    if (start == A.length - 1) return 1;
    // 완전 탐색
    int result = 1;
    for (int i = start + 1; i < n; i++) {
        if (A[start] < A[i]) {
            result = Math.max(result, lis(i) + 1);
        }
    }
    return result;
}

위 코드의 시간 복잡도는 $O(n^n)$입니다. 물론 점점 부분 문제의 개수가 줄어들고 조건에 맞지 않는 부분 문제는 제거하므로 훨씬 덜 걸리겠지만 그래도 $n$이 500이라면 시간 내에 풀기 힘든 알고리즘입니다.

메모이제이션

우리가 구현한 함수는 참조적 투명 함수입니다. 따라서 입력값에 따른 최적값을 저장하는 캐시를 만들어 메모이제이션을 구현할 수 있습니다. 입력값의 종류는 최대 N개 이므로 충분히 저장할 수 있는 양입니다.

시간 복잡도 분석

여기에서 소개한 메모이제이션을 시간 복잡도 분석할 때 주먹구구식으로 계산하는 방법을 사용하면 (존재하는 부분 문제의 수 = n) * (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수 = n) = $n^2$이므로 시간복잡도는 $O(n^2)$라는 것을 알 수 있습니다.

구현

import java.util.*;

public class Main {

    // 수열의 길이, 수열
    public static int n, A[], cache[];
    // 답
    public static int result = 0;

    public static void input(Scanner scanner) {
        n = scanner.nextInt();
        A = new int[n];
        cache = new int[n];
        for (int i = 0; i < n; i++) {
            A[i] = scanner.nextInt();
        }
    }

    public static void solve() {
        for (int i = 0; i < n; i++) {
            result = Math.max(result, lis(i));
        }
    }

    // 최장 증가 부분 수열의 길이를 반환하는 메소드
    public static int lis(int start) {
        // 메모이제이션
        if (cache[start] != 0) return cache[start];

        cache[start] = 1;
        for (int i = start + 1; i < n; i++) {
            if (A[start] < A[i]) {
                cache[start] = Math.max(cache[start], lis(i) + 1);
            }
        }
        return cache[start];
    }

    public static void output() {
        System.out.println(result);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        for (int i = 0; i < testCase; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

회고

위 코드를 -1을 입력해서 solve() 함수 안에 반복분을 없애는 방식으로 짤 수도 있습니다.

import java.util.*;

public class Main {

    // 수열의 길이, 수열
    public static int n, A[], cache[];
    // 답
    public static int result = 0;

    public static void input(Scanner scanner) {
        n = scanner.nextInt();
        A = new int[n];
        cache = new int[n + 1];
        for (int i = 0; i < n; i++) {
            A[i] = scanner.nextInt();
        }
    }

    public static void solve() {
        result = lis(-1);
    }

    // 최장 증가 부분 수열의 길이를 반환하는 메소드
    public static int lis(int start) {
        // 메모이제이션
        if (cache[start + 1] != 0) return cache[start + 1];

        cache[start + 1] = 1;
        for (int i = start + 1; i < n; i++) {
            if (start == -1 || A[start] < A[i]) {
                cache[start + 1] = Math.max(cache[start + 1], lis(i) + 1);
            }
        }
        return cache[start + 1];
    }

    public static void output() {
        System.out.println(result - 1);
    }

    public static void test() {
        for (int i = 0 ; i < n ;i++) {
            System.out.print(cache[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        for (int i = 0; i < testCase; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

이렇게 구현할 경우 $start$=-1이 주어질 수 있기 때문에 $cache[]$에 접근할 때 $cache[start]$ 대신 $cache[start + 1]$을 쓰는 것을 유의해야 합니다. $cache[]$의 크기도 $1$ 커졌습니다. 이제 $lis(-1)-1$을 결과로 쓰면 됩니다. $A[-1]$은 우리가 가상으로 추가한 입력 값이기 때문에 최종 반환 값에서 빼 줘야 합니다.