가장 긴 증가하는 부분 수열 (LIS - Longest Increasing Subsequence) 알고리즘

 가장 긴 증가하는 부분 수열 (LIS)

최장 증가 부분 수열 문제란,  

주어진 수열에서 오름차순으로 되어있는 가장 긴 부분수열을 찾는 문제이다.

이 때, 부분수열은 반드시 연속적일 필요는 없으며,

필요하다면 중간을 건너뛰는 것도 가능하다.

예를 들어, 수열 A = {10, 20, 60, 50, 30, 40, 20} 에서,

가장 긴 증가하는 부분 수열은 A = {10, 20, 60, 50, 30, 40, 20} 이고, 길이는 4 이다.

대표적인 동적 계획법(Dynamic Programming) 문제이며,

이 게시글에서 설명할 주제는 다음과 같다.

• LIS의 특성
• N^2 문제풀이
• N*logN 문제풀이
• 경로 역추적 (백트래킹)

 LIS의 특성

어떤 수열에 대해 적절히 n개를 삭제하여 최대한 긴 증가 부분 수열을 만드는 것이므로,

이 알고리즘을 수행하면 다음 두 가지 정보를 얻을 수 있다.

• LIS를 만들기 위해 선택해야 할 요소. (또는 길이)
• LIS를 만들기 위해 제거해야 할 요소. (또는 길이)

e.g)

수열 A = {10, 20, 60, 50, 30, 40, 20} 에서,

가장 긴 증가하는 부분 수열은 A = {10, 20, 60, 50, 30, 40, 20} 이다.

따라서,

• LIS를 만들기 위해 {10, 20, 30, 40}을 선택해야 하고,
• LIS를 만들기 위해 {60, 50, 20}을 제거해야 한다. 

가장 긴 증가하는 부분수열 - N^2 알고리즘

먼저 간단한 동적 계획법을 사용하여 LIS를 풀어보자.

동적 계획법이란 동일한 형태의 작은 문제로 나누어 푸는 것 이므로,

큰 문제를 어떻게 작은문제의 합으로 표현할 수 있는지 생각해야 한다.

먼저, 다음과 같은 함수를 정의하자.

int solve(int x)   // x번째 인덱스를 끝으로 하는,  증가하는 부분수열의 길이.

수열 A = {10, 20, 60, 50, 30, 40, 20} 에 대해,

최종적인 가장 긴 증가하는 부분 수열의 길이는,

solve(0) ~ solve(6) 중에서 가장 큰 값임이 자명하며,

다음 solve의 값은,  

A[x]의 값보다 작은 이전 solve의 최댓값 + 1 임을 알 수 있다.

0123456

example)

solve(5)의 값은 A[5] 보다 작은 A[x]를 갖는 solve(x) 중에서  // {solve(0),  solve(1),  solve(4)}

가장 큰 값은 solve(4) 이므로,  solve(5) = solve(4) + 1 이다.

TOP-DOWN 방식

int A[];
int LIS[];
int solve(int x){
        //! 기저사항.
        if(x == 0) return 1;

        //! 메모이제이션.
        if(LIS[x] != 0) return LIS[x];

        //! A[x]보다 작은 solve 중 최대값 구하기.
        int partial_max = 1;
        for(auto i=0; i<x; i++){
                if(A[i] < A[x]) partial_max = max(partial_max, solve(i) + 1);
        }

        //! 메모한 뒤, 반환.
        LIS[x] = partial_max;
        return LIS[x];
}

BOTTOM-UP 방식

int A[];
int LIS[];

for(int i=0; i<N; i++){
        int partial_max = 1;
        for(int j=0; j<i; i++){
                if(A[j] < A[i]) partial_max = max(partial_max, LIS[j] + 1);
        }
        LIS[i] = partial_max;
}

적어도 각 위치에 대해 한번씩 순회해야 하고,  (N)

그 위치보다 작은 위치에도 한번씩 순회해야 하므로.  (N)

시간 복잡도는 N^2이다.

 N*logN 문제풀이

A[x]보다 작은 A[y]를 갖는 slove(y)의 최댓값을 구하는 동작을 개선하면,

더 효율적인 풀이가 가능하다.

기본 아이디어는 다음과 같다.

int[ ] seq(int x)   // x번째 원소까지 이용했을 때, 증가 수열의 길이를 최대한 늘리는데 가장 유리한 증가 수열.

seq의 길이를 늘리는데 관심을 집중한다면,

모든 원소를 다 이용했을 때의 seq의 길이는, LIS의 길이와 동일할 것 이다.

그렇다면 seq(x)는 앞선 seq(x-1)을 이용해 정의될 수 있을까?

다음과 같은 경우를 살펴보자.

• case1,  A[x]가 seq(x-1)의 마지막 항 보다 큰 경우.
  

seq(x) = seq(x-1)의 마지막 위치에 A[x]를 삽입한 것.

seq의 길이가 늘어나는 방향으로 진행되어야 되기 때문이다.

• case2,  A[x]가 seq(x-1)의 마지막 항에 비해서만 작은 경우.

seq(x) = seq(x-1)의 마지막 원소가 A[x]로 갱신된 것.

이 경우에는 seq의 길이를 직접적으로 늘릴 수 없는 것에 유의하자.

A[x]가 길이를 늘리는데 참여하려면 seq의 마지막 원소보다 먼저 나왔어야 했다.

하지만,  다음 seq의 길이가 늘어나는데 최대한 유리하게 갱신해야 하므로.

이전 seq의 마지막 원소를 A[x]로 갱신한다.

이 경우가 반복되면 seq의 마지막 원소가 항상 작아지는데,

이렇게 되면 작은 수로도 seq의 마지막 위치에 삽입될 수 있기 때문에 유리하다.

따라서, seq의 마지막 원소가 A[x]로 갱신되는 것이,

다음 seq의 길이가 늘어날 가능성을 최대한 높이는 것이 된다.

예를 들어, 다음의 그림을 보자.

마지막 원소가 작은쪽으로 갱신되었기 때문에, 40을 마지막에 붙일 수 있었다.

• case3,  A[x]가 중간항에 비교해서 작을 경우.
  

seq(x) = seq(x-1)에서 lower_bound(A[x]) 위치를 A[x]로 갱신한 것.

이유는 case2와 비슷한데, 다음 seq의 길이를 최대화 시키기 위해서는,

seq의 마지막 원소가 최대한 작은것이 유리하다.

또한, seq[last]가 작아지려면 seq[last-1]가 작아야 유리하고,

seq[last-1]이 작아지려면 seq[last-2]가 작아야 유리하다.

즉, seq[x]가 작아지려면 seq[x-1]이 작아야 유리하다.

seq의 정의상 정렬을 깰 수 없으므로,

A[x]보다 처음으로 큰 원소를 A[x]로 바꿔야 한다.

다음의 그림을 살펴보자.

seq(6)의 3번째 원소가 25로 작아졌으므로,

A[7]=30이 있었을 경우, 

다음 seq(7)의 마지막 원소는 30으로 작아지는데 성공한다.

seq의 길이가 최대한 늘어나는 방향으로 갱신되므로,

seq(N)의 길이는 A[0...N]에서의 LIS의 길이임을 확신할 수 있다.

단, 이것으로 얻을 수 있는 것은 "정답의 길이"라는 것을 잊지 말아야 한다.

위의 예시에서 실제 LIS는 {10, 20, 30, 40} 이지만,  seq(6)은 {10, 20, 25, 40} 이다.

단지, 다음 부분 수열을 늘리기 유리한 방향으로 업데이트 되기 때문이다.

BOTTOM-UP

int A[ ];
int seq[ ];        
int len = 0;

for(int i=0; i<N; i++){
        int pos = lower_bound(seq, seq+len, A[i]) - seq;
        seq[pos] = A[i];
        if(pos == len) len++;
}
cout << len;

이것으로 A[x]보다 작은 solve의 최댓값을 logN 시간만에 구할 수 있으므로,

최종 시간 복잡도는 N*logN 이다.

 경로 찾기

실제 LIS의 경로를 역추적하기 위해서는, 간단한 수정이 필요하다.

int pos[ ]   // 최선을 다했을 때, A[x]가 seq에 위치되는 인덱스 번호.

맨 오른쪽의 최댓값부터 시작하여,

가장 최선으로 갱신된 지점을 선택하면 된다.

pos[2..4] = 3 이지만, pos[4]가 가장 최선인 지점임을 유의하자.

 LIS 관련 문제

검색 : 가장 긴 증가하는 부분 수열

LIS - 1 페이지