[ leetcode 문제풀이 ] Longest Increasing Subsequence

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

Longest Increasing Subsequence - LeetCode

(Longest Increasing Subsequence 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Longest Increasing Subsequence 문제 설명 > 

 

Longest Increasing Subsequence 문제는 다음과 같다.

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3, 6, 2, 7] is a subsequence of the array [0, 3, 1, 6, 2, 2, 7].

 

주어진 정수 배열 nums에 대해 가장 긴 부분 증가수열의 길이를 리턴하여라.

subsequence는 나머지 요소의 순서를 변경하지 않고 일부 요소를 삭제함으로써 만들 수 있는 수열이다. 예를 들어 [3, 6, 2, 7]은 배열 [0, 3, 1, 6, 2, 2, 7]의 subsequence이다.

 

다음 세 가지 출력 예시가 주어졌다. 

주어진 제한 조건은 1 ≤ nums.length ≤ 2500, -10^4 ≤ nums[i] ≤ 10^4 이다.

Follow up question으로는 O(n log n)의 시간복잡도를 갖는 알고리즘을 만들 수 있겠는가? 이다.

 

 

 

---

< Longest Increasing Subsequence 문제 접근 - 기본 > 

 

처음 작성한 코드는 nums[0]의 원소부터 이를 increasing subsequence의 최솟값으로 하는 가장 긴 배열을 찾는 과정을 nums[-1]이 최솟값으로 하는 경우까지 찾는 완전 탐색 알고리즘으로 작성하였다. 이를 코드로 보면 아래와 같다. (Cpp 사용) 

int cache[2501];
std::fill_n(cache, 2501, -1);		// 값이 할당되지 않은 경우를 나타내는 -1로 초기화

int lengthOfLIS(vector<int>& nums, int start){
    int& ret = cache[start+1];
    if(ret != -1) return ret;

    ret = 0;
    for(int next=start+1;next<nums.size();next++)
        if(start == -1 || nums[start] < nums[next])
            ret = max(ret, lengthOfLIS(nums, next)+1);
    return ret;
}

>> run lengthOfLIS(nums, -1)		// 가상의 index -1에서 시작하는 search

이 코드의 경우 각 nums의 index를 increasing subsequence의 최소 원소로 지정하기 위해 훑으며, 지정한 후 반복문으로 increasing subsequence를 구하기 위해 nums의 index를 한 번 더 훑게 된다. 즉, O(n^2)의 시간복잡도를 갖는다.

 

 

 

---

< Longest Increasing Subsequence 문제 접근 - 심화 >

 

앞서 살펴 본 알고리즘에서는 가능한 increasing subsequence를 모두 탐색해보며 구하고자 하는 값을 얻어냈다. memoization 하는 cache 배열로 따지면 cache[i] (nums[i]를 최솟값으로 하는 longest increasing subsequence의 길이를 누적해 최댓값 계산)을 구하기 위해 nums[i+1] ~ nums[-1]을 꼭 다 훑어 봐야 하는가? 하는 생각을 할 수 있다.

 

이를 적용하기 위해 부분 문제의 정의를 살짝 바꿔보자. 

cache[i]를 nums[i]를 최댓값으로 갖는 longest increasing subsequence의 길이라고 하자. 위에서 만든 알고리즘과 동일하게 nums[0] ~ nums[i-1]을 다 훑어보면 O(n^2)의 시간복잡도를 갖는 알고리즘이 된다. 이 경우 nums[0] ~ nums[i-1]을 훑어보는 이유는 nums[i]보다 작은 nums[j] 중 가장 큰 cache[j]를 찾기 위함이었다. 따라서 이 정보만 추려서 저장하도록 바꾸어 보자.

 

cache[i]의 정의를 i 길이의 increasing subsequence 중 가장 큰 원소의 최솟값으로 저장해두면, nums의 원소를 cache 배열에 삽입하는 과정으로 increasing subsequence에 대한 정보를 손 쉽게 업데이트 할 수 있다. 예시로 나오는 아래 gif 파일에서 각 행의 마지막 원소가 cache[i]에 대응된다.

 

from Wikipedia/Longest_increasing_subsequence

 

여기서 알 수 있는 것은 cache는 반드시 증가수열이다. 따라서, 새로운 원소를 cache에 삽입하는 것은 이미 정렬된 정수 배열에서 새로운 원소가 들어갈 위치를 찾는 것이므로 binary search를 적용해줄 수 있다.

 

이 과정을 코드로 구현하면 아래와 같다.

 

void binsearch(vector<int>& A, int low, int high, int target){
    while(low < high){
        int mid = (low + high)/2;
        if(A[mid] < target) low = mid+1;
        else high = mid;
    }
        A[low] = target;
} // 이진 탐색으로 cache값을 업데이트 하는 함수

int lengthOfLIS(vector<int>& nums) {
    vector<int> cache;
    cache.push_back(nums[0]);
     
    for(int i=1;i<nums.size();i++){
        if(cache.back() > nums[i])
            cache.push_back(nums[i]);
        else
            binsearch(cache, 0, cache.size()-1, nums[i]);
    }
    return cache.size();			// cache의 크기가 곧 LIS의 길이
} // O(n log n) time complexity

LIS의 길이 k에 대해 이진 탐색 혹은 삽입의 과정을 n회(nums의 크기를 n이라 하면) 반복하므로 위 알고리즘의 시간복잡도는

O(n log k) ≤ O(n log n) 으로 O(n log n)의 시간복잡도를 가짐을 알 수 있다.