[백준] 12015번 : 가장 긴 증가하는 부분 수열 2

문제

 

---

풀이

 

myunji.tistory.com/214

[백준] 11053번 : 가장 긴 증가하는 부분 수열

이 문제랑 똑같이 접근할 것이다.

 

위 문제에서는 LIS 수열을 만들고, 새로운 입력에 대해 LIS 수열의 마지막 원소부터 0번째 원소까지 이동하며 하나하나 비교하며 원소가 들어갈 위치를 찾아줬다. 이 부분에 대한 시간 복잡도는 O(n)이다.

 

만약 새로운 입력의 위치를 찾아주는 과정을 이분 탐색으로 하면 시간 복잡도가 O(logn)이 될 것이다.

새로운 입력값이 mid값과 같다면 그냥 리턴하고, 작다면 왼쪽으로 크다면 오른쪽으로 가도 괜찮지만 난 그냥 lower bound를 구하는걸로 mid값과 같을 경우와 mid값보다 작을 경우를 합쳤다.

---

소스코드

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> arr;

void binaryInsert(int input) { //lower bound
    int left = 0;
    int right = arr.size() - 1;

    if (input > arr[right]) {
        arr.push_back(input);
        return;
    }
    while (left <= right) {
        int mid = (left + right) / 2;
        if (input <= arr[mid]) //왼쪽 탐색
            right = mid - 1;
        else if (input > arr[mid]) //오른쪽 탐색
            left = mid + 1;
    }
    //값을 replace 하는 과정, right+1이 lower bound
    arr.erase(arr.begin() + right + 1);
    arr.insert(arr.begin() + right + 1, input);
    return;
}

int main() {
    int N, input;

    arr.push_back(0); //초기값으로 제일 작은 0 투입
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> input;
        binaryInsert(input);
    }
    cout << arr.size() - 1; //0을 미리 넣어 놓았으니까 1 빼야 함
}

전체 소스코드다.

 

    arr.push_back(0); //초기값으로 제일 작은 0 투입

11053번을 풀 때 수열의 가장 첫번째 원소로 0을 넣어줬던 것과 같은 이유로 넣은 것이다.

 

    if (input > arr[right]) {
        arr.push_back(input);
        return;
    }

binaryInsert 함수에서는 먼저 input이 벡터의 가장 오른쪽 값보다 큰지 확인한다.

크다면 바로 수열의 길이를 늘려줄 수 있는 상황이니 push_back하고 리턴한다.

 

    while (left <= right) {
        int mid = (left + right) / 2;
        if (input <= arr[mid]) //왼쪽 탐색
            right = mid - 1;
        else if (input > arr[mid]) //오른쪽 탐색
            left = mid + 1;
    }

이건 그냥 lower bound를 구하는 부분이다. right+1이 최종 lower bound가 된다.

 

    //값을 replace 하는 과정, right+1이 lower bound
    arr.erase(arr.begin() + right + 1);
    arr.insert(arr.begin() + right + 1, input);
    return;

벡터의 값을 수정하는 과정이다. 그냥 replace와 같은 역할이라고 보면 되겠다.

---

2021.04.25

재채점이 됐는데 시간초과가 뜬다.

sync어쩌구랑 cin.tie만 해도 될 것 같기도 하고 아닌 것 같기도 했지만

뭐 벡터의 값을 바꾸는 과정에서 시간 소요가 컸을 것 같다는 생각도 들어

 

myunji.tistory.com/325?category=1154147

[백준] 14003번 : 가장 긴 증가하는 부분 수열 5

이 코드에서 수열 출력 부분만 뺐다.

 

#include <iostream>

using namespace std;

int arr[1000001], dp[1000001];

int lowerBound(int left, int right, int key) { //lower bound를 찾는 함수
    while (left <= right) {
        int mid = (left + right) / 2;
        if (dp[mid] < key)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return right + 1;
}

int lis(int n) {
    int length = 0;

    for (int i = 1; i <= n; i++) {
        int pos = lowerBound(1, length, arr[i]); //arr[i]이 들어가야 할 위치 반환
        dp[pos] = arr[i];
        if (pos > length) //증가 수열의 길이가 증가하는 상황
            length++;
    }
    return length;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;

    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> arr[i];
    cout << lis(N) << '\n'; //길이 출력
}