문제 설명
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
https://www.acmicpc.net/problem/12738
제한 사항
풀이
문제를 요약하면, 주어진 배열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 것이다.
유명한 DP문제인 LIS를 구현하면 된다.
하지만, 해당 문제의 난도가 높게 평가된 이유는 아마 시간 초과를 해결해야 하기 때문이다.
보통의 LIS는 $O(N^2)$의 시간복잡도를 갖는다.
i번째 이전의 수중 i번째 수보다 더 작은 수가 갖고 있는 가장 긴 증가하는 부분 수열에 마지막에 i번째 수를 추가하면 되기 때문이다.
따라서, N개의 수에 대해 N번의 탐색을 통해 자신보다 작은 수들을 탐색하는 과정을 진행하기 때문에 $O(N^2)$이다.
하지만, 이를 개선하면 $O(NlogN)$만에 문제를 풀 수 있다.
그 방법은 이진 탐색을 활용하는 것이다.
이진 탐색을 활용하면 자신보다 앞에 있는 수 중 자신보다 작은 수에 대해 탐색하는 과정을 줄일 수 있기 때문이다.
하지만, 조금 의아한 부분이 존재할 것이다.
자신보다 작은 수를 찾는다고 하더라도 꼭 그 수가 가장 긴 증가하는 부분 수열 중 가장 긴 수를 가지는 게 보장되지 않기 때문이다.
여기서 약간의 트릭이 필요하다.
각 길이의 수에 대해 마지막에 나온 수를 알고 있다고 생각해보자.
예를 들어.
6
10 20 10 30 20 50일 때, 30에 대해 연산을 진행 중이라 하면 LIS는 {10, 20, 30}이 될 것이다.
왜냐하면, 30을 더하기 이전에 LIS는 {10, 20}이었기 때문이다.
이때 30은 자신이 들어갈 위치를 이진 탐색을 통해 찾을 수 있다.
{10, 20}에서는 자신보다 작거나 같은 수가 없기 때문에 마지막에 삽입이 되어야 한다.
만약, 이전 LIS가 {10, 20, 40}이었다면 40이 있는 위치에 30이 들어가는 게 맞다.
즉, {10, 20, 30}으로 LIS가 바뀌게 된다는 것이다.
이를 갱신하는 이유는 30보다 크거나 같은 가장 빨리 나오는 숫자를 30으로 갱신하는 것이 LIS를 구성하는데 유리하기 때문이다.
만약, LIS가 {10, 20, 30}인 상황에서 50을 추가한다고 생각해 보자.
50보다 크거나 같은 수는 없다.
따라서, 30 뒤에 50을 추가하여 {10, 20, 30, 50}이 LIS가 된다.
이러한 로직이 올바르게 동작하는 이유는 LIS는 자신보다 작은 수들이 몇 개나 순서대로 존재하는지를 세면 되기 때문이다.
정리하자면, 이러한 로직에 최적화된 lower_bound를 사용하여 현재까지 구성한 LIS에서 자신이 들어갈 위치를 찾은 뒤 자신의 위치가 가장 뒤라면 LIS의 길이를 증가시키면 된다.
전체 코드
#include <bits/stdc++.h>
using namespace std;
int N;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout << fixed;
cout.precision(4);
cin >> N;
vector<int> nums(N);
vector<int> LIS(N, 0);
for (int i = 0; i < N; i++)
{
cin >> nums[i];
}
int len = 0;
for (int i = 0; i < N; i++)
{
int pos = lower_bound(LIS.begin(), LIS.begin() + len, nums[i]) - LIS.begin();
LIS[pos] = nums[i];
if (pos + 1 > len) len++;
}
cout << len;
return 0;
}
