[Algorithm] 최장 증가 부분 수열(LIS / Longest Increasing Subsequence)

조재훈·2024년 10월 10일

algorithm

개요

백준 문제를 풀다가 LIS와 관련된 문제가 나왔다. 자주는 아니지만 등장 하는 경우가 있는 문제라 개념을 확실히 알아두면 나중에 문제를 풀 때 빠르게 대응할 수 있을 것 같아 블로그에 정리하려 한다

LIS

LIS란?
문제에서 주어진 수열에서 순서를 유지하면서 증가하는 부분 수열 중 가장 길게 증가하는 수열을 의미한다

예를 들어, 수열 {10, 22, 9, 33, 21, 50, 41, 60, 80}이 주어졌을 때, LIS는 {10, 22, 33, 50, 60, 80}이며, 길이는 6이다

구현

이를 구현하는 방법은 여러 가지가 있고 각 방법마다 구현 방법과 효율이 다르다

완전 탐색(브루트 포스)

완전 탐색으로 풀 경우 수열 내에 존재하는 모든 부분 수열을 찾고 증가하는 수열 중 가장 긴 수열을 찾아야 한다

모든 부분 수열을 구하려면 i번째 인덱스를 포함할 지 안 할지 이기에 2x2..x2 = 2^n의 시간 복잡도이다. 절대 피해야 한다

DP(동적 계획법)

이 방법은 DP 배열을 이용해 각 원소를 마지막으로 하는 증가 부분 수열의 최대 길이를 계산한다. 기본 아이디어는 각 원소에 대해 그 원소보다 앞에 있는 원소들과 비교하며, 해당 원소가 이전 원소보다 크다면 DP 배열을 갱신해나가는 식이다

예제 문제를 풀면서 살펴보자
백준 11053번

코드로 살펴보자. dp[i]는 i번째 원소에서 시작했을 때 가장 긴 수열의 길이이다

#include <bits/stdc++.h>

using namespace std;

int n;
int arr[1004];
int dp[1004];

int LIS_DP() {

    // DP로 LIS 길이 계산
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            if (arr[i] > arr[j])
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    // 최대 LIS 길이 반환
    return *max_element(dp, dp + n);
}

int main() {
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    // 일단 dp 배열의 초깃값은 1이다
    for (int i = 0; i < n; i++)
    {
        dp[i] = 1;
    }

    cout << LIS_DP() << endl;

    return 0;
}

위의 코드는 단순해서 비슷한 문제들을 풀다 보면 저절로 손이 기억할 것 같다

하지만 이중 반복문을 쓰고 O(N^2)의 시간복잡도가 걸리는 것을 알 수 있을 것이다. 그래서 N이 커지면 못 쓰는 알고리즘임

이분 탐색

LIS를 할 때 대부분은 이 알고리즘을 사용한다고 한다. DP보다 훨씬 빠르고 간단하다고 함

원본 배열과는 다른 LIS를 기록하는 배열을 하나 만든다. 각 원소에 대해 새로운 배열에서 해당 원소가 들어갈 위치를 이분 탐색으로 찾는 개념이다

#include <bits/stdc++.h>

using namespace std;

int n;
int arr[1004];

int LIS_BS()
{
    // LIS용 리스트 생성 후 첫 번째 원소 삽입
    vector<int> v;
    v.push_back(arr[0]);

    for (int i = 1; i < n; i++)
    {
        // arr[i]가 LIS 배열에 있는지 확인
        auto index = lower_bound(v.begin(), v.end(), arr[i]);

        // 만약 arr[i]보다 큰 값이 LIS 배열에 없다면 리스트에 추가
        if (index == v.end())
        {
            v.push_back(arr[i]);
        }
        else
        {
            *index = arr[i];
        }
    }

    return v.size();
}

int main() {
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    // 일단 dp 배열의 초깃값은 1이다
    for (int i = 0; i < n; i++)
    {
        dp[i] = 1;
    }

    cout << LIS_BS() << endl;

    return 0;
}

여기선 lower_bound가 핵심인데 이 함수를 통해 새로 들어온 수가 LIS 배열의 어디에 위치해야 하는지를 결정한다

lower_bound
정렬된 배열에서 주어진 값 이상이 처음 나타나는 위치를 반환

현재 수가 LIS 배열에서 가장 큰 값일 경우 : 벡터의 end()를 반환 -> 현재 수가 LIS 배열에 추가될 수 있음을 의미
현재 수가 LIS 배열에서 그 수보다 큰 값을 대체할 경우 : 현재 수가 LIS 배열의 어느 위치에 들어가는 지 반환하고 해당 위치의 값을 교체함