14003번: 가장 긴 증가하는 부분 수열 5
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)
www.acmicpc.net
이번 문제는 유명한 LIS(Longest Increasing Subsequence)유형의 문제이다.
보통 이러한 문제는 브루트 포스(완전탐색)으로 풀면 시간초과가 나도록 조건이 주어지는 것 같다.(알고리즘 대회나 코딩 테스트에서 항상 그랬던 것으로 기억된다.)
나는 이 문제를 다이나믹 프로그래밍을 배울 때 처음 풀었던 것 같다.
그런데 다이나믹 프로그래밍으로 푼다고 해도 O(N^2)의 시간복잡도를 갖기 때문에 전체 수열의 크기가 크게 주어진 경우 제한 시간안에 해결할 수 없다.
따라서 O(NlogN)의 시간복잡도를 갖는 방법을 써야한다.
이 방법에 이분 탐색을 이용하는 방법, 세그먼트 트리를 이용하는 방법(사실 이건 잘 모른다)이 있다.
나는 이 문제를 이분탐색을 이용하여 해결하였다.
이분 탐색으로 푸는 방법은 이러하다.
만약 전체 수열이 10, 20, 30, 15, 10, 40, 25 로 주어졌다고 하자.
주어진 수열을 0번지부터 보면서 새로운 배열 L 에서 이분탐색을 통해 자신보다 크거나 같은 수가 있으면 자신으로 변경해준다.
1. 처음에는 빈 배열 L 이기 때문에 10을 채워준다.
10, 20, 30, 15, 10, 40, 25
| 10 |
2. 20을 배열 L에서 이분탐색을 통해 20보다 크거나 같은 수를 찾는다. 그런 수가 없기 때문에 맨 끝에 자기 자신을 채워준다.
10, 20, 30, 15, 10, 40, 25
| 10 | 20 |
3. 30을 배열 L에서 이분탐색을 통해 30보다 크거나 같은 수를 찾는다. 그런 수가 없기 떄문에 맨 끝에 자기 자신을 채워준다.
10, 20, 30, 15, 10, 40, 25
| 10 | 20 | 30 |
4. 15를 배열 L에서 이분탐색을 통해 자기 자신보다 크거나 같은 수를 찾는다. 1번지의 20의 위치에 자기 자신을 채워준다.
10, 20, 30, 15, 10, 40, 25
| 10 | 30 |
5. 10을 배열 L에서 이분탐색을 통해 자기 자신보다 크거나 같은 수를 찾는다. 0번지의 10의 위치에 자기 자신을 채워준다.(바꾸지 않아도 되지만 조건문을 하나 빼려면 그냥 바꿔도 된다.)
10, 20, 30, 15, 10, 40, 25
| 15 | 30 |
6. 40을 배열 L에서 이분탐색을 통해 자기 자신보다 크거나 같은 수를 찾는다. 그런 수가 없기 때문에 맨 끝에 자기 자신을 채워준다.
10, 20, 30, 15, 10, 40, 25
| 10 | 15 | 30 | 40 |
7. 25을 배열 L에서 이분탐색을 통해 자기 자신보다 크거나 같은 수를 찾는다. 3번지의 30의 위치에 자기 자신을 채워준다.
10, 20, 30, 15, 10, 40, 25
| 10 | 15 | 40 |
전체 배열을 돌고 나면 최장 부분 수열의 길이가 4임을 알 수 있다.
하지만 실제 최장 수열은 10, 20, 30, 40 이지만 배열 L에는 10, 15, 25, 40이 들어있다.
이렇듯 최장 부분 수열의 길이를 배열 L을 통해 알 수 있지만, 그 부분 수열이 무엇인지는 이 배열 L 문으로 알 수가 없다.
따라서 추가적으로 tracking(?)을 해주어야하는 문제이다.
이분탐색으로 푸는 방법은 코드가 간단하기도 하고 몇번 풀어본적이 있기때문에 어렵지 않게 생각하고 풀고 제출했다.(이때는 tracking을 생각하지 않았다.)
아무생각없이 코딩을 하니까 3번이나 틀렸다. 사실 저 때는 무엇이 문제인지 파악도 제대로 못했다.
그 뒤에 tracking이 따로 필요하다는 것을 깨달았다.
진짜 처음 생각할 때는 감도 못잡았는데 막상 아이디어를 생각하니 생각보다 간단했다.
이분탐색을 통해 배열 L에서 업데이트 시켜줄 index를 찾아 따로 check 배열을 만들어 저장해 주었다.
만약 위의 예시의 경우에는
| 0 | 1 | 2 | 1 | 0 | 3 | 2 |
이 될 것이다.
전체 수열에 대해서 위에서 설명한 방법을 적용 후 check 배열을 뒤에서부터 보면서 tracking을 해준다.
맨 뒤부터 보면 최장 수열의 길이는 4이기 때문에 index상으론 배열 L의 끝은 3이다.
따라서 check 배열을 뒤에서부터 보면서 업데이트 되는 index가 3부터 역순이 되도록 해야한다.(내가 봐도 무슨 소린지 모르겠다.)
자세한 방법을 표로 보자.
1. check 배열 맨 뒤부터 보면 2이다. 아직 3이 나오지 않았으니 넘어간다.
| 0 | 1 | 2 | 1 | 0 | 3 | 2 |
2. check 배열에서 3이 최초로 발견되었다! 이 3이 저장될 때의 전체 수열에서의 값은 40이다. vector(또는 stack도 가능)에 40을 넣어준다.
| 0 | 1 | 2 | 1 | 0 | 3 | 2 |
3. check 배열에서 0이 발견되었다. 현재 찾고있는 건 2이다. 넘어간다.
| 0 | 1 | 2 | 1 | 0 | 3 | 2 |
4.마찬가지로 2가 아니기 때문에 넘어간다.
| 0 | 1 | 2 | 1 | 0 | 3 | 2 |
5. 마침내 2가 처음 나왔다. 이때의 수열은 30이다. vector에 30을 넣어준다.
| 0 | 1 | 2 | 1 | 0 | 3 | 2 |
6. 마침내 1이 처음 나왔다. 이때의 수열은 20이다. vector에 20을 넣어준다.
| 0 | 1 | 2 | 1 | 0 | 3 | 2 |
7. 마침내 0이 처음 나왔다. 이때의 수열은 10이다. vector에 10을 넣어준다.
| 0 | 1 | 2 | 1 | 0 | 3 | 2 |
8. 현재 vector에는 40 30 20 10 순으로 들어갔고 뒤에서부터 빼면서 출력한다.
업데이트가 일어난 index를 역순으로 찾는데 그 index를 마지막으로 업데이트 시킨 수열을 찾는다. 라고 말할 수 있겠다.
글로는 이해가 잘가지 않지만 예시를 하나하나 따라가면 이해가 되..길 바란다.
(코드를 정리하지 않았기때문에 조금 이상할 수 있지만 나는 이렇게 했다!.)
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int check[1000001];
int arr[1000001];
vector<int>v;
int max_cnt =0;
int main(){
int n,cnt = 0;
scanf("%d",&n);
for(int i=0; i<n; i++){
scanf("%d",&arr[i]);
auto it = lower_bound(v.begin(), v.end(), arr[i]) - v.begin();
check[i]=it;
if(it + v.begin() == v.end()){
v.push_back(arr[i]);
cnt++;
}
else{
v[it] = arr[i];
}
}
printf("%d\n",cnt);
vector<int>ans;
for(int i=n-1; n>=0; i--){
if(cnt < 1)break;
if(check[i]==cnt-1){
ans.push_back(arr[i]);
cnt--;
}
}
while(!ans.empty()){
printf("%d ",ans.back());
ans.pop_back();
}
return 0;
}
정리에 미흡한 점도 많고 알고리즘을 잘하지 않기때문에 오류가 있을 수 있습니다.
일기처럼 생각을 정리하려고 사용하는 목적이기 때문에 너그럽게 봐주십쇼. 피드백은 언제나 환영입니다.
감사합니다.
'알고리즘문제' 카테고리의 다른 글
| 백준 1167(트리의 지름) (0) | 2021.01.30 |
|---|