[LIS(Longest Increasing Subsequence)] 개념과 예제 문제: LIS 1_백준(O(n^2)), LIS 2_백준(O(nLogn))
알고리즘(Algorithm)
부분 수열
길이가 n인 수열이 있다.
이 수열의 부분 수열이란 이 수열을 구성하는 수의 순서는 유지한 채 몇 개의 수를 제거해서 얻을 수 있는 수열들을 의미한다.
예를 들어 1 3 2 4 라는 수열의 부분 수열은 다음과 같다.
1
3
2
4
1 3
1 2
1 4
3 2
3 4
2 4
1 3 2
1 3 4
1 2 4
3 2 4
1 2 3 4
LIS
LIS(Longest Increasing Subsequence)는 말 그대로 해석하면 가장 긴 증가하는 부분 수열이다.
1
3
2
4
1 3
1 2
1 4
3 2
3 4
2 4
1 3 2
1 3 4 <= LIS
1 2 4 <= LIS
3 2 4
1 3 2 4
예제 문제: LIS1_백준
수열의 크기가 최대 1,000 이다. 점화식을 사용하는 바텀업 방식 또는 재귀+메모제이션 기법을 사용하는 탑다운 방식 모두 시간 제약 통과 가능하다.
1. (탑다운) DFS + 메모제이션 방식 사용
시간 복잡도 O(N^3)의 풀이에서 메모제이션을 적용한 것과 같다.
#include <iostream>
#include <vector>
using namespace std;
int N;
vector<int> Arr(1000000);
vector<int> DP(1000000, 0);
int DFS(int beforeIdx) {
// 메모제이션 활용
if (DP[beforeIdx] != 0)
return DP[beforeIdx];
// 탐색
int maxLen = 0;
for (int i = beforeIdx + 1; i < N; i++) {
int nowIdx = i;
if (Arr[beforeIdx] >= Arr[nowIdx])
continue;
maxLen = max(maxLen, DFS(nowIdx));
}
// 메모제이션
DP[beforeIdx] = 1 + maxLen;
return DP[beforeIdx];
}
int solution() {
int maxLen = 0;
for (int startIdx = 0; startIdx < N; startIdx++) {
maxLen = max(maxLen, DFS(startIdx));
}
return maxLen;
}
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> Arr[i];
}
int answer = solution();
cout << answer << endl;
return 0;
}2. 바텀업 방식
시간복잡도는 O(n^2)이다.
Sequence를 순차적으로 서칭.
현재 idx: nowIdx , 값: nowValue
DP를 채우는 조건, if(no
-> dp[nowValue] = max(dp[0~nowValue-1]);
위 dp를 채우는 과정을 계속해서 반복하면 된다.
이미 전에 채워진 dp는 그 의미가 idx가 전이었다는 의미.
#include <iostream>
#include <vector>
using namespace std;
int dp[1000+1];
// 바텀업 방식
int solution(int n, vector<int> vec){
int answer = 0;
for(int i=0; i<n; i++){
int nowNum = vec[i];
for(int j=nowNum-1; j >= 0; j--){
dp[nowNum] = max(dp[nowNum], 1 + dp[j]);
}
answer = max(answer, dp[nowNum]);
}
return answer;
}
int main(){
int n;
cin >> n;
vector<int> vec;
for(int i=0; i<n; i++){
int x;
cin >> x;
vec.push_back(x);
}
int answer = solution(n, vec);
cout << answer << '\n';
}최신 바텀업 풀이
또는 아래와 같이 값이 아닌 인덱스를 기준으로 풀이 가능
#include <iostream>
#include <vector>
using namespace std;
int N;
vector<int> Sequence(1000);
vector<int> DP(1000, 1);
int solution() {
int maxCnt = 0;
for (int i = 0; i < N; i++) {
int nowIdx = i;
int nowNum = Sequence[i];
for (int j = nowIdx - 1; j >= 0; j--) {
int beforeIdx = j;
int beforeNum = Sequence[j];
if (nowNum > beforeNum) {
DP[nowIdx] = max(DP[nowIdx], 1 + DP[beforeIdx] );
}
}
maxCnt = max(maxCnt, DP[nowIdx]);
}
return maxCnt;
}
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> Sequence[i];
}
int answer = solution();
cout << answer << '\n';
return 0;
}예제 문제2: LIS2_백준
시간 복잡도: O(N^2)로 해결 불가능 => O(NlogN) 필요
위 O(N^2)의 바텀업 풀이에서 D[i]를 계산하기위해 Seq[0] ~ Seq[i-1]을 모두 훑어보았다. Seq[i]보다 작은 A[j]들 중 가장 큰 D[j]를 찾기 위함이었다. 이 과정에서 추가적인 O(N)이 곱해지고, 결국 총 시간복잡도는 O(N^2)이 된다.
이를 O(logN)으로 해결하여 O(NlogN)으로 해결할 수 있다. 아래 참조로 달린 나무위키에서 확인할 수 있다.
#include <iostream>
#include <vector>
using namespace std;
int N;
vector<int> Sequence(1000000);
int solution() {
vector<int> DP; // 비어있는 벡터로 시작
int maxCnt = 0;
for (int i = 0; i < N; i++) {
int nowNum = Sequence[i];
if (DP.size() == 0) {
DP.push_back(nowNum);
maxCnt = max(maxCnt, 1);
continue;
}
if (DP[DP.size() - 1] < nowNum) {
DP.push_back(nowNum);
maxCnt = max(maxCnt, (int)DP.size());
continue;
}
// 이진 탐색
int start = 0;
int end = DP.size() - 1;
int lastIdx = -1;
while (start <= end) {
int mid = (start + end) / 2;
if (DP[mid] == nowNum) {
maxCnt = max(maxCnt, mid + 1);
lastIdx = mid;
break;
}
else if(DP[mid] > nowNum) {
lastIdx = mid;
// 좀더 큰 쪽으로 이동
end = mid - 1;
}
else {
start = mid + 1;
}
}
if (lastIdx != -1)
DP[lastIdx] = nowNum;
}
return maxCnt;
}
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> Sequence[i];
}
int answer = solution();
cout << answer << endl;
return 0;
}