BOJ 가장 긴 증가하는 부분 수열

이 문제 시리즈는 출력 값이 길이만 출력하는지, 긴 수열 또한 출력해야 하는지에 따라 풀이 방법이 달라지고, n 조건에 따라 풀이 방법이 달라진다.

 

1 단계 O(n^2), 가장 긴 수열의 길이만 출력

 

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

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

이 문제는 입력 조건 n 의 크기에 따라 풀이 방법이 달라지고, 먼저 11053 번 문제는 n 조건이 1000 까지 이므로 n^2 만에 풀이 가능하며, 이전 배열값을 다시 참조하면서, 가장 긴 값을 저장하면 된다.

 

#include<cstdio>
#include<algorithm>
using namespace std;
int n, arr[1001],cnt[1001],ans=1;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    for (int i = 0; i < n; i++) {
        cnt[i] = 1;
        for (int j = i - 1; j >= 0; j--) {
            if (arr[i] > arr[j]) {
                cnt[i] = max(cnt[i],cnt[j]+1);
                ans = max(ans, cnt[i]);    
            }
        }
    }
    printf("%d", ans);
    return 0;
}

 

 

2 단계 O( n log n), 가장 긴 수열의 길이만 출력

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

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

 두 번째 문제는 1 단계 문제와 같이 길이만 출력하지만, n의 조건이 크기 때문에 O(N^2)만에 해결할 수 없다. 따라서 이 문제는 1번 문제 풀이에서 가장 긴 수열의 길이를 탐색해가는 과정을 log n으로 줄여야 풀 수 있다. 

 풀이 방법은 하나의 벡터를 정의하여, 가장 마지막 값이 현재 탐색하는 값보다 클 경우 이진 탐색을 통해 현재 탐색 값이 들어갈 위치를 찾아 수정한다. 주의할 점은 이렇게 풀었을 때, 정의한 벡터 안의 값이 가장 긴 부분 수열이라고 보장하지 않는다.

 

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int n, arr[1000001];
 
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d", &arr[i]);
    }
 
    vector<int> ans;
    ans.push_back(arr[0]);
    for(int i=1;i<n;i++){
        if(ans.back() < arr[i]){
            ans.push_back( arr[i] );
        } else {
            vector<int>::iterator it = lower_bound(ans.begin(), ans.end(), arr[i]);
            *it = arr[i];
        }
    }
    printf("%d", ans.size());
    return 0;
}

 

 

 

3단계, O(N^2) 수열까지 출력

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

14002번: 가장 긴 증가하는 부분 수열 4

이 문제는 가장 긴 수열의 길이와 더불어 긴 수열까지 모두 출력해야 한다. 위에서 말했듯이 2단계 풀이로는 가장 긴 수열이라고 보장하지 않기 때문에 풀 수 없다. 다행히 이 문제는 다시 n 조건이 작아 졌기 때문에, 각 배열 값을 참조하면서 현재까지 가장 긴 수열들을 모두 저장할 수 있다.

 

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int n, arr[1001], len[1001];
 
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d", &arr[i]);
    }
 
    vector<int> ans[1001];
    int ans_idx = 0, ans_len = 1;
    for(int i=0;i<n;i++){
        len[i] = 1;
        for(int j=i-1; j >= 0; j--){
            if(arr[i] > arr[j] && len[i] < len[j] + 1){
                len[i] = len[j] + 1;
                ans[i].clear();
                ans[i].insert(ans[i].end(), ans[j].begin(), ans[j].end());
                if(ans_len < len[i]){
                    ans_len = len[i];
                    ans_idx = i;
                }
            }
        }
        ans[i].push_back(arr[i]);
    }
    printf("%d\n", ans_len);
    for(int i=0;i<ans_len;i++){
        printf("%d ",ans[ans_idx][i]);
    }
    return 0;
}

 

 

 

4단계 O(n log n), 수열까지 출력

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

14003번: 가장 긴 증가하는 부분 수열 5

마지막은 n 조건도 커지고, 정답 수열까지 출력해야 하는 문제이다. 이 문제를 풀기 위해선 2번째 문제 풀이를 응용하여 lower_bound(이진탐색)으로 찾은 인덱스 값을 따로 저장해 풀 수 있다. 마지막 출력 시 뒤에서 부터 정답 수열 길이 값과 매칭되는 인덱스 값을 순차적으로 찾으며 출력하면 된다.

 

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int n, arr[1000001], idx[1000001], ans2[1000001];
 
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d", &arr[i]);
    }
 
    vector<int> ans;
    ans.push_back(arr[0]);
    idx[0] = 0;
    for(int i=1; i<n; i++){
        if(ans.back() < arr[i]) {
            ans.push_back(arr[i]);
            idx[i] = ans.size()-1;
        } else {
            vector<int>::iterator it = lower_bound(ans.begin(), ans.end(), arr[i]);
            *it = arr[i];
            idx[i] = distance(ans.begin(), it);
        }
    }
 
    printf("%d\n", ans.size());
    for(int i = n-1, len = ans.size()-1; i>=0 && len>=0; i--){
        if(idx[i] == len){
            ans2[len] = arr[i];
            len --;
        }
    }
 
    for(int i=0; i < ans.size(); i++){
        printf("%d ", ans2[i]);
    }
    return 0;
}

 

결국 4단계 풀이 방법만 기억하고 있으면, 모두 풀 수 있다.