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

1. 개념 🌠

  최장 증가 부분 수열(LIS - Longest Increasing Subsequence)이란 임의의 수열로 만든 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 의미한다.

  '3 2 6 4 5 1'이 있다고 하자. 해당 수열의 부분 수열은

{3}, {2}, {6},...
{3, 2}, {2, 1},...
{2, 6, 4}, {2, 4, 5},...
{3, 2, 5, 1},...
{2, 6, 4, 5, 1},...
{3, 2, 6, 4, 5, 1}

등이 존재한다. 여기서 최장 증가 부분 수열은 {2, 4, 5}이며 그 길이는 3이 되게 된다.
  이번 글을 통해 최장 증가 부분 수열의 길이를 구하는 3가지 방법을 알아보자. 순서는 시간복잡도가 큰 것에서부터 작은 것으로 진행된다.

 

2. 방법 1 - O(2^N) 🌀

  첫 번째 방법은 위에서 설명한 것처럼 부분 수열을 이용하는 것이다. 주어진 수열에서 부분 수열을 모두 구해서 증가하는 부분 수열 중 가장 길이가 긴 것을 찾는 방식이다.
  시간복잡도는 O(2^N)인 지수 시간 복잡도를 가지게 된다.

 

3. 방법 2 - O(N^2) 🌟

  두 번째 방법은 DP를 이용하는 방법이다. 이 방법은 주어진 수열을 i번째까지만 고려하면서 최대증가 부분수열의 길이를 업데이트하는 방식이다.
  아래의 DP[i]는 (0 ~ i) 번째 원소들을 포함하는 수열에서의 최대증가 부분수열의 길이를 나타낸다.

만약 i < k이고, arr[i] < arr[k]이고, DP[i] + 1> DP[k] 라면 DP[k]는 DP[i] + 1로 업데이트해주어야 한다. 이는 'k번째까지 고려된 상황'에서 'k보다 앞선 i번째까지 고려된 상황에서의 최대증가 부분수열의 길이'보다 더 큰 최대증가 부분수열의 길이를 찾은 경우를 의미한다.

  즉, 수열의 길이를 증가하면서 최대증가 부분수열의 길이도 같이 업데이트해 주는 것이다. 아래의 코드를 이용하여 자세히 이해해 보자.

public static void main(String[] args) {
    int N = 6;
    int[] arr = new int[]{3, 2, 6, 4, 5, 1};
    int[] DP = new int[N];

    // 최대증가부분수열의 길이
    int maxLen = 0;

    // i번째까지만 고려하는 수열 만들기
    for(int i = 0; i < N; i++) {
        DP[i] = 1;

        for(int j = 0; j < i; j++) {

            // i번째의 값보다 작은 것(= 증가 부분 수열)들 중에서
            // 증가 부분 수열의 길이가 가장 긴 것으로 업데이트 하는 과정
            if((arr[j] < arr[i])
                    && (DP[i] < DP[j] + 1)) {
                DP[i] = DP[j] + 1;
            }
        }

        // 어느 지점에서 
        // 최장증가수열의 최대 길이를 포함하는지 바로 알 수 없기 때문에
        // 이렇게 계속 최장증가부분수열의 길이(maxLen)를 업데이트
        if(maxLen < DP[i]) {
            maxLen = DP[i];
        }
    }

    System.out.println(maxLen);
}

  해당 방법의 시간복잡도는 O(n ^ 2)이다.

 

4. 방법 3 - O(N logN) 🌌

  세 번째 방법은 DP를 이용한 두 번째 방법을 개선한 것이다. 
'8 2 4 3 6 11 7 10 14 5'라는 수열이 있다고 해보자. 수열의 앞부분부터 고려하면서 최대증가 부분수열을 만든다고 하면 아래처럼 만들 수 있다. (주어진 수열은 검은색 영역에 가로로, 해당 지점의 최대증가 부분수열은 세로로 나타나져 있다.)

  이는 매 순간 최대증가 부분수열을 최적화해 나간다고 할 수 있다. 여기서 말한 최적화는 최대증가 부분수열을 만들기 위해 이후의 상황을 고려하였을 때 주어진 상황에서 가장 적절한 최대증가 부분수열을 만드는 것이라고 할 수 있다.
  결국 순회를 할 때(=주어진 수열의 앞부분부터 고려하면서 진행할 때) 최적의 최대증가 부분수열을 만들어나가면 되는 것이다. 이는 아래의 코드처럼 이분탐색을 이용하여 만들 수 있다. 전체 시간복잡도는 O(N log N)이다.

public static void main(String[] args) {
    int N = 6;
    int[] arr = new int[]{3, 2, 6, 4, 5, 1};
    // 최적의 최대증가부분수열
    int[] bestSubsequence = new int[N];

    // 최대증가부분수열의 길이
    int maxLen = 0;
    for(int i = 0; i < N; i++) {
        // 이분 탐색을 이용하여 위치 찾기
        int pos = Arrays.binarySearch(bestSubsequence, 0, maxLen, arr[i]);

        // 이미 같은 값이 존재하는 경우(pos > 0)는 건너뛰기
        if(pos >= 0) {
            continue;
        }

        int posiblePos = Math.abs(pos) - 1;
        // 최적의 최대증가부분수열 업데이트
        bestSubsequence[posiblePos] = arr[i];

        // 맨 뒤에 추가한 경우
        if(posiblePos == maxLen) {
            maxLen++;
        }
    }

    System.out.println(maxLen);
}

  위에서 나오는 Arrays.binarySearch의 리턴값은 아래의 그림을 통해 빠르게 이해할 수 있다.

  간단하게 생각하면, 찾고자 하는 값이 있으면 해당 인덱스를 리턴해주고, 없다면 있어야 하는 위치의 소수점 자리에 -를 붙여서 리턴해주는 것이다.

 

  이상으로 최장증가 부분수열(LIS)을 구하는 3가지 방법에 대해서 알아보았다. 각각의 방법의 시간복잡도는 O(2^N), O(N^2), O(N logN)이라는 점을 기억해 두자.

 

해당 글은
큰돌 님의 '최대증가부분수열, LIS, Longest Increase Sequence',
bang2001 님의 'Arrays.binarySearch() 메소드'
를 참고하였습니다.