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

DP 배열을 푸는 방법을 알고 있다면 엄청 어렵지 않게 해결할 수 있다.

 

1~n까지 반복문을 돌면서 이전에 받았던 값들을 다시 탐색하면서 찾아가는 방식으로 문제를 해결했다.

 

□ DP 이용

int n;
scanf("%d",&n);

int dp[1001] = {0};
int array[1001] = {0};

for(int i=1;i<=n;i++)
    scanf("%d",&array[i]);

for(int i=1;i<=n;i++){
    dp[i] = 1;
    for(int j=1; j<i; j++){
        if(array[j] < array[i]){
            dp[i] = max(dp[j] + 1,dp[i]);
        }
    }
}

int res = 0;
for(int i=1;i<=n;i++)
    res = max(dp[i],res);

printf("%d\n",res);

 

이문제를 해결하고 다른 사람들은 어떻게 풀었지 찾았다.

위 코드에서 이전에 받은 값들을 다시 조사하는 과정이 O(N)

이 부분을 줄일 수 있는 방법이 이진탐색을 이용하는 방법이다.

 

이진탐색을 이용하면 O(logN)으로 줄일 수 있다!

 

Cpp에서는 이진탐색 라이브러리를 지원하는데 

lower_bound, upper_bound 를 지원해 준다.

 

□ lower_bound 이용

int n;
scanf("%d",&n);

int array[1001] = {0};
vector<int> lis;
lis.push_back(array[1]);

for(int i=1;i<=n;i++)
    scanf("%d",&array[i]);

for(int i=1;i<=n;i++){

    if(lis.back() < array[i]){
        lis.push_back(array[i]);
    }
    else{
	    long index = distance(lis.begin(), lower_bound(lis.begin(), lis.end(), array[i]));
        lis[index] = array[i];
    }
}

cout<<lis.size()-1<<endl;

lower_bound를 이용하면 이진탐색을 한 후 가장 작은 최솟값의 주소값을 반환해 준다.

그렇지만 실력향상을 위해..ㅎ

 

이진 탐색 함수를 만들어 보았다.

 

□ 이진탐색 함수

int binary_Search11053(vector<int> &lis, int start, int end, int target){
    int mid = (start + end) / 2;
    while(start < end){
        mid = (start + end) / 2;
        
        if(lis[mid] < target){
            start = mid + 1;
        }
        else{
            end = mid;
        }
    }
    return end;
}

 

공부할수록 너무 어렵다ㅜ