최장 증가 부분 수열 (LIS)

LIS (Longest Increasing Subsequence)

최장 증가 부분 수열

→ 어떤 수열이 왼쪽에서 오른쪽으로 나열되어 있으면 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분 수열을 추출 하는 문제

1. LIS란?

주어진 순열에서 오름차순 을 유지하는 부분 수열 중 가장 긴 수열의 길이를 구하는 알고리즘

ex) 수열 = [10, 20, 10 ,30 ,20 ,50] 이 주어졌을때

가능한 증가 부분 수열은

• [10, 20, 30, 50] → 길이가 4
• [10, 20, 50] → 길이가 3
• [10, 30, 50] → 길이가 3

등등이 생성된다. 이럴 경우 정답이 4

2. 대표적인 풀이방법

• 풀이방법1 : DP
• 풀이방법2 : 이진 검색 활용

DP O(N^2) 풀이 - 기초적인 방법

• 아이디어 : dp[i] = i 번째 원소를 마지막으로 하는 LIS의 길이
• 점화식

dp[i] = max(dp[j]) + 1

java 코드

import java.util.Arrays;

public class DP {
    public static void main(String[] args) {

        int[] arr = { 10, 20, 10, 30, 20, 50};
        int n = arr.length;
        int[] dp = new int[n];

        Arrays.fill(dp, 1);

        int answer = 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[i] + 1);
                }
            }
            answer = Math.max(answer, dp[i]);
        }
    }
}

이분탐색 O(N log N) 풀이

• 핵심: LIS 의 길이만 구한다면 이분탐색을 활용
• 원리: LIS 배열을 유지하면서 새로운 원소가 들어올 때 크면 append 작거나 같으면 lower bound 위치에 대체( 길이는 안 줄어들고 나중에 더 긴 수열 가능성 유지)

동작 예시 : [10, 20, 10 ,30 ,20 ,50]

10 → [10]

20 → [10 ,20]

10 → [10, 20] / 10이 lower bound 위치를 대체

30 → [10, 20, 30]

20 → [10, 20, 30] → 20이 lower bound 위치 대체

50 → [10,20,30,50]

결과 길이 = 4

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {10,20,10,30,20,50};
        List<Integer> list = new ArrayList<>();

        for (int x : arr) {
            int pos = Collections.binarySearch(list, x);
            if (pos < 0) {
                pos =-(pos + 1);
            }

            if (pos == list.size()) {
                list.add(x);
            }else{
                list.set(pos, x);
            }
        }

        System.out.println(list.size());
    }
}

두 방법 비교

DP O($N^2$) → N ≤ 2000 에서 가능

O(N log N) → N ≤ 1,000,000 도 가능

응용문제

• LDS 감소 부분 수열
• 2차원 LIS
• LIS 복원하기 → 실제 수열 출력
• LBS → 증가 후 감소