각 i에 대해, i에서 끝나는 LIS를 찾는 문제이다.
즉 자기 포함 나한테서 끝나는 가장 긴 Subsequence의 길이를 계산하게 된다.
O(N^2)
#include <iostream>
int main(void)
{
int n = 0;
cin>>n;
int input[n];
int dp[n];
for(int i=0; i<n; i++)
{
cin>>input[i];
}
// 첫 글자는 1로 초기화
dp[0] = 1;
for(int i=0; i<n; i++)
{
// 자신 밖에 없는 경우 자신의 길이인 1을 할당하기 위한 초기값
int maxLength = 1;
for(int j=0; j<i; j++)
{
// 내 앞에 있는 숫자 중 나보다 작은 숫자이면
if(input[j] < input[i])
maxLength = max(maxLength, dp[j]+1);
}
dp[i] = maxLength;
}
}O(NlogN)
- 입력 배열의 첫번째 인덱스의 값은 dp배열에 바로 할당하여 초기화해준다.
이후 로직
1) 입력배열을 순회한다.
2) 이번에 만난 숫자가 dp배열의 마지막 값보다
- 크면 dp배열의 마지막 값 뒤에 넣어준다.
- 작으면 이분탐색으로 자리를 찾아준다.
int dp[n];
int input[n];
int start, end;
cur = 1;
end = 0;
dp[0] = input[0];
while(cur<n)
{
// 현재 값이 dp배열의 마지막 값보다 크면
if(input[cur] > dp[end])
{
// dp 배열 마지막에 현재 값을 넣어줌
dp[end+1] = input[cur];
end++;
}
// 현재 값이 dp배열의 마지막 값보다 작으면
else
{
// 이분탐색으로 현재 값이 들어갈 수 있는 자리를 찾아줌
int idx = binary_search(0, end, input[cur]);
dp[idx] = input[cur];
}
// 다음 값 조회
cur++;
}
// 마지막 idx에 1 더해서 길이를 구함
cout<<end+1; 배열을 한 번만 순회하면서
Lis 배열에 값을 추가하거나, 이분탐색을 통해 자리를 찾아주는 일만 하므로
시간 복잡도는 O(NlogN)이다.
수열 길이와 수열의 값을 NlogN으로 찾기
같은 길이를 가지는 수열이 여러 개 있을 때 해당 수열들의 마지막 값들을 모아보면 값이 점점 작아지는 패턴이다. 왜냐하면 만약 마지막 값이 더 컸다면 같은 길이를 가지지 않고 더 큰 길이를 가지게 될 것이기 때문이다.
3 1 2 6 5 8 3 9 1
예를 들어 위와 같은 배열이 있다고 했을 때
input[4] = 5에서 끝나는 LIS는 길이 3으로 1 2 5이다.
또한 input[6] = 3에서 끝나는 LIS는 길이 3으로 1 2 3이다.
이처럼 길이가 같은 두 LIS 수열을 모아놓으면 그 마지막 값은 점점 작아지는 패턴이다.
여기에서는 더 긴 최장 증가 부분 수열을 찾는 것이 목표이므로
같은 길이 중 더 작은 값만 기억하면 된다.
왜냐하면 3을 기억할 경우 이후에 3보다 큰 값만 나오면 길이 4인 수열을 만들 수 있는데
최소가 아닌 5를 기억할 경우 이후에 5보다 큰 값이 나와야 길이 4인 수열을 만들 수 있으므로 더 손해이기 때문이다.
그래서 다음과 같은 배열도 만들 수 있다.
인덱스가 수열의 길이이고, 값은 해당 수열의 마지막 값을 의미한다.
ex. arr[5]=8
길이 5인 수열의 마지막 값이 8임을 의미
따라서 이후에 8보다 큰 값만 나오면 길이 6인 수열을 만들 수 있다.
그리고 각 인덱스(수열 길이)에 대한 수열의 마지막 값을 기록하기 때문에
길이 뿐 아니라 전체 수열을 찾을 수 있다.
위와 같은 상태에서
배열을 순회하다가 또 다시 길이가 6인 수열을 찾게 되면
12를 해당 수열의 마지막 값으로 바꾸면 된다.
같은 길이인 경우 그 마지막 값이 점점 작아지는 패턴이므로 12보다 더 작은 값이 나왔을 것이기 때문이다.
참고
