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

최장 증가 부분 수열(LIS, Longest Increasing Subsequence)

최장 증가 부분 수열(LIS, Longest Increasing Subsequence)은 주어진 수열에서 요소들이 증가하는 순서대로 선택되는 가장 긴 부분 수열을 말한다. 즉, 주어진 수열에서 원래 순서를 유지하면서 순서대로 증가하는 숫자들을 선택하여 만들 수 있는 가 장 긴부분 수열을 찾는 문제이다.

 

예를 들어 수열 {3, 1, 5, 2, 4}가 주어졌을 때, 이 수열의 최장 증가 부분 수열은 {1, 2, 4}가 된다. 이 부분 수열은 원래 수열의 순서를 유지하면서 각 요소가 증가하는 순서대로 선택되었기 때문에 최장 증가 수열 부분이라고 할 수 있다.

 

최장 증가 부분 수열은 다이나믹 프로그래밍(DP)와 이분탐색을 이용하여 효율적으로 해결할 수 있다. DP를 사용하면 시간복잡도는 O(n^2)이 발생하지만, 이분탐색으로 사용하면 O(n logn)으로 줄일 수 있다.

 

DP 접근

https://superohinsung.tistory.com/198

[Algorithm] 동적 계획법(Dynamic Programming)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 백준알고리즘 11053번 가장 긴 증가하는 부분 수열

public class Main {
    static int A;
    static int[] arr;
    static Integer[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        A = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        arr = new int[A];
        dp = new Integer[A];
        for (int i = 0; i < A; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < A; i++) {
            DP(i);
        }

        int max = dp[0];
        for (int i = 1; i < A; i++) {
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);

    }

    static int DP(int n) {
        if (dp[n] == null) {
            dp[n] = 1;

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

백준알고리즘에 LIS의 대표적인 문제의 풀이를 가져왔다.

 

위에 코드에서 보이는 것 처럼

• dp[n] = 1 : 각 원소는 자기 자신을 부분 수열로 삼을 수 있다. 이때는 길이가 1이다.
• for (int i = n - 1; i >= 0; i--) : 현재 원소를 가르키는 인덱스는 n이다. i는 n이전의 원소의 인덱스를 의미한다. 즉, 현재 인덱스의 값을 기준으로 이전에 등장한 원소의 값을 살펴본다.
• if (arr[i] < arr[n])  dp[n] = Math.max(dp[n], dp[i] + 1); : 현재 원소가 이전 원소보다 크다면(arr[i] < arr[n])를 만족하고 이전 원소를 포함하는 부분 수열의 길이보다 현재 원소를 포함하는 부분 수열의 길이가 작으면 Math.max(dp[n], dp[i] + 1) 을 만족한다면 현재 원소를 포함하는 부분 수열의 길이 d[n]를 업데이트 한다.

위 코드의 시간 복잡도를 살펴보면, O(N2)이다.
만약, N이 10만 이라면, 10억번의 연산(10초)을 해야 하므로, 시간초과가 발생할 수 있다.
이때는 다른 방법을 살펴볼 필요가 있다.

 

이분 탐색 접근

// 자바 코드
import java.util.ArrayList;

public class Main {

    public static int binarySearch(ArrayList<Integer> lis, int el) {
        int l = 0;
        int r = lis.size() - 1;

        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (lis.get(mid) == el) {
                return mid;
            } else if (lis.get(mid) < el) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return l;
    }

    public static int getLISLength(int[] arr) {
        ArrayList<Integer> lis = new ArrayList<>();
        lis.add(arr[0]);

        for (int i = 1; i < arr.length; i++) {
            int el = arr[i];
            if (lis.get(lis.size() - 1) < el) {
                lis.add(el);
            } else {
                int idx = binarySearch(lis, el);
                lis.set(idx, el);
            }
        }

        return lis.size();
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 10, 30, 20, 50};
        int lisLength = getLISLength(arr);
        System.out.println(lisLength); // 최장 증가 부분 수열의 길이 출력
    }
}

위에 코드에서 보이는 것 처럼

 

• binarySearch(ArrayList<Integer> lis, int el) : 현재 원소 el이 LIS 리스트의 어디 위치에 들어갈 수 있는지를 찾는 함수이다.
•  for (int i = 1; i < arr.length; i++) {
              int el = arr[i]; : 원소를 하나씩 순회한다.
• lis.get(mid) < el : 현재 원소 el이 LIS의 마지막 원소보다 크다면, 그냥 LIS의 끝에 el을 추가한다.
• int idx = binarySearch(lis, el) : 만약, LIS의 마지막 원소보다 작거나 같다면, el이 들어갈 수 있는 위치를 이진 탐색으로 찾는다.
• lis.set(idx, el);: 위에서 찾은 인덱스에 현재 원소 el을 넣는다.

이진 탐색은 일반적으로 시간 복잡도가 O(logN) 으로 알려져 있다.
그러므로, 길이가 n인 리스트를 순회하면서 이진 탐색으로 원소가 들어갈 위치를 찾으므로 총 시간 복잡도는 O(NlogN) 이다.

 

최장 감소 부분 수열(LDS, Longest Decreasing Subsequence)

최장 감소 부분 수열은(LDS, Longest Decreasing Subsequence) 주어진 수열에서 요소들이 감소하는 순선대로 선택되는 가장 긴 부분 수열을 말한다. 즉, 주어진 수열에서 원래 순서를 유지하면서 순서대로 감소하는 숫자들을 선택하여 만들 수 있는 가장 긴부분 수열을 찾는 문제이다.

 

예를들어, 수열 {5, 3, 8, 4, 2, 1, 7}이 주어졌을 때, 이 수열의 최장 감소 부분 수열은 {8, 4, 2, 1}이 된다. 이 부분 수열은 원래 수열의 순서를 유지하며 각 요소가 감소하는 순서대로 선택되었기 때문에 최장 감소 부분 수열이라고 할 수 있다.

 

LDS의 경우 LIS에서 필요 부분만 등호를 변경해주면 원리는 같다.

 

참고

https://chanhuiseok.github.io/posts/algo-49/

알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘

https://velog.io/@49crehbgr/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-LIS-LDS

[알고리즘/Algorithm] LIS, LDS