[가장 긴 증가하는 부분 수열] LIS, DP, 이분탐색

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

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

 

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

- 최장 길이 구하는 방법 

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

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

 

void LIS_DP() {
    for (int i = 0; i < N; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i])
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }
}

 

 

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

 

rec에서 후반부 3에 왜 값이 1인지 모르겠지만

rec 보고 최종 LIS 구할 수 있음 

rec에서 N-1부터 찾아가면 LIS 배열 찾을 수 있음.

int Rec[N];
vector<int> LIS;
int BS(int left,int right,int val) {
    while (left < right) {
        int mid = (left + right) / 2;
        if (LIS[mid] < val) left = mid + 1;
        else right = mid;
    }
    return right;
}

int LIS_BS() {
    int ret = 1; // LIS 길이 
    LIS.push_back(arr[0]);
    Rec[0] = 0; //LIS에서 순서

    for (int i = 1; i < N; i++) {
        if (LIS.back() < arr[i]) {
            LIS.push_back(arr[i]);
            ret++;
        }
        int pos = BS(0, LIS.size() - 1, arr[i]);
        Rec[i] = pos;
        LIS[pos] = arr[i];
    }
    return ret+1;
}

 

 

 

참고1

참고2