algorithm-bj-12015 가장 긴 증가하는 부분 수열 2

algorithm-bj-12015

https://www.acmicpc.net/problem/12015

이전 코드 참조해서 풀었다. 사실상 실패.

이전 코드도 아마 완전히 내 힘으로 풀었던 게 아닐거같은 느낌이 드는데..

어쨌든, 세그먼트 트리 주차에 나온 문제지만 왜 세그먼트 트리에 속하는지 잘 이해가 안된다.

어려운 부분:

1. 이분 탐색
2. 업데이트 해나갈 때 가장 낮은 수가 나왔을 때 어떻게 해야 할 지 몰랐음

1.

이분 탐색

아직도 조건식이 저렇게 되어야 하고, 나온 후 end를 써야 하는 게 잘 와닿지가 않는다.

int left=0,right=arr.size();
int mid;
while(left<right){
    mid=(left+right)/2;
    if(arr[mid]<val){
        left=mid+1;
    } else if(arr[mid]>val){
        right=mid;
    } else if(arr[mid]==val){
        right=mid;
    }
}
arr[right]=val;

upper_bound를 구현해야 하는건가 했는데 생각해보니 같은 수를 찾으면 뒤의 수는 업데이트 하면 안 되므로 그냥 같은 수를 찾아서 덮어쓰기를 하는 것이었다.

2.

말그대로 가장 긴 증가하는 부분 수열을 찾아야 하는데, 반복적인 동작에서의 아이디어는 기억이 났는데, 다음과 같은 경우를 처리하려면 어떻게 해야 했는지 기억이 나지 않았다.

10 20 30 40 1 2 3 4 5

기본적으로 반복 동작에서는 벡터에 수를 담아 최대 길이이되, 끝 수를 낮게 만들도록 하는 배열을 유지하면 된다는 아이디어는 기억났는데, 위의 경우 10 20 30 40 1 2 3까지는 10 20 30 40이 나와야 하지만, 10 20 30 40 1 2 3 4 부터는 끝 수가 1 2 3 4가 낮으므로 완전히 바뀌어야 한다. 이전 코드를 참조한 결과, 시작점을 가장 작은 수보다 작은 시작값인 -1로 잡으면 되는 것이었다. 그런데, 생각해보니 이게 왜 괜찮은거지? 싶다. -1부터 시작하는것만으론 10 20 30 40 1 2 3 같은 경우 두 개의 배열을 저장해서 비교하다가 하나를 버리는 식의 방식이 필요할 것처럼 보이는데, 어떻게 동작하길래 이게 맞는거지 싶어서 돌려보았다.

10
10 20 30 40 1 2 3 1 1 1

>>> 4
>>> -1 1 2 3 40

놀랍게도 그냥 순서 상관 안하고 작은 수들부터 앞에서 집어넣고 있었다. 다시 생각해보면 그냥 이렇게 해도 되는 게, 작은 수 배열이 나오면 다시 길이 1부터 즉 맨앞부터 시작하므로 새로 저장하면서 하는 것이나 마찬가지고, 그 뒤로 작은 수와 큰 수 사이의 값이 나온다면 그냥 작은 수 뒤로 덮으면서 업데이트 하면 된다.

cpp solution

vector<int> arr;

void solve(){
    int N; cin>>N;
    int tmp;
    int val;
    arr.push_back(-1); // 최소값보다 작은 값을 지정
    rep(N, tmp){
        // 특정 지점에서, 현재까지 읽은 길이 중 최대값이 가장 작게 하는
        // 정보를 기억해야 함.
        // 그러려면 중간의 원소를 업데이트 할 때 효율적으로 해야 하므로
        // 이분 탐색이 필요.
        cin>>val;
        if(val>arr.back()){
            arr.push_back(val);
        } else {
            // val값이 들어갈 자리를 찾아본다.
            int left=0,right=arr.size();
            int mid;
            while(left<right){
                mid=(left+right)/2;
                if(arr[mid]<val){
                    left=mid+1;
                } else if(arr[mid]>val){
                    right=mid;
                } else if(arr[mid]==val){
                    right=mid;
                }
            }
            arr[right]=val;
        }
    }   
    cout<<arr.size()-1<<endl;
}