최장 증가 수열 (LIS, Longest Increasing Subsquence)

최장 증가 수열, 정확히 최장 증가 부분 수열은 어떠한 수열에서 오름차순으로 증가하는 가장 긴 부분수열을 의미한다.

이 때, 부분 수열의 각 수는 서로 연속할 필요는 없다.

아래의 예시 수열을 보자.

 

위 수열에서 최장 증가 수열을 찾으면 아래와 같다.

 

그림에서 붉은 칸으로 칠해진 부분 수열 (1, 2, 3, 6, 7, 9) 는 전체 수열 중 오름차순으로 증가하는 가장 긴 부분수열이다.

이제 주어진 수열에서 LIS의 길이를 구하는 두 가지 방법을 알아보자.

다이나믹 프로그래밍을 이용한 방법 : O(N^2)

이러한 최장 증가 수열을 찾는 가장 단순한 방법은 완전 탐색일 것이다.

하지만 수열에 존재하는 수의 개수가 k개일 때, 1개 이상의 원소를 갖는 모든 부분수열의 가짓수는 2^k개이므로, 모든 부분수열을 확인해 이들이 오름차순으로 정렬되어 있는지 확인하는 것은 매우 비효율적이다.

따라서 우리는 다이나믹 프로그래밍을 통해 이를 구현할 수 있다.

수열의 한 원소에 대해, 그 원소에서 끝나는 최장 증가 수열을 생각해보자. 그 최장 증가 수열의 k를 제외한 모든 원소들은 반드시 k보다 작아야 할 것이다.

따라서 k의 앞 순서에 있는 모든 원소들 중 값이 k보다 작은 원소에 대해, 그 각각의 원소에서 끝나는 최장 증가 수열의 길이를 알고 있다면, k에서 끝나는 최장 증가 수열의 길이도 구할 수 있을 것이다.

위의 예시에서는 8 이전의 (1, 5, 4, 2, 3)까지의 수열 중 각각의 원소에서 끝나는 최장 증가 수열의 길이는 다음과 같다.

 - 1에서 끝나는 LIS 길이 : 1 (1)

 - 5에서 끝나는 LIS 길이 : 2 (1, 5)

 - 4에서 끝나는 LIS 길이 : 2 (1, 4)

 - 2에서 끝나는 LIS 길이 : 2 (1, 2)

 - 3에서 끝나는 LIS 길이 : 3 (1, 2, 3)

이들 중 가장 긴 (1, 2, 3)에 현재 수 8을 더한 (1, 2, 3, 8)이 8에서 끝나는 최장 증가 수열이 된다.

즉, 앞 순서의 모든 원소에서 끝나는 최장 증가 수열들의 길이 중 가장 긴 것을 골라 1을 더한 것이 곧 현재 수에서 끝나는 최장 증가 수열의 길이이다.

따라서 dp[i] = "i번째 인덱스에서 끝나는 최장 증가 수열의 길이"로 정의한다.

void LIS_DP() {
    for (int i = 0; i < n; i++) {
        dp[i] = 1;            //해당 원소에서 끝나는 LIS 길이의 최솟값. 즉, 자기 자신
        for (int j = 0; j < i; j++) {
            //i번째 이전의 모든 원소에 대해, 그 원소에서 끝나는 LIS의 길이를 확인한다.
            if (arr[i] > arr[j]) {
                //단, 이는 현재 수가 그 원소보다 클 때만 확인한다.
                dp[i] = max(dp[i], dp[j] + 1);        //dp[j] + 1 : 이전 원소에서 끝나는 LIS에 현재 수를 붙인 새 LIS 길이
            }
        }
    }
}

이분 탐색을 이용한 방법 : O(NlogN)

DP를 이용한 방법은 분명 완전 탐색에 비해 시간 복잡도 면에서 효율적이지만, 여전히 O(N^2)이라는 점이 발목을 잡는다. 

이 때, 이분 탐색(Binary Search)을 사용하면 시간 복잡도를 O(NlogN)으로 줄일 수 있다.

이 방법에서는 LIS를 기록하는 배열을 하나 더 두고, 원래 수열에서의 각 원소에 대해 LIS 배열 내에서의 위치를 찾는다.

 

 

 

 

 

 

 

 

그림의 아래 배열의 크기는 최대 6까지 갔었으므로, LIS의 길이는 6이 된다.

이 방법은 그림의 아래 배열을 LIS의 형태로 유지하기 위해, 기존 수열의 각 원소가 LIS에 들어갈 위치를 찾는 원리로 동작한다. 즉, 현재 원소를 아래 배열에 넣어 LIS를 유지하려고 할 때, 그 최적의 위치를 찾는 것이다.

int binary_search(vector<int> lis, int start, int end, int element) {
    //이분 탐색으로 lis 벡터 내에서 element의 위치를 반환
    //lis 벡터의 start - end 구간에서만 확인
    while (start < end) {
        int mid = (start + end) / 2;
        if (element > lis[mid]) start = mid + 1;
        else end = mid;
    }
    return end;
}
 
int LIS_BS() {
    int ret = 0;
    vector<int> lis;
    lis.push_back(arr[0]);
 
    for (int i = 1; i < n; i++) {
        //만약 lis 벡터의 마지막 수보다 i번째 수가 크다면, 그냥 뒤에 붙인다.
        if (arr[i] > lis.back()) {
            lis.push_back(arr[i]);
            ret = lis.size() - 1;
        }
        //i번째 수에 대해, lis 벡터 내에서 그 수의 위치를 찾는다.
        int pos = binary_search(lis, 0, ret, arr[i]);
        lis[pos] = arr[i];
    }
 
    return ret + 1;
}

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