✓

태그:

26. 동적 계획법과 최단거리 역추적 CLASS 5 ESSENTIAL

LIS 전체에 대한 정보는 몰라도 일단 각 LIS 원소에 대해 바로 이전 원소만 알면 재구성할 수 있겠죠…??

풀이 비스무리한거 보기

주어진 수열에서 가장 긴 증가하는 부분 수열와 그 길이를 구하는 문제입니다. 수열의 최대 크기가 10⁶인 것을 보아하니 알고리즘은 $O(n\log n)$ 이하로 만들어야 할 것 같습니다. 이 때 사용하는 알고리즘은 다음과 같습니다.

길이가 i인 LIS가 있을 때, 그 마지막 원소의 최소값의 배열을 계속 저장해나갑니다. 그리고 새 원소에 대해 이분 탐색으로 배열에 인덱스 j에 대해 j보다 작고 j-1보다 큰 원소가 있으면 그 자리를 새 원소로 대체합니다. (① 2568 - 전깃줄 - 2 참조)

다만 여기서는 원소의 값이 아닌 인덱스를 저장하고, LIS에서의 이전 원소의 해당하는 인덱스를 또 다른 배열에 저장하여 LIS 전체에 대한 정보도 추적할 수 있도록 해야합니다. 이전 원소에 해당하는 인덱스는 현재 원소에 의해 업데이트된 ‘LIS의 마지막 원소의 최소값 배열’의 원소의 바로 이전 원소입니다. 이를 모든 원소에 대해 진행하면 LIS의 길이는 물론 그 LIS도 얻을 수 있습니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-03-04 23:14:34

---