[LeetCode] Longest Increasing Subsequence

https://leetcode.com/problems/longest-increasing-subsequence/

Longest Increasing Subsequence - LeetCode

 

정말 유명한 Longest Increasing Subsequence(LIS) 문제입니다. BOJ에도 관련 문제가 시리즈로 있으니 한 번 찾아서 풀어보시는 것을 추천드립니다. 

 

https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions

Blind 75 LeetCode Questions - LeetCode Discuss

 

위 링크에서 해당 문제의 분류를 보면 Dynamic Programming으로 분류가 되어 있습니다. 물론 DP로 풀 수 있지만 DP로 풀 경우 O(N^2)의 시간복잡도를 갖습니다. (DP를 이용한 LIS 풀이 https://belepi.tistory.com/6) 하지만 문제 하단의 follow-up question에서도 확인할 수 있듯이 이 문제는 O(NlogN)의 시간복잡도를 갖는 알고리즘이 존재합니다. 저는 이미 BOJ에서 LIS 문제 시리즈를 전부 풀어봤기 때문에 O(NlogN) 알고리즘으로 풀이하였습니다. 

 

3/6

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> ans;
        for(int num : nums){
            auto pos = lower_bound(ans.begin(), ans.end(), num);
            if(pos == ans.end()) ans.push_back(num);
            else ans[pos-ans.begin()] = num;
        }
        return ans.size();
    }
};

96.42%

 

Binary search를 이용한 알고리즘으로, 코드가 상당히 짧습니다. 우선 num이 들어갈 위치를 lower_bound를 통해(binary search, O(logN)) 찾아줍니다. ans 내에 num 이상의 수가 없을 경우 ans.end()가 반환되는데 이 때에는 ans에 num을 추가합니다. num 이상의 수가 존재하는 경우에는 해당 위치의 element 대신 num을 넣어줍니다. LIS의 길이는 ans의 size가 됩니다. 

 

매 num마다 binary search를 수행하므로 시간복잡도는 O(NlogN)입니다.

 

class Solution {
public:
    int L[2501];
    int lengthOfLIS(vector<int>& nums) {
        int len = 0;
        fill(L, L+2501, -1e5);
        for(int i = 0; i < nums.size(); ++i){
            auto pos = lower_bound(L, L+len+1, nums[i]);
            *pos = nums[i];
            if(pos == L+len+1) ++len;
        }
        return len;
    }
};

다음처럼 vector가 아닌 일반 배열을 이용하여 구현할 수도 있겠습니다. 유의할 점은 최소 입력값으로 -10^4까지 가능하므로 그보다 작은 수로 L 배열을 초기화해야한다는 점입니다. -1e5로 초기화했는데 이 때 memset이 아닌 fill이나 반복문을 통해 초기화해줘야 함에 다시 한번 유의해주세요. (memset으로 초기화할 수 있는 수는 0, -1, 0x3f, 0x7f 등으로 제한적입니다.)

 

여기서 주의할 점으로는 ans 배열이나 L 배열 모두 올바른 LIS가 아니라는 점입니다. 즉, LIS 중 하나를 출력하라고 했을 때(LIS가 여러 개 존재할 수 있으므로 그 중 하나를 출력하면 정답으로 인정되는 스페셜저지) ans이나 L 배열의 element를 차례대로 출력할 경우 AC를 받을 수 없습니다. 

 

이 경우 별도의 index를 저장할 배열을 사용해 백트래킹 등을 통해 LIS를 추적하는 알고리즘이 가능한데 이 부분에 대해선 추후 BOJ LIS 시리즈를 다룰 때 이 포스트도 함께 업데이트하도록 하겠습니다. 궁금하신 분들을 위해 미리 [BOJ] 14003번: 가장 긴 증가하는 부분 수열 5(https://www.acmicpc.net/problem/14003)의 소스 코드를 올려드리니 고민해보시면 좋을 것 같습니다.

 

#include <bits/stdc++.h>
using namespace std;
 
int arr[1000001], L[1000001], P[1000001], len, N;

void backtrace(int idx, int num) {
    if(idx == 0) return;
    if(P[idx] == num) {
        backtrace(idx - 1, num - 1);
        cout << arr[idx] << " ";
    }
    else {
        backtrace(idx - 1, num);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    for(int i = 1; i <= N; ++i) {
        cin >> arr[i];
        auto pos = lower_bound(L + 1, L + len + 1, arr[i]);
        *pos = arr[i];
        P[i] = pos - L;
        if(pos == L + len + 1) len++;
    }
    
    cout << len << "\n";
    backtrace(N, len);
}