[BOJ] 11053번 | 가장 긴 증가하는 부분 수열 (C++)

🔗문제 보러가기

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

 

🧑🏻‍💻풀이 과정

최장 증가 부분 수열(LIS) 알고리즘은 저에겐 처음 접해보는 개념이었습니다. 그래서 해당 개념에 대해 먼저 공부하였고, 기존 $O(n^2)$의 시간복잡도를 가지는 알고리즘을 이진 탐색(Binary Search)을 활용하여 $O(nlogn)$으로 줄이는 방법에 대해서도 알게 되었습니다.

(🔗참고 블로그)

 

방법은 다음과 같았습니다. 

1. 최장 증가 부분 수열 숫자들을 담을 배열을 준비한다.
2. 입력된 숫자에 대하여, 다음 과정을 진행한다.
   • 배열이 비었거나, 배열의 마지막 원소보다 입력된 숫자가 크다면, 배열의 마지막 원소 뒤에 추가한다.
   • 그게 아니라면, 이진 탐색을 통해 입력된 숫자가 들어갈 인덱스 번호를 찾는다.
     • 해당 인덱스에 입력된 숫자를 저장한다.

 

배열의 마지막 원소 인덱스를 i라고 하면, 기존 $O(n^2)$ 알고리즘은 0 ~ i - 1까지 새로 입력된 숫자와 비교하여 들어갈 자리를 찾았는데, 이걸 이진 탐색을 활용하여 탐색 시간을 크게 줄였다고 볼 수 있습니다.

종종 유용하게 쓰일 것 같아, 알아두면 좋을 것 같네요!

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
#include <algorithm>
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
using namespace std;

int GetIndexWithBinarySearch(const vector<int>& sequence, int data)
{
    if (sequence.empty())
        return 0;
    return lower_bound(sequence.begin(), sequence.end(), data) - sequence.begin();
}

int main()
{
    FAST_IO;

    int N;
    cin >> N;

    vector<int> sequence;

    for (int i = 0; i < N; i++)
    {
        int data;
        cin >> data;

        int index = GetIndexWithBinarySearch(sequence, data);
        if (index < sequence.size())
            sequence[index] = data;
        else
            sequence.push_back(data);
    }

    cout << sequence.size();
    return 0;
}