LIS 최장 증가 수열

 

최장 증가 부분 수열은 배열에서 가장 긴 증가하는 수열을 찾는 알고리즘입니다.

 

예시) [ 7, 2, 3, 8, 4, 5 ] → 해당 배열에서는 [2,3,4,5]가 LIS로 답은 4

예시) [ 6, 2, 5, 1, 7, 4, 8, 3] -> [2,5,7,8]

 

DP로 풀기

일반적으로 푸는 방법은 DP을 이용하여 푸는 것입니다. 

이중 포문을 통하여 구현하며 시간복잡도는 O(N^2)가 나옵니다. 

 

방법은 간단합니다. 

Bottom to Top형태의 DP을 사용합니다.

i = 1 부터 Dp의 값을 계산해 나갑니다. i번째의 배열값은 자기보다 작은 index인 j번째 배열값들과 비교하여 더큰지를 비교합니다.

만약 더 크다면 해당번째의 Dp값을 비교합니다. Dp[i]의 의미는 i번째 인덱스에서 끝나는 가장 큰 최장 증가 수열을 의미합니다. i가 j보다 같거나 작다는 의미는 이전의 arr[i]가 더크다는 논리와 맞지 않으므로 dp[j]+1의 값으로 배정해주고 아니면 그대로 둡니다.

int arr[] = {7, 2, 3, 8, 4, 5};
int dp[] = new int[arr.length]; // LIS 저장 배열


for(int i = 1; i < dp.length; i++) {
    for(int j = i-1; j>=0; j--) {
        if(arr[i] > arr[j]) {
            dp[i] = (dp[i] <= dp[j]) ? dp[j]+1 : dp[i];
        }
    }
}
int max = -1;

for (int i = 0; i < dp.length; i++) {
	if(max < dp[i]) max = dp[i];
}

Lower Bound(이분탐색)으로 풀기

이분탐색으로 푸는 방법 역시 원리는 간단합니다. 

이분탐색으로 배열을 순회하면서 위치를 찾습니다. 만약 해당 위치에 이미 원소가 존재한다면 크기를 비교하여 작다면 교체합니다.

N번 순회하면서 LogN의 이분탐색을 하게되므로 시간복잡도는 O(NlogN)입니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// LIS를 찾는 함수
int LIS(vector<int>& arr) {
    int size = arr.size();
    if (size == 0) return 0;

    // LIS의 길이를 저장할 배열
    vector<int> tail(size, 0);
    int length = 1;

    tail[0] = arr[0];
    for (int i = 1; i < size; i++) {

        // arr[i]가 tail 배열의 마지막 요소보다 클 경우, LIS 길이를 증가시킨다.
        if (arr[i] > tail[length - 1]) {
            tail[length++] = arr[i];
        } 
        else {
            // 이분 탐색을 통해 arr[i]가 들어갈 위치를 찾는다.
            auto it = lower_bound(tail.begin(), tail.begin() + length, arr[i]);
            *it = arr[i];
        }
    }

    return length;
}