최장 증가 수열 (Longest Increasing Sequence)

최장 증가 수열(LIS)은 주어진 배열에서 가장 긴 증가하는 부분 수열을 찾는 문제입니다. 예를 들어, [7, 2, 3, 8, 4, 5]라는 배열이 있을 때, 이 배열에서 [2, 3, 4, 5]가 최장 증가 수열이 되며, 답은 4가 됩니다.

구현 방법과 시간 복잡도

1. 동적 계획법 (DP)

동적 계획법을 사용하여 LIS 문제를 해결할 수 있습니다. 이 방법은 시간 복잡도가 O(N^2)이지만, 배열의 크기가 작은 경우에 적합합니다.

2. 이진 탐색을 활용한 Lower Bound

이 방법은 LIS를 O(NlogN)의 시간 복잡도로 해결할 수 있습니다. 배열의 길이가 매우 클 때, 예를 들어 최대 10만인 경우, 이 방법을 사용하는 것이 효율적입니다.

DP를 활용한 코드 예제

아래 코드는 동적 계획법을 사용하여 최장 증가 수열을 찾는 방법을 보여줍니다.

public class LIS_DP {
    public static void main(String[] args) {
        int[] arr = {7, 2, 3, 8, 4, 5};
        int[] dp = new int[arr.length]; // LIS 저장 배열
        int max = 0;

        for (int i = 0; i < arr.length; i++) {
            dp[i] = 1; // 최소한 자기 자신 하나는 포함되므로 1로 초기화
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }

        System.out.println("최장 증가 수열의 길이: " + max);
    }
}

동작 설명

• dp[i]는 arr[i]를 마지막 원소로 하는 증가 수열의 최대 길이를 나타냅니다.
• 이중 반복문을 통해 i 이전의 모든 원소를 확인하여, arr[i]가 arr[j]보다 큰 경우 dp[j] + 1을 dp[i]에 갱신합니다.
• max 변수는 전체 dp 배열 중 가장 큰 값을 기록하여 최종적으로 출력합니다.

출력 결과

최장 증가 수열의 길이: 4

So...

최장 증가 수열(LIS) 문제는 동적 계획법과 이진 탐색을 활용한 두 가지 접근 방식이 있습니다. DP는 간단하지만 시간 복잡도가 O(N^2)로 큰 반면, Lower Bound를 사용한 이진 탐색 방법은 O(NlogN)의 시간 복잡도로 더 효율적입니다. 문제의 크기와 요구 사항에 따라 적절한 방법을 선택하여 사용하면 됩니다.