[LeetCode] 300 - Longest Increasing Subsequence

문제

• 링크: https://leetcode.com/problems/longest-increasing-subsequence
• 난이도: Medium
• 태그: 배열, 이진 탐색, 다이내믹 프로그래밍
• 결과: Time: 0 ms (100.00%), Space: 13.86 MB (99.30%)

풀이

$O(n^2)$ 풀이

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> d(n);

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

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

웰노운 오브 웰노운, LIS이다. 일단 간단하게는 이렇게 풀 수 있다. d[i] = a[i]를 마지막으로 하는 LIS의 길이로 점화식을 세우면 된다. 그렇게 2중 for문을 돌면서 증가하는 부분수열인지 판단해서 최댓값을 업데이트 해나가면 된다.

시간 복잡도는 $O(n^2)$으로, 백준 11053 - 가장 긴 증가하는 부분 수열에서 요구하는 수준이다.

$O(n \log n)$ 풀이

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> d;

        for (int i = 0; i < n; ++i)
        {
            auto it = lower_bound(d.begin(), d.end(), nums[i]);
            if (it == d.end())
            {
                d.push_back(nums[i]);
            }
            else
            {
                *it = nums[i];
            }
        }

        return d.size();
    }
};

이진 탐색을 활용한 아이디어이다. 시간 복잡도는 $O(n\log n)$으로, 백준 12015 - 가장 긴 증가하는 부분 수열 2에서 요구하는 수준이다.

여기서는 길이가 k인 증가하는 부분 수열을 만들 때, 마지막 원소를 최대한 작게 유지한다는 전략을 세운 것이다. 마지막 원소가 작을 수록 그 뒤에 더 많은 숫자를 이어붙일 수 있기 때문이다.

이를 위해서 d에서 nums[i]보다 크거나 같은 값이 있으면 그 값을 nums[i]로 교체할 수 있다. 구현의 관점에서는 배열을 순회하면서 std::lower_bound를 통해 d 배열에서 nums[i]보다 크거나 같은 값의 위치를 찾아 값을 덮어쓰면 된다. 만약 d의 모든 원소가 nums[i]보다 작아 d.end()가 반환되었다면 d의 맨 뒤에 추가하면 된다.

예를 들어, [3, 1, 8, 2, 5]를 처리해보자.

처리할 원소	d 배열	설명
3	[3]
1	[1]	3보다 1이 작음, 이걸 택하는게 이득
8	[1, 8]	8은 d에 있는 모든 요소보다 큼, 뒤에 추가
2	[1, 2]	8보다 2가 작음, 이걸 택하는게 이득
5	[1, 2, 5]	5는 d에 있는 모든 요소보다 큼, 뒤에 추가

이렇게 구한 d의 길이가 곧 LIS의 길이가 된다. 주의할 점은, d 배열이 LIS 그 자체는 아니라는 것이다. d의 엄밀한 정의는 d[i] = 길이가 i + 1인 증가하는 부분 수열에서 마지막 값이 될 수 있는 가장 작은 값이다. d는 LIS를 저장하는 게 아니라, “길이가 i인 증가하는 부분 수열을 만들 때 끝 값이 최소 얼마인가?”라는 정보를 담는 배열이다.

d가 유효한 LIS가 될 수 없는 예로, [3, 5, 6, 2]를 처리해보자.

처리할 원소	d 배열
3	[3]
5	[3, 5]
6	[3, 5, 6]
2	[2, 5, 6]

보다시피 마지막에 2를 업데이트하면서 d 배열은 실제 LIS가 아니게 되었다. 그러나 d의 길이는 LIS의 길이와 동일하다. d의 길이를 늘리는 d.push_back은 실제로 이어붙일 수 있는 시점에만 실행되기 때문이다.

배운 점과 후기

분명 몇 년 전에 백준에서 풀었던 건데 다 까먹었다. 알고리즘 공부 정말 열심히 해야겠다…

이 포스트는 달레 스터디(6주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.