[알고리즘] 가장 긴 증가하는 부분 수열 2

구현 방식

• 참고 사이트를 보면 잘 설명이되어있다. 참고바란다.
• 벡터의 끝 값 보다 크면 맨 뒤 에다 채우고, 작으면 현재 탐색하는 값에서 벡터의 lower_bound 와 변경한다. lower_bound를 계산할 때 이분 탐색을 써서 이분탐색 유형인듯
  • lower_bound(v,k) : 해당 벡터 v 에서 k 값 이하가 처음 나오는 위치
  • upper_bound(v,k) : 해당 벡터 v 에서 k 값 이상이 처음 나오는 위치
• 여기서 중요한 부분은 벡터에 채우는 수열이 가장 긴 부분 수열을 의미하는것은 아니다. 그냥 길이만 같을 뿐!
• 예시로 10 20 40 25 15 20 50 이 있다고 가정하자. 원래 해당 최대길이 수열은 10 20 25 50 이겠지만, 해당 알고리즘을 거치면 10 15 25 50 이 나온다.

10 # 끝에 채우기
10 20 # 끝에 채우기
10 20 40 # 끝에 채우기
10 20 25 # 25의 lower_bound 는 40 이므로 변경 
10 15 25 # 25의 lower_bound 는 20 이므로 변경 
10 15 25 50 # 끝에 채우기

코드

• 최종 코드는 아래와 같다.

void solution(int N, vector<int>& numbers)
{
    vector<int> seq;
    for (auto& num : numbers)
    {
        if (seq.size() == 0 || seq.back() < num)
            seq.push_back(num);
        else
        {
            auto it = lower_bound(seq.begin(), seq.end(), num);
            *it = num;
        }
    }

    cout << seq.size();
}