동적 계획법 [DP] - [Longest Increasing Subsequence]

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

부분수열(subsequence)은 하나 이상 수를 지우거나 심지어 지우지 않은 모든 수열을 말한다.

예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다. 즉 부분 수열은 원래 수열의 순서를 지켜야 한다.

다음으로 증가부분수열(increasing subsequence)이란 부분수열에 포함된 숫자들이 순증가(strictly increasing)하는 부분수열이다. 순증가는 수열에서 모든 두 인접한 숫자 중 앞의 것이 항상 더 작다. 참고로 단조 증가(monotonically increasing)는 같은 경우도 함께 포함한다.

최장증가 부분수열 문제는 수열이 주어졌을때 얻을수 있는 증가부분수열 중 길이가 가장 길고 순증가(strictly increasing)하는 수열을 찾는 것이다. 아래는 수열이 주어졌을때, 가능한 최장증가부분수열을 나타낸 것이다.

{1 2 3 4} => {1 2 3 4}
{5 4 3 2 1 6 7 8} => {5 6 7 8},{4 6 7 8},{3 6 7 8},{2 6 7 8},{1 6 7 8},
{5 6 7 8 1 2 3 4} => {5 6 7 8},{1 2 3 4}

가장 간단한 전략은 $2^n$개의 부분수열을 모두 구하고 그 중에 조건을 만족하는 부분수열을 찾으면 된다. 하지만 너무 계산량이 많으니 다른 전략을 생각해야 한다.

먼저, 증가수열의 특성을 생각해보자. 증가수열에서 모든 원소는 자신보다 뒤에 있는 원소와 반드시 작거나 같아야 한다. 최장증가부분수열도 증가수열이기 때문에 특정한 위치에 원소는 반드시 뒤에 원소보다는 항상 작거나 같아야 한다. 예를 들어 $[5, 1, 10, 7]$이 주어졌을때 각 원소를 순회하면서 가능한 증가수열을 생각해보자.

[5] -> [5], [5, 1], [5, 10], [5, 7], [5, 1, 10], [5, 1, 7], [5, 10, 7], [5, 1, 10, 7]
[1] -> [1], [1, 10], [1, 7], [1, 10, 7]
[10] -> [10], [10, 7]
[7] -> [7]

증가수열은 순회의 기준이 되는 원소와 그 원소와 비교하여 같거나 큰 수들로 이루어진다. 따라서 기준 원소보다 작은 수들은 증가수열을 찾는과정에서 제외하여 검색량을 줄일 수 있다. 달리 말하면 기준 원소보다 같거나 큰 원소들로만 다음 재귀함수 호출시 사용하는 것이다.

getLIS(sequence) {
    //get LIS from candiateIS by the longest size;
    List candidateIS; //증가수열 후보군
    for(int index=0; index < sequence.lenth; index++)
        target = sequence[index]; 
        List numbers = getHigherOrEqualNumbers(sequence, ,target, index+1);
        candidateIS.add(target + getLIS(numbers));
    }
    return candidateIS()
}

메모이제이션을 사용하면 최대시간복잡도는 $O(n^2)$이다. 왜냐하면, 중복을 제외하면 함수 호출시 가능한 수열은 $n$가지가 되고 수열마다 증가부분수열을 구하기위해 $n$번의 추가 연산이 필요하기 때문이다. 또한 특정 수열에 대한 LIS를 계산하기 위해 과거에 연산증가수열을 찾으려면 맨 앞에 있는 숫자보다 큰 숫자들로만 만든 부분 수열들로 lis함수를 재귀 호출한다. 즉 현재 단계에 있는 수열은 과거에 있는 수열을 알 필요가 없다는 점에서 최적 부분 구조가 여기서도 성립한다.

더 빠른 방법으로 LIS 길이 찾기 

보다 전략적인 방법으로 $O(nlogn)$만에 LIS의 길이를 찾는 것이 가능하다. 주의할 점은 LIS 수열 자체가 아니라 길이를 빠르게 계산할 수 있다는 점이다 주의하도록 하자. 

이 방법은 정렬된 리스트 L에 원소를 추가 또는 교체하면서 진행한다. 주어진 입력 수열의 원소들을 앞에서부터 순회하는데 특정 순회 차례의 원소를 t(target)이라고 하겠다. 이때 추가 또는 교체하는 조건은 아래와 같다.

• 추가(Adding) 조건
  • 리스트가 비어있거나, 현재 리스트의 마지막 원소보다 t가 클 경우, 리스트에 t를 추가한다.
• 교체(Replacing)
  • 추가 조건이 아니라면 리스트에서 t의 LowerBound를 찾아 t로 교체한다.

정렬된 리스트(L)에 어떤 입력값(t)을 삽입하려고 하는데 삽입 후에도 정렬된 상태를 유지하고자 한다. 이 때 삽입 가능한 위치(index) 중에 가장 작은 위치를 리스트(L)에서 입력값(t)에 대한 LowerBound라고 한다.

예를 들어 1, 3, 3, 6, 7 이라는 배열에서 5의 LowerBound는 3이며, 3의 LowerBound는 1이다. 마지막으로 1의 LowerBound는 0이다. LowerBound의 연산은 최악의 경우 $O(log n)$이다.

정렬된 리스트는 과거의 입력값을 최대한 활용하여 이번 입력값이 리스트에 추가되는 경우가 많도록 만들어진 리스트이다. 교체 메커니즘은 정렬 리스트에서 가장 큰 수보다 입력값이 작은 경우, 그 작은 수로 기존 수열의 하나의 큰 수를 교체한다는 것을 말한다. 그 교체될 위치를 임의로 $i$라고 하자. $L[i]$가 t로 교체되면 결과적으로 $L[i+1] - L[i]$의 차이는 커지게 된다. 그리고 $L[i+1] - L[i]$의 차이가 커진다는 것은 다음 LowerBound를 계산시 $i+1$이 나올 경우가 많아진다는 의미다. 이런 식으로 입력 값에따라 LowerBound 보다 하나 큰 리스트 L은 정렬되어 있다고 볼 수 있고, 위치의 값을 작은 값으로 바꾸어 최대한 입력 값이 추가되도록 노력한다.

• 예제 1: 정렬된 리스트 $1, 5, 10$가 주어지고, 순서대로 $7, 8$을 입력해보자. 그러면 7의 LowerBound는 2이기 때문에 10이 7로 교체된다. 다음에는 자연스럽게 8이 추가되는데 앞선 교체 과정으로 입력값이 위치 3에 추가되도록 교체했기 때문이과정으로만 리스트를 변형하면 다음 호출시 정렬된 상태가 깨지지 않는다. 계속해서 LowerBound를 찾는데 이진 탐색을 사용할 수 있다.
• 예제 2: 정렬된 리스트가 $1,7, 10$ 주어지고, 순서대로 $3, 5, 9$이 입력해보자. 3의 LowerBound는 1이기 때문에 $1,3, 10$가 되고 $L[2]-L[1]$의 차이가 커진다. 덕분에 5가 입력될때 LowerBound는 2가 되고 $1,3,5$가 된다. 따라서 9는 자연스럽게 추가가 된다.

그 밖에 다른 예제를 보고 싶다면, 예제 링크를 가보자.
마지막으로 거듭 강조하지만 위 알고리즘은 LIS의 길이를 $O(nlogn)$만에 찾는 알고리즘이다. 진정한 LIS를 찾는것이 아니다.