[알고리즘] 최장 증가 부분 수열 LIS(Longest Increasing Subsequence)

0. 최장 증가 부분 수열 LIS

최장 증가 부분 수열 LIS
어떤 수열이 왼쪽에서 오른쪽으로 나열되어 있을 때, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분 수열을 추출하는 문제를 의미한다.

ex) 3, 2, 6, 4, 5, 1의 배열의 LIS 해 중 하나는 2, 4, 5이다.

이 문제를 부분집합으로 접근하면 시간 복잡도가 O(2^n)이므로, DP나 이진 검색을 활용하여 접근하는 것이 효율적이다.

---

1. DP를 활용한 접근

각 원소까지의 LIS 길이를 저장하는 배열인 LIS라고 할 때, LIS(i)를 이전 단계들과의 관계로 표현해보자.

• Case 1: LIS(i)가 a_i를 부분 수열의 마지막으로 포함하지 않는다면 → LIS(i) = LIS(i - 1)
• Case 2: LIS(i)가 a_i를 부분 수열의 마지막으로 포함한다면
  • 증가 수열 관계인 a_j >a_i인 a_j를 찾는다.
  • j값을 알 수 없으므로 모두 검색해야 한다.
  • 그 중 최대값을 찾아 1 증가시켜 LIS(i)에 저장한다.
    • LIS(i) = 1 + max LIS(j)
               (j < i and a_j < a_i)
• LIS(i) 중에서 최대값을 찾는다.

이 방식은 시간복잡도가 O(n^2)으로 효율적이지 않다.

1-1. 코드

---

2. DP와 이진 탐색을 활용한 접근

이번에는 LIS 배열에 각 원소까지의 길이가 아닌 i까지의 배열에서 i자리에 올 수 있는 가능한 값 중 가장 작은 값을 저장하는 배열로 사요한다.

이 과정에서 LIS 배열을 갱신하기 위해 이진 검색을 수행하게 되면 시간복잡도가 O(nlogn)이 되므로 더욱 효율적이다.

단, 이 과정으로 얻은 LIS 배열은 LIS를 구성하는 값이 아니라는 사실을 주의해야 한다.

2-1. 코드

---

3. LIS 배열을 찾는 코드