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

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

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

---

1. Logic

이전 가장 긴 증가하는 부분 수열 문제에서는 DP를 사용해서 풀었다. DP를 사용하는 풀이에서는 전체를 돌면서 확인 하며 메모이제이션 했기때문에 시간복잡도가 O(N^2)이었다. 하지만 이 문제에서는 입력값이 엄청 많기 때문에 N^2으로 풀지 못하기 때문에 시간복잡도가 O(nlogn)을 가지는 이분탐색 기반으로 풀어야 한다.

 

binary search를 구현해서 푸는 방법과 C++의 STL에 있는 lower_bound를 사용해서 풀이하는 방법이 있다.

 

binary Search를 사용하여 구현하는 방법은

1. 먼저 각 인자별로 lis(가장 긴 증가하는 부분수열)는 무조건 자기 자신이 있기 때문에 1이다. 그래서  cnt를 1로 맞춰준다.

2. 0번째 인덱스는  이미 넣어줬기 때문에 1부터 for문을 돌며 확인한다. 여기서 부분문제를 나눌 수 있는데 

  1)  lis중 가장 마지막 인자보다 탐색하는 인자(input[i])가 큰경우 : lis이기 때문에 lis배열에 push하고 cnt++

  2)  lis중 가장 마지막 인자보다 탐색하는 인자가 작은경우 : 이분탐색으로 현재 탐색하는 값보다 크거나 같은 값을 가진 인덱스를 찾고 해당 인덱스에 넣는다.

 

2번이 약간 이해하기 어려울텐데 예시를 들어서 설명해 볼것이다.

input이 10 20 30 21 27이라고 가정했을 때

10 20 30 까지는 자연스럽게 이해가 갈 것이다. 여기서 21이 문제인데 21을 마주친 순간 if문에 들어가서 이분탐색을 돌 것이다. 이분탐색으로는 21이라는 값보다 같거나 큰 값들중에서 가장 작은 값을 찾을것이다. 여기서 30이 선택된다. 그리고 현재 lis배열에는 {10, 20, 30}이 들어가 있는데 binarySearch를 돌며 1이 반환된다. 이 반환된 값은 lis의 인덱스를 나타내는데, 이 인덱스를 가진 값에 현재 우리가 탐색한 21을 넣어준다.

그이유는 이 문제에서는 lis의 최장 길이를 구하는 것이 목표이다. 현재까지는 10, 20, 30 을 찾아 3이 정답인데 앞으로의 상황을 봤을 때 30자리에 21을 넣는게 그 다음 나올 27을 선택하여 lis가 {10, 20, 30}이 아닌 {10, 20, 21, 27}로 길이 4가 나오는게 더 적합한 상황이기 때문이다.

요약하자면 나중을 생각해서 가능한 범위내에서 더욱 작은 숫자를 선택하여 바꿔주는것이다.

한가지 주의할 점은 lis배열은 최장수열은 맞지만 안에있는 인자가 항상 lis를 구성하는 원소는 아니다. 반례를 살펴보자면

10 20 30 18 17이 그 예인데 순서대로 써보면

10 20 30

10 18 30

10 17 30

lis의 길이는 3이 맞지만 나중에 어떤 숫자가 나올지 모르기 때문에 20을 계속 작은 숫자로 바꿔줬기 때문에 lis를 구성하는 원소는 아니라는 것이다.

---

2. Code

1. Binary Search를 구현한 풀이

#include<bits/stdc++.h>

using namespace std;

int n;
vector<int> input;
vector<int> lis;

int binarySearch(int key) {
    int start = 0;
    int end = lis.size() - 1;

    int mid;

    while(start < end) {
        mid = (start + end) / 2;
        if(key > lis[mid]) {
            start = mid + 1;
        }
        else {
            end = mid;
        }
    }
    return end;
}

void solve() {
    int cnt = 1;
    lis.push_back(input[0]);

    for(int i = 1; i < n; i++) {
        if(lis.back() < input[i]) {
            lis.push_back(input[i]);
            cnt++;
        }
        else {
            int idx = binarySearch(input[i]);
            lis[idx] = input[i];
        }
    }
    cout << cnt;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;

        input.push_back(a);
    }

    solve();
}

2. lower_bound를 사용한 풀이

#include<bits/stdc++.h>

using namespace std;

int n;
vector<int> arr;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;

    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;
        if(arr.empty() || arr.back() < input) {
            arr.push_back(input);
        }
        else {
            *lower_bound(arr.begin(), arr.end(), input) = input;
        }
    }
    cout << arr.size();
}

---

3. Feedback

lis배열에 넣고 계속 변환한 숫자가 왜 항상 lis를 구성하는 원소가 아닌지 이해가 잘 안가서 알아내느라 빡셌다. 다음 문제인 가장 긴 증가하는 부분 수열 3, 4, 5는 보지 않고 풀어봐야겠다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐