목차


LIS(Longest Increasing Subsequence)

Subsequence는 주어진 sequence에서 일부 원소를 제거해 얻을 수 있는 sequence입니다. 예를 들어, sequence $[1, 3, 2, 4, 6]$라 할 때 $[1, 3, 2, 4]$는 subsequence입니다. Subsequence는 원래 sequence의 순서를 유지해야 하지만, $[1, 2, 4]와 같이 연속적이지 않은 원소들로 이루어진 subsequence도 가능합니다.

LIS는 매우 유명한 동적 계획법 연습 문제 중 하나로, 주어진 sequence에서 가장 긴 증가하는 subsequence의 길이를 구하는 문제입니다. 이때 증가하는 subsequence는 원래 sequence에서 원소의 순서를 유지하면서, 각 원소가 이전 원소보다 크거나 같은 $[1, 3, 4, 6]$와 같은 subsequence를 말합니다.


완전 탐색

LIS 문제를 완전 탐색으로 풀 수 있습니다. sequence의 모든 부분 집합을 생성하고, 각 부분 집합이 증가하는 subsequence인지 확인하는 방식일 수도 있고, 또는 증가하는 모든 subsequence를 생성하고 가장 긴 subsequence를 찾는 방식일 수도 있습니다.

이 때 시간 복잡도는 $O(2^n)$이 됩니다.

모든 부분 집합을 생성하는 방법

#include <vector>

std::vector<std::vector<int>> generateSubsequences(const std::vector<int>& sequence, std::vector<int> current = {}, int index = 0) {
    if (index == sequence.size()) {
        return {current};
    }

    // 현 원소를 포함하지 않고 다음 원소로 넘어가는 경우
    std::vector<std::vector<int>> subsequences = generateSubsequences(sequence, current, index + 1);

    // 현 원소를 포함하고 다음 원소로 넘어가는 경우
    current.push_back(sequence[index]);
    std::vector<std::vector<int>> includeSubsequences = generateSubsequences(sequence, current, index + 1);

    subsequences.insert(subsequences.end(), includeSubsequences.begin(), includeSubsequences.end());
    return subsequences;
}

이런 뒤 각각의 부분 집합이 증가하는 subsequence인지 확인하고, 가장 긴 subsequence를 찾으면 됩니다. 이보다 간단한 방법은 다음과 같습니다.

증가하는 모든 subsequence를 생성하는 방법

#include <vector>

int LIS(const std::vector<int>& sequence, int index, std::vector<int>& current) {
    if (index == sequence.size()) {
        return 0;
    }

    int result = 0;
    if (current.empty() || current.back() < sequence[index]) {
        current.push_back(sequence[index]);
        result = 1 + LIS(sequence, index + 1, current);
        current.pop_back();
    }

    return std::max(result, LIS(sequence, index + 1, current));
}

위 알고리즘의 Time complexity는 $O(2^n)$입니다. 성능을 개선했어도 여전히 지수 시간 복잡도를 가지고 있기 때문에 큰 입력에 대해 사용하기 어렵습니다.


동적 계획법을 이용한 LIS

이 때 두 번째 해결책의 경우, 한 원소 이후의 LIS 중 가장 긴 subsequence를 구하는 문제가 반복되어 발생하고 있습니다. 이 때문에 overlapping subproblem이 발생하며, 이를 해결하기 위해 동적 계획법을 사용할 수 있습니다.

동적 계획법을 사용하면 시간 복잡도를 $O(n^2)$로 줄일 수 있습니다.

#include <vector>
#include <algorithm>

int LIS(const std::vector<int>& sequence, int index, std::vector<int>& cache) {
    if (index == sequence.size()) {
        return 0;
    }

    int& result = cache[index];
    if (result != -1) {
        return result;
    }

    result = 1;
    for (int next = index + 1; next < sequence.size(); ++next) {
        if (sequence[index] < sequence[next]) {
            result = std::max(result, 1 + LIS(sequence, next, cache));
        }
    }

    return result;
}

이 때 이 문제를 해결하기 위해서는 위에 작성한 함수를 다음과 같이 호출해야 합니다.

#include <vector>

int main() {
    std::vector<int> sequence = {3, 1, 2, 4, 6};
    std::vector<int> cache(sequence.size(), -1);

    int result = 0;
    for (int i = 0; i < sequence.size(); ++i) {
        result = std::max(result, LIS(sequence, i, cache));
    }

    return 0;
}

마지막의 for loop을 생략하기 위해서는 다음과 같이 코드를 수정할 수 있습니다.

#include <vector>
#include <algorithm>

int LIS(const std::vector<int>& sequence, int index, std::vector<int>& cache) {
    if (index == sequence.size()) {
        return 0;
    }

    int& result = cache[index];
    if (result != -1) {
        return result;
    }

    result = 1;
    for (int next = index + 1; next < sequence.size(); ++next) {
        if (index == -1 || sequence[index] < sequence[next]) {
            result = std::max(result, 1 + LIS(sequence, next, cache));
        }
    }

    return result;
}

이 경우 main 함수는 다음과 같이 작성할 수 있습니다.

#include <vector>

int main() {
    std::vector<int> sequence = {3, 1, 2, 4, 6};
    std::vector<int> cache(sequence.size(), -1);

    return LIS(sequence, -1, cache);
}

출처


2024-10-01
다음 글: 10월 4주차 알고리즘 문제 → 카테고리로 돌아가기 ↩