[Algorithm]Baekjoon 12015번 : 가장 긴 증가하는 부분수열 2

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

12015번: 가장 긴 증가하는 부분 수열 2

 
using namespace std;
 
int n, input;
vector<int> v(1);
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;cin >> v[0];
 
    for (int i = 0; i < n; ++i)
    {
        cin >> input;
 
        if (v.back() < input)
        {
            v.push_back(input);
        }
        else
        {
            *lower_bound(v.begin(), v.end(), input) = input;
        }
    }
 
    cout << v.size();
}
 
 
 
 
 

 

시간복잡도 N logN으로 풀어보는 LIS문제이다.

N^2풀이만 알다가, 시간복잡도를 더 줄여야하는 문제를 풀어야해서 알아보게 되었다.

 

이 풀이법은 코드작성은 정말 쉽다.

일단 로직은 다음과 같다.

 

1. input값이 벡터의 마지막원소보다 크면 그대로 넣어준다.

2. input값이 벡터의 마지막원소보다 작으면, 벡터내에서 해당 원소보다 같거나 큰(대신 차이가 가장 적은) 원소를 찾아서 대체한다.

 

1번은 말 그대로고, 2번같은경우는 이분탐색을 이용해서 원소를 찾으면 된다.

직접 작성해도 되고, stl에서 제공하는 lower_bound함수를 사용하면 편하게 구할 수 있다.

 

여기서 사용되는 벡터자체가 일단 LIS이다. 그렇기 때문에 벡터의 크기가 LIS의 길이이다.

위 로직대로 했을 때 LIS가 구해지는 이유는, 최대한 각 원소들 크기의 갭을 줄이면서 늘리기 때문이다.

오름차순을 형성해야하기 때문에 숫자가 커질수록 LIS의 크기가 줄어들 가능성이 '반드시' 높아진다.

그렇기때문에 위 로직을 수행하면 LIS크기는 유지하되, 각 원소크기의 갭을 줄이는 업데이트를 수행하게 되는것이다.

 

설명보다는 사실 아무 특정케이스를 적용해서 로직수행과정을 보면 더 쉽게 알 수 있다.