[백준] 12015번 가장 긴 증가하는 부분 수열 2

 

 

문제

소스코드

 

#include<iostream>
#include<algorithm>
#include<vector>
 
int main() {
    std::vector<int> v;
    std::vector<int> L(1000000, 0);
 
    int  N{};
    std::cin >> N;
 
    for (int i = 0; i < N; ++i) {
        int value{};
        std::cin >> value;
        v.emplace_back(value);
    }
 
    for (auto& here : v) {
        //L이 비어있거나 마지막 원소보다 here가 큰경우
        if (L.empty()) {
           L.emplace_back(here);
        }
 
        else if (*(L.end() - 1) < here) {
           L.emplace_back(here);
        }
        //그렇지 않은경우
        else {
            auto iter = std::lower_bound(L.begin(), L.end(), here);
            L[iter - L.begin()] = here;
        }
    }
    std::cout << L.size() << "\n";
}

 

후기

이 문제를 해결하기 위한 키워드는 LIS가지이다.

 

LIS 증가하는 부분 수열이란: 어떠한 수열의 부분 수열들 중 오름차순인 것들을 증가하는 부분 수열이라 한다.

 

이러한 수열이 있다고 했을 때 증가하는 부분 수열은 [5, 8, 9], [1, 3, 8], [3, 8, 9] 등이 증가하는 부분 수열 LIS 이다.

 

 

이 부분 수열은 다이나믹 프로그래밍과 이진 탐색으로 구현이 가능하다. 이 중 이진 탐색으로 구현하는 핵심은 다음과 같다.

 

1. 부분 수열 리스트(L)이 비어있거나 현재 L의 원소가 전체 수열(V)의 현재 값(Here) 보다 크면

     부분 수열 리스트(L)의 뒤에 Here를 추가한다.

 

2. 그렇지 않다면

     부분 수열 리스트(L)에서 Here 의 lower_bound를 찾아서 그 자리를 Here로 바꾼다.

 

3. 모든 수열을 탐색하고 나온 부분 수열 리스트(L)의 크기가 가장 긴 증가하는 부분 수열의 길이이다. 

 

이 내용을 포함해서 자세하게 설명된 블로그를 밑에 게시했습니다.

 

출처 및 레퍼런스

문제 링크: https://www.acmicpc.net/problem/12015

 

LIS 설명 블로그: https://blockdmask.tistory.com/168