최장 증가 부분수열 (LIS)

1. 개요

• 최장 증가 부분 수열(LIS)은 주어진 수열 내에서 순서를 유지하면서 선택할 수 있는 가장 긴 증가하는 부분 수열을 찾는 문제다.
• 가장 긴 증가하는 부분 수열의 길이를 찾는 것이 목적이며, 해당 수열 자체를 구하는 것이 목표일 수도 있다.

2. 특징

• 다이나믹 프로그래밍 활용: LIS는 다이나믹 프로그래밍을 사용하여 해결할 수 있는 대표적인 예제 중 하나이다. 이 방식은 문제를 재귀적으로 분할하고, 중복 계산을 피하기 위해 이전에 계산된 결과를 저장한다.
• 이진 탐색 활용: 이진 탐색을 통해 LIS의 길이를 더 효율적으로 구할 수 있다. 이 방법은 수열의 각 요소를 순차적으로 검토하면서, 현재까지의 LIS를 유지하는 데 필요한 위치를 빠르게 찾아 업데이트한다.
• 시간 복잡도: 다이나믹 프로그래밍 방식은 O(n^2)의 시간 복잡도를 가지며, 이진 탐색 방식은 O(n log n)으로 더 효율적이다.
• 공간 복잡도: 두 방식 모두 O(n)의 공간 복잡도를 가진다. 다이나믹 프로그래밍은 각 단계에서의 최대 길이를 저장하는 데 사용되는 배열을, 이진 탐색은 LIS를 구성하는 요소를 저장하는 데 사용되는 배열을 필요로 한다.

3. 코드

public class LISDynamicProgramming {
    public static int lisDP(int[] arr) {
        if (arr == null || arr.length == 0) return 0;
        int[] dp = new int[arr.length];
        int max = 0;

        for (int i = 0; i < arr.length; 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;
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 10, 30, 20, 50};
        System.out.println("LIS 길이: " + lisDP(arr));
    }
}

import java.util.Arrays;

public class LISBinarySearch {
    public static int lisBinarySearch(int[] arr) {
        int[] tailTable = new int[arr.length];
        int length = 0;

        for (int num : arr) {
            int i = Arrays.binarySearch(tailTable, 0, length, num);
            if (i < 0) i = -(i + 1);
            tailTable[i] = num;
            if (i == length) length++;
        }
        return length;
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 10, 30, 20, 50};
        System.out.println("LIS 길이: " + lisBinarySearch(arr));
    }
}