[C++] 백준/BOJ - 12015 : 가장 긴 증가하는 부분 수열 2

문제 이해 단계

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

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

수열 A가 주어졌을 때,
가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에
가장 긴 증가하는 부분 수열은 A = {10, 20 30,50}이고, 길이는 4이다.

 

---

문제 접근 단계

---

특이점 알아내기

가장 긴 ~ 부분 수열 시리즈 문제
항상 비슷하면서 풀이가 다른 게 해당 시리즈 특징이다.

일단 수열을 고를 때 연속성이 없는 거 빼고는 딱히 특징이 없어 보인다.

일단 제한사항부터 살펴보자.
수열의 개수 N과 크기는 최대 1,000,000까지다.
여기서 얻을 수 있는 것을 생각해 보자.

이 시리즈 바로 전 문제인 가장 긴 증가하는 부분 수열 1에서 이 문제를 DP로 해결했다.
해당 방식은 아래에 링크를 달아두겠다.

https://howudong.tistory.com/47

[C++] 백준 11053 - 가장 긴 증가하는 부분 수열

그때는 이중반복문을 사용했기 때문에 시간복잡도가 O(N^2)이 나왔다.

하지만 여기서는 수열의 최대 개수가 10^6개이므로,
O(N^2)을 하면 10^12으로 시간초과가 뜬다.

따라서 DP 방식 말고 다른 방식으로 이 문제를 해결해야 한다.

---

부분 수열의 길이를 효과적으로 늘리는 방법

우리가 구해야 하는 것은 가장 긴 증가하는 부분 수열이다.
즉, 어떻게 하면 효과적으로 길이를 늘일 수 있을까?

바로 이전에 있는 수보다 커야 하는 것은 당연하다.
또 하나는 바로 이전에 있는 수보다 큰 차이가 나지 않는 것이다.

이게 무슨 말이냐면,
만약 수열이 {10,20,11,…} 이 있다고 생각해 보자.

뒤에 어떤 수열이 들어올지는 모른다.

일단 첫 번째로 10을 고를 수 있고, 그다음에는 20과 11 둘 다 올 수 있다.

근데 뒤에 뭐가 올 줄 모르는 상황에서 어떤 수를 넣어야 할까?
당연히 11을 넣어야 한다.

11을 넣으면 그 뒤에 선택할 수 있는 숫자의 폭이 넓어진다.
11을 10 뒤에 넣는 근거는, 10보다 크지만 절댓값 차가 적기 때문이다.

이를 일반화해 보면 어떤 숫자를 수열에 넣는다고 하자.

그 수열에서 해당 숫자보다 작긴 하지만,
절댓값 차이가 많이 나지 않는 숫자 바로 앞에 배치해야 한다.

37을 현재 완성되어있는 수열에 넣는다고 가정

---

탐색하는 방법

그런데 위 그림과 같이 수열에 숫자가 여러 개 들어있을 때는 절댓값 차이가 얼마 나지 않는다.

절댓값 차이가 얼마 나지 않는 숫자를 찾기 위해
현재 가장 긴 수열을 이루고 있는 원소를 탐색해야 한다.

여기서는 개수가 5개여서 빠르지만
1,000,000개에서 찾을 경우엔 많은 시간이 걸릴 것이다.

게다가 탐색을 모든 입력에 대해 진행해야 하기 때문에
일반적으로 탐색하면 시간초과가 뜰 것이다.

그래서 수열이 증가하는 방향으로 나열된다는 점,
즉 오름차순으로 정렬된다는 점을 이용한다.

정렬되어 있을 때만 사용할 수 있는 탐색법인,
이분 탐색을 이용하여 시간복잡도를 log(N)으로 줄인다.

그래서 이 문제의 시간 복잡도를 Nlog(N)까지 줄일 수 있다.

요약하자면, 이 문제의 핵심은 2가지이다.

1. 증가하는 부분 수열을 최대한 작은 수로 구성하는 것
2. 탐색을 이분 탐색으로 진행하는 것

이제 이를 문제 구현 단계에서 코드로 살펴보겠다.

 

---

문제 구현 단계

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int arr[1000001] = {0,};
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int N;
    vector<int> sequence; // 증가하는 부분 수열을 담을 벡터

    cin >> N;
    for(int i = 0; i < N; i++) cin >> arr[i];

    sequence.push_back(arr[0]); // 가장 첫 숫자를 넣어줌

    // 전체 배열을 훑음
    for(int i = 1; i < N; i++){
        // 증가하는 부분 수열의 가장 큰 수(끝에 있는 수)보다 큰 경우
        if(sequence.back() < arr[i]) sequence.push_back(arr[i]); // 길이 추가
        else{
            // 그렇지 않은 경우 lower_bound(이분탐색)을 통해 arr[i]보다 같거나 큰수의 인덱스를 찾음
            auto it = lower_bound(sequence.begin(),sequence.end(),arr[i]);
            sequence[it-sequence.begin()] = arr[i]; // 그 수를 arr[i]로 바꿈
        }
    }
    cout << sequence.size(); // sequence의 길이가 정답
}

코드는 상당히 짧다.
이분탐색을 할 때 lower_bound라는 함수를 써줬기 때문이다.

lower_bound를 통해 그 벡터의 원소 중에서
arr [i]와 같거나 큰 원소가 최초로 나오는 인덱스를 반환한다.

물론 이를 사용하기 위해서는 벡터가 오름차순 정렬되어있어야 한다.
lower_bound의 탐색은 이분 탐색의 원리기 때문에 가능했다.

만약 arr [i]가 10이라면, 벡터에서 10보다 크거나 같은 수를
10으로 바꾸는 것이 길이를 더 길게 하는데 이득이 된다.

이와 같은 원리로 반복을 하면 된다.
문제 풀이는 여기까지이고 이제 풀이를 마치겠다.

 

---

시행착오

처음에는 DP로 풀었다가
시간초과가 떠서 더 이상 방법이 생각이 안 났다.
DP로 계속 풀면서 시간을 줄일 방법만 떠올리다가
시간이 너무 지나버려서 인터넷을 참고했다.

이 방법은 듣지도 보지도 못한 방법이어서 너무 신기하다.
이걸 어떻게 떠올리지

많이 해보는 수밖에 없을 것 같다.

https://toss.me/howudong

howudong님에게 보내주세요