최대 증가 부분 수열

최대로 긴 증가하는 부분 수열을 구하는 방법

다음의 수열이 있다.

10, 20, 10, 30, 20, 50

다음의 4가지를 사용해 최대 증가 수열을 만들 수 있다.

10, 20, 10, 30, 20, 50

다음의 3가지를 사용해도 증가하는 수열을 만들 수 있지만 최대로 긴 부분수열은 아니다.

10, 20, 10, 30, 20, 50

각자 자신의 위치에서 왼쪽을 바라보고

그 중 자기보다 작은 수들 중에 가장 큰 cnt 값에 + 1을 해서 자신한테 적는다.

예시 코드

시간 복잡도는 n^2 이니 주의.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int result = 0;

int n = 6; // 더미값
int a[1001] = { 10, 20, 10, 30, 20, 50 }; // 더미값
int cnt[1001];
int ret;

// int main(void)
int Code::main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    for (int i = 0; i < n; ++i)
    {
        int maxValue = 0;

        for (int k = 0; k < i; ++k)
        {
            if (a[k] < a[i] && maxValue < cnt[k])
                maxValue = cnt[k];
        }
        
        cnt[i] = maxValue + 1;
        ret = max(ret, cnt[i]);
    }

    cout << ret;
    return 0;
}

예시 코드 2

최대 크기가 아니라 배열을 구하고 싶다면

별도로 prev_list를 두어서 이전 값을 저장하면 된다.

추가적으로 cnt를 전부 1로 초기화 한 다음에,

이번에 탐색한 위치가 현재 위치보다 작고 + 이번에 탐색한 위치 cnt + 1 한 것보다 현재위치가 작은 경우 갱신한다.

이것도 이중 for문이라 시간복잡도는 n^2이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int result = 0;

int n = 6; // 더미값
int a[1001] = { 10, 20, 10, 30, 20, 50 }; // 더미값
int cnt[1001];
int prev_list[1001];
int ret;
int idx;

vector<int> v;
void Go(int idx)
{
    if (idx == -1) return;
    v.push_back(a[idx]);
    Go(prev_list[idx]);
}

// int main(void)
int Code::main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    fill(prev_list, prev_list + 1001, -1);
    fill(cnt, cnt + 1001, 1);

    for (int i = 0; i < n; ++i)
    {
        for (int k = 0; k < i; ++k)
        {
            if (a[k] < a[i] && cnt[i] < cnt[k] + 1)
            {
                cnt[i] = cnt[k] + 1;
                prev_list[i] = k;

                if (ret < cnt[i])
                {
                    ret = cnt[i];
                    idx = i; // 최대값이 증가했다면 idx를 최신화
                }
            }
        }
    }

    Go(idx);
    for (int i = v.size() - 1; i >= 0; --i)
    {
        cout << v[i];
    }

    cout << ret;
    return 0;
}

예제 코드 3

이번에는 NlogN 시간복잡도이다.

선형 탐색하면서 자신보다 큰값이 없다면 수열에 넣고

자신보다 큰값이 맨 마지막에 있다면 자신으로 대체한다

정말 간단하고 코드도 짧고 성능도 좋지만

로직 실행 시 원본 배열을 훼손하기 때문에

Trace가 불가능하기 때문에 크기만을 구하는 문제에서 사용할 수 있다.

#include <iostream>
#include <vector>
using namespace std;

int n, lis[1001], len, num;

// int main(void)
int Code::main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;

    for (int i = 0; i < n; ++i)
    {
        cin >> num;
        auto lowerPos = lower_bound(lis, lis + len, num); // 크거나 같은 값을 찾는 함수
        if (*lowerPos == 0) // 없다
            len++;

        *lowerPos = num;
    }

    cout << len;
    return 0;
}

std::lower_bound 는 이진탐색으로 정렬된 범위에서 특정 값 이상의 첫 번째 위치(iterator)를 찾아주는 함수이다. 

기존은 0으로 초기화했는데

범위가 -1e9 ~ 1e9 같이 넓게 주어지면 기본값을 1e9 +1 정도로 값이 될 수 없는 값으로 지정해주자.

https://www.acmicpc.net/problem/14003 

lower_bound로 트래킹 하는 방식은 아래와 같다.

위에서 n^2 로직들은 잊어버리고 이걸로만 기억하면 된다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int n, temp, len;
vector<int> v;
vector<pair<int, int>> ans;
const int MAX = 1e9 + 1;

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

    cin >> n;
    v.resize(n, MAX);
    ans.resize(n);

    for (int i = 0; i < n; ++i)
    {
        cin >> temp;
        auto lowerPos = lower_bound(v.begin(), v.end(), temp);
        int _pos = (int)(lowerPos - v.begin());
        if (*lowerPos == MAX)
            ++len;

        *lowerPos = temp;
        ans[i] = { _pos , temp };
    }

    cout << len << '\n';

    vector<int> ret;
    for (int i = n - 1; i >= 0; --i)
    {
        if (ans[i].first == len - 1)
        {
            ret.push_back(ans[i].second);
            --len;
        }
    }
    
    auto it = ret.rbegin();
    while (it != ret.rend())
    {
        cout << *it << ' ';
        ++it;
    }
}