볼 때마다 뭐였더라...를 시전하고 있는 LIS 알고리즘에 대해 작성해보려고 한다.
LIS?
- 최장 증가 부분 수열(
Longest Increasing Subsequence)을 말한다. 부분 수열: 수열에서 일부를 선택해서 만들어진 수열, 당연히 원본 순열에서의 순서는 유지해야 한다.원본 수열: [2, 3, 4, 1, 6, 5] 부분 수열: [2], [3], [4], [1], [6], [5] [2, 3], [2, 4], ..., [6, 5] [2, 3, 4], .... , [1, 6, 5] [2, 3, 4, 1] ..., [4, 1, 6, 5] [2, 3, 4, 1, 6], [3, 4, 1, 6, 5] [2, 3, 4, 1, 6, 5]- 위의 예시에서 증가하는 부분 수열은
[2, 3],[2, 3, 4][2, 3, 4, 6],[2, 3, 4, 5]등이 있고, 그 중 가장 긴 것은[2, 3, 4, 6],[2, 3, 4, 5]이다. - 일반적으로 LIS의 길이만을 구하는 경우가 많다.
- 당연하지만 직접적으로 주어지지 않고 응용되어 나오기 때문에 이 문제가 LIS 문제구나! 하고 알아채는 것이 어렵다.
how?
이 알고리즘이 어려운 이유는 예제를 보고 답을 도출하기는 쉽지만, 방금 본인이 어떻게 풀었는지 말로 설명하기가 어렵기 때문이다. [2, 3, 4, 1, 6, 5]가 주어졌을 때 한번 훑어보면 LIS의 길이가 4인걸 알 수 있는데, 방금 내 뇌에서 무슨 일이 일어났는지 모르겠다.
일단 처음 생각나는 가장 간단한 방법은 백트래킹으로 증가하는 부분 수열을 모두 구하며 길이의 최댓값을 갱신하는 것이다. 그러나 이 방법은 시간초과가 날 가능성이 높다. 우선 시간복잡도가 O(2^n)...
보통 이렇게 어떻게 시작해야 할지 모르겠는 경우는 처음부터가 아니라 중간부터 생각을 해보면 좋다. 이미 선택된 부분 수열이 있다고 가정해보는 것이다. 그 이후의 선택을 위해서 필요한 정보는 사실 마지막으로 온 숫자 하나 뿐이다. 이미 선택된 부분수열로[3, 4], [2, 3, 4], [4] 가 주어져있을 때, 이후의 선택은 4보다 크게 시작하는 가장 긴 증가하는 부분수열로 모두 같다. 앞이 무슨 숫자로 선택되었는지 중요하지 않다. 따라서 전체 부분 수열의 길이는 4로 끝나는 부분 수열 + 4보다 큰 숫자로 시작하는 부분 수열이 된다. 혹은 4를 아예 포함하지 않거나. 뭔가 점화식을 세울 수 있을거 같다...!
sol1. DP - O(n^2)
LIS의 원본 수열에서 중복되는 수는 얼마든지 있을 수 있기 때문에, 원소의 값이 아니라 인덱스를 이용해서 나타내보자면,
전체 LIS = MAX(arr[i]를 선택하지 않는 경우,
arr[i]로 끝나는 LIS + arr[i+k]로 시작하는 LIS)이 때 k>0, arr[i] < arr[i+k]를 만족해야 한다.
그렇다면 인덱스 i 까지의 LIS는
i까지의 LIS = MAX(arr[i]를 선택하지 않는 경우, arr[i]로 끝나는 LIS)
= MAX(i-1까지의 LIS, arr[i]로 끝나는 LIS)i-1까지의 LIS는 이전에 구했던 값을 사용하면 되고, arr[i]로 끝나는 LIS는 어떻게 구할 수 있을까? 우선 arr[i]를 선택하기 위해서는 arr[i]보다 작은 arr[k]로 끝나는 부분 수열을 찾아야 한다. 따라서 arr[k]로 끝나는 LIS + arr[i]가 arr[i] 로 끝나는 LIS이다.
dp[i]가 i까지의 LIS 길이라고 한다면,
dp[i] = max(dp[i-1],
j는 0부터 i-1까지 arr[i] < arr[j]를 만족하는 가장 큰 값 + 1이다.
정리를 하려고 하는데 왜 더 어려워지는지 모르겠다.
코드로 말하자면
int size = 6;
int arr[] = {2, 3, 4, 1, 6, 5};
int dp[size] = {0, };
// 초기 값(dp[0]은 1이다. 선택하면 0, 안하면 1이니까 그 중에 큰건 1)
dp[0] = 1;
for (int i = 1; i < size; i++) {
int tmp_max = 0;
for (int j = 0; j < i-1; j++){
if (arr[j] < arr[i]) tmp_max = max(tmp_max, dp[j]);
}
dp[i] = max(dp[i-1], tmp_max + 1);
}2중 반복문이 들어가므로 시간복잡도는 O(N^2)이다.
시간을 좀 더 줄일 수 있는 방법이 있다.
sol2. 이분탐색 (Binary Search)
현재 우리가 알아야 하는건 LIS의 길이 뿐이다. 그렇다면 위에도 나왔지만, 중요한 건 끝나는 숫자 뿐이다!! 따라서 다음으로 나오는 방법은 끝나는 숫자를 저장하는 방법이다. 즉, last_digit[i] = 길이가 i인 증가 부분 수열의 마지막 원소를 갱신하면서 탐색하는 것이다. 길이가 i인 증가 부분 수열을 어떻게 알 수 있을까?
원소를 기준으로 생각하면, 내가 들어갈 수 있는 가장 뒷 자리에 들어간다면, 가장 긴 부분 수열의 마지막 자리에 들어갈 수 있다. 예를 들어보자.
각 열은 서로 다른 증가 부분 수열이라고 생각하면 편하다. 현재 LIS의 후보는
[1]
[?, 3]
[?, ?, 5]이렇게 세가지가 있는 것이다.
여기서 두가지 경우의 수가 있다.
- case 1 > 다음 원소로 6이 오는 경우
이 경우는 쉽다. 길이가 3인 증가 부분 수열을 선택한 후, 6을 뒤에 덧붙이면 된다. 따라서 길이 4인 부분 증가 수열이 새롭게 만들어진다.last_digit[4] = 6
- case 2 > 다음 원소로 2가 오는 경우
이 경우 2가 선택할 수 있는 부분 수열 중 가장 긴 것은[1]이다.
길이 2인[1, 2]가 새롭게 만들어졌다. 그런데 길이가 3인 증가 부분 수열[?, 3]이 이미 존재한다. 어느 것이 더 이득인가? 당연히 같은 길이라면 끝나는 숫자가 작은 것이 이득이다. 만약 뒤에 3가 있다고 가정해보자.[1, 2]를 선택할 경우 이어 붙여서 길이가 3인 수열로 만들 수 있다. 따라서, 새롭게 만들어진 부분수열을 채택한다.last_digit[2] = 2
정리하자면, 각 원소별로 last_digit[pos] < arr[i]를 만족하는 pos중 가장 큰 값을 선택하여 last_digit[pos+1] = arr[i]를 해주면 된다.
아까 dp랑 별로 다르지 않은거 같다고 생각할 수 있으나, arr[0]부터 계속 위와 같이 끼워넣고 있었기 때문에 last_digit에 있는 숫자들은 정렬되어 있다. 이분 탐색은 O(log N)만에 위치를 구할 수 있으므로, 전체 시간 복잡도는 O(Nlog N)가 된다.
이분탐색을 직접 구현해서 pos를 찾을 수도 있겠으나, lower_bound 개념을 알고 있다면 그럴 필요가 없다. last_digit에서 arr[i]의 lower_bound가 정의상 pos + 1이 되기 때문이다.
lower_bound(first, last, x): 찾고자 하는 x 이상이 처음 나오는 위치를iterator로 반환, 만약x이상의 수가 없다면 마지막 위치(last)를 반환
#include <algorithm> //lower_bound
#include <vector>
int size = 6;
int arr[] = {2, 3, 4, 1, 6, 5};
vector<int> last_digit;
for (int i = 0; i < size; i++) {
auto pos = lower_bound(last_digit.begin(), last_digit.end(), arr[i]);
if (pos == last_digit.end()) last_digit.push_back(arr[i]);
else *pos = arr[i];
}reference
