최장 증가 부분 수열. [12738]

[1. 문제 설명]

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

---

[2. 풀이 접근]

LIS 관련 문제 접근은 보통 아래와 같은 방식으로 진행한다.

1. 완전 탐색
2. 동적 계획법 (완전 탐색에서 부분 문제에 대한 메모이제이션 적용)

완전 탐색 접근법은 아래와 같다.

• 수열 A[0] 부터 시작할 때 가장 긴 수열의 길이를 찾는다.
• 수열 A[1] 부터 시작할 때 가장 긴 수열의 길이를 찾는다.
• 수열 A[2] 부터 시작할 때 가장 긴 수열의 길이를 찾는다.
• 이런 방식을 수열의 끝까지 적용하면 구할 수 있으나, 
• 시간복잡도가 O(2^N) 가 되므로, 길이가 1백만 이상인 수열에 대해서는 현실적인 시간내에 구할 수 없다.

다만 여기서 중복문제가 있다는 것을 인지하면, 메모이제이션을 적용하여 조금 더 빠른 시간 내 해결 할 수 있다.

• A[n] 에서 시작하는 수열을 대상으로 LIS 를 구하고 나서,
• A[k] (n < k) 에서 시작하는 수열을 대상으로 LIS 를 구할 때, A[n] 에서 계산한 결과를 재활용 할 수 있다.
• A[k] < A[n] 인 경우, A[n] 부터 시작하는 증가 수열의 길이를 재활용 할 수 있는 것이다.

그러나, 메모이제이션을 적용해도 시간복잡도는 O(N^2) 이다.

• 최대 O(N) 개의 부분 문제
• 하나의 부분 문제 당 O(N) 번의 반복문 호출

역시, 길이가 1백만 이상인 수열에 대해서는 현실적인 시간내에 구할 수 없다.

 

이번 문제에서는 O(NlogN) 시간복잡도를 갖는 알고리즘을 적용해야 한다.

문제에서 제시하는 최장 부분 수열은 하나이지만,

수열 내, 증가 수열은 여러 개가 될 수 있다.

 

이제, 입력 된 수열을 iterate 하면서,

각각의 길이를 갖는 증가 수열 에서 가장 마지막에 오는 값이 최소가 되게끔 하는 테이블을 생성하도록 한다.

• C[i] : 증가 수열의 길이가 i 일 때, 해당 증가 수열에서 최소인 마지막 값

이번에 확인 하는 값이, C 에 저장 된 값 중 가장 마지막 값보다 크다면, 

길이가 1 만큼 더 긴 증가 수열의 마지막 값이 되는 것이고,

 

그렇지 않다면 (더 작다면), C[i] 를 교체 해야 한다.

• 테이블 C 는 항상 순 증가 일 수 밖에 없다.
• 이분 탐색을 통해 교체 해야 할 i 값을 탐색 할 수 있다.

---

[3. 코드 - 완전 탐색]

 

[4. 코드 - 동적계획법]

 

[4. 코드 - 이분 탐색]