[Computer Algorithms] LIS (Longest Increasing Subsequence, 최장 증가 부분 수열)

LIS (Longest Increasing Subsequence)

말 그대로 가장 긴 증가하는 부분 수열이다. 수열에서 LIS를 구하는 방법은 두 가지가 있다.

1. DP를 이용한 방법 -> 시간 복잡도 O(N^2)

2. 이분 탐색을 이용한 방법 -> 시간 복잡도 O(N * logN)

 

Finding LIS using DP

- LIS의 길이 구하기 (DP)

문제 링크 : https://www.acmicpc.net/problem/11053

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <algorithm>
#define endl '\n'
using namespace std;

int N;
vector<int> A, DP;
int maxVal = 0;

void input()
{
    cin >> N;
    A.resize(N);
    DP.resize(N);

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

void solution()
{
    for (int i = 0; i < N; i++)
    {
        DP[i] = 1;
        for (int j = 0; j < i; j++)
        {
            if (A[j] < A[i] && DP[i] < DP[j] + 1)
                DP[i] = DP[j] + 1;
        }
    }

    for (int i = 0; i < N; i++)
    {
        if (maxVal < DP[i])
            maxVal = DP[i];
    }
}

void output()
{
    cout << maxVal << endl;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    solution();
    output();
    return 0;
}

DP[i]는 0~i 수열의 LIS의 길이를 저장한다.

1. DP[i]를 1로 설정한다.

2. j를 0 부터 i - 1 이라고 할 때, A[j]중 A[i]보다 작은 값이 있다면 DP[i] = DP[j] + 1로 업데이트 해준다.

 

- LIS와 LIS의 길이 구하기 (DP)

문제 링크 : https://www.acmicpc.net/problem/14002

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <algorithm>
#define endl '\n'
using namespace std;

int N;
vector<int> A, DP, parent, LIS;
int maxVal = 0, maxIndex = 0;

void input()
{
    cin >> N;
    A.resize(N);
    DP.resize(N);
    parent.resize(N, -1);

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

void solution()
{
    for (int i = 0; i < N; i++)
    {
        DP[i] = 1;
        for (int j = 0; j < i; j++)
        {
            if (A[j] < A[i] && DP[i] < DP[j] + 1)
            {
                DP[i] = DP[j] + 1;
                parent[i] = j;
            }
        }
    }

    for (int i = 0; i < N; i++)
    {
        if (maxVal < DP[i])
        {
            maxVal = DP[i];
            maxIndex = i;
        }
    }

    for (int index = maxIndex; index != -1; index = parent[index])
    {
        LIS.push_back(A[index]);
    }
    reverse(LIS.begin(), LIS.end());
}

void output()
{
    cout << LIS.size() << endl;
    for (int e : LIS)
        cout << e << " ";
    cout << endl;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    solution();
    output();
    return 0;
}

1. 모든 노드의 parent의 인덱스를 -1로 초기화한다.

2. j를 0 부터 i - 1 이라고 할 때, A[j]중 A[i]보다 작은 값이 있다면 i의 parent는 j가 된다.

3. DP의 값이 가장 큰 원소의 인덱스를 maxIndex에 저장한다.

4. parent의 인덱스가 -1이 될 때까지 트랙킹 하며 LIS를 채운다.

 

Finding LIS using Binary Search

- LIS의 길이 구하기 (Binary Search)

문제 링크 : https://www.acmicpc.net/problem/12738

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <algorithm>
#define endl '\n'
using namespace std;

int N;
vector<int> A, LIS;

void input()
{
    cin >> N;
    A.resize(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
}

void solution()
{
    for (int i = 0; i < N; i++)
    {
        auto pos = lower_bound(LIS.begin(), LIS.end(), A[i]);
        if (pos == LIS.end())
            LIS.push_back(A[i]);
        else
            *pos = A[i];
    }
}

void output()
{
    cout << LIS.size() << endl;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    solution();
    output();
    return 0;
}

  A를 순차적으로 순회하며 LIS 배열에 A[i]보다 크거나 같은 값이 없다면, 즉 A[i]가 LIS에 현재 있는 모든 값보다 크다면 LIS에 들어간다. 

LIS에 A[i]보다 크거나 같은 값이 있다면, 새로운 LIS를 업데이트 하기 위해서 그 자리를 A[i]로 대체한다. 따라서 LIS의 길이는 정확하겠지만 최종적으로 LIS의 들어있는 원소들은 실제 수열에서의 LIS가 아닐 수 있다.

 

- LIS와 LIS의 길이 구하기 (Binary Search)

문제 링크 : https://www.acmicpc.net/problem/14003

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <algorithm>
#define endl '\n'
using namespace std;

int N, lisIndex;
vector<int> A, LIS, parent, LISIndices;

void input()
{
    cin >> N;
    A.resize(N);
    parent.resize(N, -1);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
}

void solution()
{
    for (int i = 0; i < N; i++)
    {
        auto pos = lower_bound(LIS.begin(), LIS.end(), A[i]);
        lisIndex = pos - LIS.begin();

        if (pos == LIS.end())
        {
            LIS.push_back(A[i]);
            LISIndices.push_back(i);
        }
        else
        {
            *pos = A[i];
            LISIndices[lisIndex] = i;
        }

        if (lisIndex > 0)
            parent[i] = LISIndices[lisIndex - 1];
    }

    int index = LIS.size() > 0 ? LISIndices.back() : -1;

    LIS.resize(0);
    while (index != -1)
    {
        LIS.push_back(A[index]);
        index = parent[index];
    }
    reverse(LIS.begin(), LIS.end());
}

void output()
{
    cout << LIS.size() << endl;
    for (int e : LIS)
        cout << e << " ";
    cout << endl;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    solution();
    output();
    return 0;
}

LIS에 들어있는 원소가 A에서 몇번째 원소인지 저장하는 LISIndices 배열을 추가한다.

1. 모든 노드의 parent의 인덱스를 -1로 초기화한다.

2. lower_bound함수를 통해서 i번째 수가 LIS에 삽입될 위치를 lisIndex에 저장한다. 이 위치의 인덱스가 0보다 크다면, i번째 수의 parent는 LISIndices[lisIndex - 1]이다.

3. LIS.size()가 0보다 크다면, index에 LISIndices의 맨 뒤에 있는 값을 저장한다.

4. parent의 인덱스가 -1이 될 때까지 트랙킹 하며 LIS를 채운다.