[이분탐색] 가장 긴 증가하는 부분 수열 2(12015)(C++)

 

1. 문제 개요

 

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

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

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

https://www.crocus.co.kr/913

lower_bound, upper_bound 이용 방법

 

어떻게 풀면 될지 감이 안잡혀서 위 블로그의 게시물을 보고 풀었다.

 

간단하게 요약하자면, 이중루프를 사용하되, 안의 루프에 이중탐색을 적용해서 시간을 n^2에서 nlogn으로 줄이는 방식이다.



수열의 첫번째 값부터 오름차순으로 벡터에 넣어가는 방식인데, 이미 벡터에 존재하는 값을 대체해서 넣는다. 예를 들어, 벡터에 (1, 20, 50) 이렇게 세 개의 값이 존재할 때, 40이란 값을 새롭게 넣는다고 하면 20 뒤의 자리에 넣을 수 있으므로 50을 대체해서 넣는다. 여기에 이중탐색을 적용해서 벡터에 값이 들어갈 자리를 찾는다.

 

풀이를 보니 대충 어떤 방식으로 동작하는지 이해는 되지만, 이런 방법을 어떻게 생각해내는 건지는 모르겠다.

기억해놓고 나중에 사용해볼 기회가 있다면 적용해보아야할 것 같다.

 

 

4. 전체 코드

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> v;

int binary_search(int left, int right, int target) {
    while(left<=right) {
        int mid = (left+right)/2;
        if(v[mid]<target)
            left = mid+1;
        else
            right = mid-1;
    }
    return left;
}

int main(void)
{
    int num;
    scanf("%d",&num);
    
    int ans = 0;
    int x;
    v.push_back(0);
    for (int i=0; i<num; i++) {
        scanf("%d",&x);
        if (v.back()<x) {
            v.push_back(x);
            ans++;
        } else {
            v[binary_search(0,v.size()-1,x)] = x; // 또는 lower_bound 함수 사용
        }
    }
    printf("%d",ans);
}

아직 배워가는 중이라 틀린 부분이 있을 수 있습니다. 지적할 부분이 있다면 댓글로 알려주시면 감사하겠습니다!!!