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

백준 11053번 가장 긴 증가하는 부분 수열 문제 풀이: 이진 탐색 알고리즘을 활용하여 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 방법을 상세하게 설명합니다. 문제 출처부터 풀이, 코드 구현까지의 과정을 살펴봅니다.

1. 문제출처: https://www.acmicpc.net/problem/11053

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

2. 문제풀이

이진 탐색(Binary Search)을 사용한 O(N log N) 시간 복잡도의 풀이 방법입니다.

다이나믹 프로그래밍(DP)로도 풀 수 있습니다.

 

// key값 이상인 수 중에서 가장 먼저 나온 수의 인덱스를 반환
int mylower_bound(vector<int>& arr, int key) {
    int st = 0;
    int ed = arr.size() - 1;
    while (ed > st) {
        int mid = (st + ed) / 2;
        if (key > arr[mid]) {
            st = mid + 1;
        }
        else {
            ed = mid;
        }
    }
    return ed;
}

 

이 함수는 key 값 이상인 수 중 첫 번째로 나오는 수의 인덱스를 찾는 이진 탐색 함수입니다.

st는 검색 시작 인덱스, ed는 검색 끝 인덱스입니다.

이진 탐색으로 key 값 이상의 첫 번째 수의 인덱스를 찾아서 반환합니다.

 

void solve() {
    int cnt = 1;
    res.push_back(arr[0]);
    for (int i = 1; i < N; i++) {
        if (res.back() < arr[i]) {
            res.push_back(arr[i]);
            cnt++;
        }
        else {
            int idx = mylower_bound(res, arr[i]);
            res[idx] = arr[i];
        }
    }
    cout << cnt;
}

 

이 함수는 가장 긴 증가하는 부분 수열의 길이를 계산하고 출력하는 함수입니다.

cnt는 가장 긴 증가하는 부분 수열의 길이를 저장하는 변수이고, res 벡터에 수열 arr의 첫 번째 원소를 추가합니다.

for문을 통해 수열 arr의 모든 원소를 순회하며, res 벡터의 마지막 원소보다 크면 res 벡터에 추가합니다.

그렇지 않으면, mylower_bound를 호출해 key 값이상의 수를 찾아 해당 위치의 값을 현재 원소로 바꾸어 줍니다.

최종 계산된 가장 긴 증가하는 부분 수열의 길이(cnt)를 출력합니다.

3. 문제코드

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

int N;
vector<int> arr, res;

// key값 이상인 수 중에서 가장 먼저 나온 수의 인덱스를 반환
int mylower_bound(vector<int>& arr, int key) {
    int st = 0;
    int ed = arr.size() - 1;
    while (ed > st) {
        int mid = (st + ed) / 2;
        if (key > arr[mid]) {
            st = mid + 1;
        }
        else {
            ed = mid;
        }
    }
    return ed;
}
void solve() {
    int cnt = 1;
    res.push_back(arr[0]);
    for (int i = 1; i < N; i++) {
        if (res.back() < arr[i]) {
            res.push_back(arr[i]);
            cnt++;
        }
        else {
            int idx = mylower_bound(res, arr[i]);
            res[idx] = arr[i];
        }
    }
    cout << cnt;
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    arr.resize(N + 1);
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    solve();
}

 

이진 탐색 알고리즘을 활용하여 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 찾는 방법을 설명하였습니다. 문제 이해부터 코드 구현까지의 과정을 따라가면서 논리적으로 문제를 해결하는 능력을 키웠기를 바랍니다.