[백준][C++] 12015 가장 증가하는 부분 수열 2

 

 

 

 

알고리즘 종류

    - 이분탐색

 

 

 

사고 과정

    - 입력된 값을 저장된 배열의 원소들과 비교해서 배열에 넣기

        1. 입력 값 받기

        2. 입력 값이 배열에서 가장 큰 값보다 크면 배열 끝에 그냥 넣기

        3. 입력 값이 배열에서 가장 큰 값보다 작거나 같으면 배열 내부의 원소들과 비교

            3-1. 이분 탐색을 이용해서 입력 값보다 큰 값이 처음으로 나타나는 위치를 찾는다.

            3-2. 위치에 입력 값을 대체해서 넣어 준다.

        4. 배열은 가장 증가하는 원소들만 보여있기 때문에 배열의 크기가 가장 증가하는 부분 수열이다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
 
using namespace std;
 
int n;
// 연속으로 증가된 원소들이 저장될 벡터
vector<int> list;
 
// 이분 탐색을 이용해서 입력된 값을 어디에 넣을지 탐색
int find_location(int num){
    // 초기화 : 양 끝
    int left = 0;
    int right = list.size() - 1;
    
    while(left < right){
        int mid = (left + right) / 2;
        // 입력 값보다 큰 첫 번째 값을 찾아야 함으로 >=으로 해서 right에 mid가 포함되게 한다.
        if(list[mid] >= num) right = mid;
        // 입력 값보다 작은 값은 볼 필요 없으니 mid+1한다.
        else left = mid + 1;
    }
    
    return left;
}
 
 
int main(void){
    // 입력을 빠르게 받기
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    
    int num;
    // 연속으로 증가하는 것을 표현하기 위한 index
    int idx = 0;
    for(int i=0; i<n; i++){
        cin >> num;
 
        // 기준이 될 첫 번째 값 받기
        if(i==0){
            list.push_back(num);
            continue;
        }
        
        // 저장된 원소 중에 가장 큰 값와 비교해서 입력된 값이 더 크다면, 벡터의 끝에 저장
        if(list[idx] < num){
            list.push_back(num);
            idx++;
        }else{
            // 벡터의 어딘가와 비교해서 입력된 값으로 대체하기
            int pos = find_location(num);
            list[pos] = num;
        }
        
    }
    // 연속된 값만 저장됨으로 벡터의 길이가 가장 긴 증가하는 부분 수열이다.
    cout << list.size() << endl;
}
 
 

 

 

 

시행착오

    -    ios::sync_with_stdio(0); cin.tie(0); 을 적용하니 처리 속도가 많이 빨라졌다. 사용하지 않았을 때, 480ms였고, 사용 후 152ms였다.

 

    - 이분탐색으로 찾는 위치에 대한 이해를 위해서 예가 필요했다. {10, 20, 15, 30, 20, 50} 수열이 있다고 할 때, 

 

[10, 20] 상태에서 15가 들어간다. 그러면, 15가 들어갈 위치는 20이다.

 

[10, 15]가 된다. 이후, 30이 들어간다.

 

[10, 15, 30]이 된다. 이후, 20이 들어간다. 그러면, 20이 들어갈 위치는 30이다.

 

[10, 15, 20]이 된다. 이후 50이 들어간다.

 

[10, 15, 20, 50]이 된다.

 

위 과정을 보면, 입력된 값 미만은 값은 유지한다. 하지만 같거나 큰 값은 입력된 값으로 대체된다. 대체되면, 더 작아진다. 즉, 이후에 들어올 값들의 범위가 더 늘어나서 더 큰 증가하는 부분 수열을 만들 수 있다.