코테연습 - LIS에서 부분수열 추적

LIS 알고리즘

어떤 수열의 부분 수열에서 가장 긴 부분수열의 길이를 찾는 것이 LIS 알고리즘이다.

흔히 리스트를 만들어서 이분탐색으로 수열의 모든 원소를 삽입해줬을 때, 리스트의 길이가 LIS의 길이가 된다.

근데 이 리스트가 수열의 가장 긴 부분수열은 아니다.

실제로 가장 긴 부분 수열을 구하려면 어떻게 해야하는가?

DP

DP로 LIS를 역추적할 수 있다.

• DP[i] : 원래 수열의 i번째 원소가 리스트에서 몇 번 인덱스인지
• prev[i] : 리스트에서 수열의 i번째 원소의 바로 앞 원소

DP와 prev는 다음과 같다

LIS를 구하기 위한 리스트의 상황이 현재
[a,b,c,d,e]
라고 가정하자.

원소 c의 DP값은 2이다. 리스트의 2번 인덱스에 있기 때문.
원소 c의 prev는 b이다. 리스트의 2번 인덱스 앞인 1번 인덱스에는 b가 있기 때문.

---

가장 긴 수열을 구하는 방법

LIS처럼 리스트에 원소를 삽입할 위치를 이분탐색하여 삽입하는 것은 똑같다.

과정

1. 이분탐색으로 원소를 삽입할 위치를 찾는다.
2. 원소를 삽입할 위치를 DP에 저장한다.
3. 원소를 삽입한다.
4. prev에 리스트에서 삽입한 원소의 앞 원소를 저장한다.
5. LIS의 길이를 구하고 나면 DP값이 가장 큰 원소를 찾는다.
6. DP값이 가장 큰 원소부터 prev를 따라가면서 가장 긴 수열을 거꾸로 탐색한다.

---

관련 문제

14002번: 가장 긴 증가하는 부분 수열