LIS, LDS (최장 증가 부분 수열, 최장 감소 부분 수열)

배씌 2025. 4. 5. 16:23

LIS (Longest Increasing Subsequence) 란?

LIS(최장 증가 부분 수열) 말 그대로, 수열에서 일부 원소들을 증가하는 순서대로 선택했을 때, 얻을 수 있는 가장 긴 부분 수열을 말한다.

예를 들어,

{10, 20, 10, 30, 20, 50}

// -> LIS : 10 -> 20 -> 30 -> 50 
// 길이 : 4

LIS와 LDS 역시 일반적으로 DP를 사용하여 해결한다. 그러나, DP를 사용했을 때의 시간 복잡도는 O(n^2)가 되므로, 시간 초과가 발생하는 문제에서는 이분 탐색 방법을 사용하자. 이분 탐색 방법은 O(n log n)의 시간 복잡도를 보장한다.

자세한 설명과 동작 방식은 아래 코드를 보며 설명하겠다.

LIS 기본 알고리즘 (DP)

int[] dp = new int[N];
Arrays.fill(dp, 1);

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

dp 배열을 우선 1로 초기화 시키는 이유는, 최소 원소 길이는 자기 자신이기 때문이다.

이후, arr[i] 의 원소와 그 이전 원소들의 값을 하나씩 비교하며, 자신보다 작은 값들이 있을 경우, 하나씩 더해준다. 반복문이 종료되었을 때, dp 배열의 원소 중 가장 큰 값이 LIS가 된다.

보다시피 DP의 경우, O(n^2) 의 시간복잡도를 가지기에, 시간초과가 발생하는 문제에서는 이분 탐색 방법을 고려하자.

{10, 20, 10, 30, 20, 50}

위의 예시를 코드에 적용 시켜, 각 단계별 dp 배열의 상태를 살펴보겠다.

i=0: [1]  
i=1: [1, 2] → 10 < 20  
i=2: [1, 2, 1]  
i=3: [1, 2, 1, 3] → 10 < 30 or 20 < 30  
i=4: [1, 2, 1, 3, 2]  
i=5: [1, 2, 1, 3, 3, 4]

LIS 이분 탐색 방법

이분 탐색을 활용하면, lower_bound 방식으로 O(n log n)의 시간복잡도를 가지고도 문제를 해결할 수 있다. 다만, 이는 실제 수열이 아니라 길이만 구하므로 이점 유의하자.

int[] arr = {10, 20, 10, 30, 20, 50};

List<Integer> list = new ArrayList<>();
for(int num : arr) {
    if(list.isEmpty() || num > list.get(list.size() - 1)) {
        list.add(num);
    } else {
        // num이 들어갈 자리를 BinarySearch를 통해 찾아서 교체
        int idx = Collections.binarySearch(list, num);
        if(idx < 0) idx = -(idx + 1);
        list.set(idx, num);
    }
}
System.out.println(list.size());

위 코드 처럼, 이분 탐색에서 사용되는 list는 실제 수열이 아니다. LIS의 길이만을 찾기 위한 가짜 수열이므로, 헷갈리지 말자.

list.get(i) 는 길이가 i+1인 증가 수열에서, '가장 작은 마지막 원소'를 의미한다.

새로운 숫자가 왔을 때,

- 마지막 원소보다 크면 -> LIS 연장 가능

- 마지막 원소보다 작으면 -> 마지막 원소에 해당 값 삽입

이때, 어떻게 탐색하려는 값을 list에 삽입할 수 있는가? 이는 binarySearch의 특징 때문이다.

int idx = Collections.binarySearch(list, num);

위의 코드에서 binarySearch는 아래와 같은 값을 반환한다.

탐색 성공(idx >= 0) -> num이 존재하는 위치 그대로 반환
탐색 실패(idx < 0) -> -(삽입 위치) -1 을 반환

아래에서 예시로 설명해보겠다.

List<Integer> list = List.of(10, 20);
int idx = Collections.binarySearch(list, 15);

현재 리스트의 상태는 [10, 20] 이다. 이때 탐색하려는 15는 현재 리스트에 없지만, 해당 값이 들어가야 하는 위치(삽입 위치)는 1인 것을 알 수 있다. 따라서 반환 값은

-(삽입 위치) -1 = -(1) - 1 = -2

즉, -2가 반환된 값을 아래 문장을 통해 실제 삽입 위치로 변환하게 된다.

if (idx < 0) {
    idx = -(idx + 1);  // 삽입 위치로 변환
}

결론적으로, 리스트의 상태는

[10, 15] 로 변경되어, 이어지는 증가 부분을 구할 수 있다.

LDS (Longest Decreasing Subsequence)

LDS의 경우 LIS에서 필요한 부분의 부등호만 변경해주면 원리는 동일하다.

int[] dp = new int[N];
Arrays.fill(dp, 1);

for (int i = 1; i < N; i++) {
    for (int j = 0; j < i; j++) {
        if (arr[j] > arr[i]) {
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
}