[LeetCode] 300. Longest Increasing Subsequence

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

Longest Increasing Subsequence - LeetCode

leetcode - Longest Increasing Subsequence

문제 유형 : 다이나믹 프로그래밍, 이진탐색, LIS

문제 난이도 : Medium

 

 

문제

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

 

정수 배열 nums가 주어진다.

가장 긴 증가하는 부분 수열의 길이를 반환하시오.

 

 

풀이

1. 다이나믹 프로그래밍(O(n²))

가장 대표적인 다이나믹 프로그래밍 문제 중 하나이다.

i번째 숫자를 부분 수열에 넣었을 때 최대 길이를 dp[i]에 담는다.

i에서 이전의 인덱스들을 찾아가면서, 만약 nums[i]보다 더 작은 값이 있다면, 그 인덱스에서의 dp값에서 +1한 값과 최대값을 비교하여 갱신한다.

dp배열에는 각 인덱스를 마지막으로 부분 수열에 넣었을 때의 최대 길이가 담겨있다.

 

2. 이진탐색(O(nlog n))

임시 lis 배열을 만든다.

배열 내에서 이진 탐색을 하면서, 임시 lis에 들어갈 경우의 자리를 찾는다.

(lower_bound를 이용하여 lis 내에서의 들어갈 경우의 위치를 찾는다.)

만약, 이번 원소가 lis중에서 가장 크다면, lis의 뒤에 추가한다.

아니라면, 기존의 lis에서 자신보다 크거나 같은 값과 교체한다. 

맨 뒤에 더 작은 값이 대신 들어오면, 앞으로 더 많은 요소를 받을 수 있기 떄문이다.

 

nums의 모든 요소를 순차적으로 한 번씩 위의 과정을 거치면, lis가 완성된다.

길이를 반환해주면 된다.

 

 

코드

C++

 

1. 다이나믹 프로그래밍

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        const int n = nums.size();
        vector<int> dp(n, 1);

        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j]+1);
                }
            }
        }

        for(int i = 0; i < n; i++) {
            cout << dp[i] << endl;
        }

        return *max_element(dp.begin(), dp.end());
    }
};

 

2. 이진탐색

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> lis;
        for (const auto &num : nums) {
            auto it = lower_bound(lis.begin(), lis.end(), num);
            if (it == lis.end()) {
                lis.push_back(num);
            } else {
                *it = num;
            }
            for(const auto &li : lis) {
                cout << li << " ";
            }
            cout << endl;
        }
        return lis.size();
    }
};