[알고리즘] 최장 증가 부분 수열(LIS) - DP, 이분 탐색, LIS 출력

최장 증가 부분 수열 (LIS)이란?

어떤 수열에서 수열의 일부 원소를 골라 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 수열을 최장 증가 부분 수열이라고 한다.

이 최장 증가 부분 수열 알고리즘을 간단하게 구현하는 방법은 DP를 사용하는 것이다.

다이나믹 프로그래밍을 이용한 최장 증가 부분 수열

   for(int i=1;i<num;i++){
        dp[i] = 1;
         for(int j=0;j<i;j++){    
            if(v[i] > v[j] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
        }
        result = max(result, dp[i]);
    }

각 수열의 원소까지의 최장 증가 부분 수열의 크기를 dp배열에 입력을 해주는 알고리즘이다.
처음 원소부터 해당 원소까지 for문을 돌리는데
이때, for문에서 돌리는 원소의 크기보다 해당 원소의 크기가 크고 최장 증가 부분 수열의 크기는 작다면 해당 원소의 최장 증가 부분 수열 크기 값을 갱신해준다.

아래는 다이나믹 프로그래밍으로 LIS알고리즘을 푼 문제이다.

https://kimmessi.tistory.com/189?category=833468

[LIS, DP] BOJ 11053 가장 긴 증가하는 부분 수열 (C++)

이런 식으로 이중 for문을 이용해서 푼다면 시간 복잡도가 $O(n^2)$이다.

하지만 이분 탐색을 이용해 LIS 알고리즘을 만든다면 $O(n \mathrm{log} n)$으로 더 빠른 알고리즘이 가능하다.

이분 탐색을 이용한 최장 증가 부분 수열

수열의 각 원소들을 최장 증가 부분 수열에 맞게 LIS 배열에 입력해준다.
이 때, 각 원소의 위치를 이분 탐색으로 찾아주는 것이다.

예를 들어,

위와 같은 수열이 있다고 하자.

우선 LIS 배열에 초기 원소인 10을 넣어준다.

다음 두 번째 원소인 20은 마지막 원소인 10보다 크므로 마지막 다음 자리에 값을 넣는다.

다음 세 번째 원소인 10이 들어갈 자리를 이분 탐색으로 찾는다.
인덱스 값인 0에 10을 입력해준다.

다음 네 번째 원소 30은 마지막 원소인 20보다 크므로 마지막 다음 자리에 값을 넣는다.

다음 다섯 번째 원소인 20이 들어갈 자리를 이분 탐색으로 찾는다.
인덱스 값인 1에 20을 입력해준다.

다음 여섯 번째 원소 50은 마지막 원소인 30보다 크므로 마지막 다음 자리에 값을 넣는다.

모든 원소를 비교해봤으므로 LIS의 크기가 최장 증가 부분 수열의 크기이다.


일반적으로 이분 탐색 알고리즘은 $O( \mathrm{log} n)$이고,
모든 원소를 한 번씩 방문하므로 이분 탐색을 이용한 최장 증가 부분 수열 알고리즘의 시간복잡도는 $O(n \mathrm{log} n)$이다.

아래는 이분 탐색을 이용한 LIS알고리즘으로 구하는 문제이다.
https://kimmessi.tistory.com/190?category=833468

[LIS, 이분 탐색] BOJ 12738 가장 긴 증가하는 부분 수열 3 (C++)

하지만 이런 식으로 푼다면 최장 증가 부분 수열의 크기는 구할 수 있지만 최장 증가 부분 수열을 구할 수는 없다.

그러면 길이도 구하고 최장 증가 부분 수열도 구해보자.

각 원소가 LIS에 들어갈 때 인덱스 값을 record 배열에 따로 정리를 한다.
그 배열의 값들을 바탕으로 최장 증가 부분 수열을 구할 수 있다.

예를 들어,

위와 같은 수열이 있다고 하자.

위에 이분탐색을 이용한 LIS알고리즘으로 LIS 배열에 입력을 해주고 record 배열에 해당 인덱스 값을 넣는다.
이 방식대로 쭉 해주면 된다.

이런 식으로 해당 값이 넣어질 인덱스 값을 구했다면
그 인덱스 값을 최대값순으로 역순으로 차례대로 구하면 우리가 구하고자하는 최장 증가 부분 수열이 나오게 된다.

배열에서 최장 증가 부분 수열 길이는 4이므로 역순으로 4 3 2 1로 가장 최근에 기록된 숫자를 출력해준다.


여기서는 -61 -28 -21 -1이 LIS이다.

아래는 LIS알고리즘을 통해 길이와 수열을 구하는 문제이다.

https://kimmessi.tistory.com/188?category=833468

[LIS, 이분 탐색] BOJ 14003 가장 긴 증가하는 부분 수열 5 (C++)