가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence / LIS)

• 참고: https://cp-algorithms.com/sequences/longest_increasing_subsequence.html
• 먼저 종종 헷갈리는 용어를 정리하면, 부분수열(Subsequence)은 '주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열' 이다. 연속될 필요가 없다
  • 이게 헷갈리는 이유는, 부분배열(Subarray)이나 부분문자열(Substring)은 연속된 부분을 의미하기 때문이다. 딱히 차이를 구분할 요령이 없다. 그냥 외우자;
• 기본적으로는 DP를 이용해서 푼다. 나이브하게 풀면 O(n^2)이고, 이것을 최적화하는 방법으로 O(nlogn)의 세그트리 방법, O(nlogn)의 이진탐색 방법이 있다.
  • O(nlogn)이 옵티멀하다는 것이 증명되어있다고 한다.
• 이 중에서 속도, 메모리, 코드길이 등 모든 면에서 이진탐색이 우월하므로 이 방법을 기본으로 사용하도록 하자.
• 가장 흔한 태스크는 LIS의 길이를 찾는 것이다. 그 외에 경우에 따라서는 LIS 자체를 찾아야 하는 경우도 있다.

• 가장 흔히 사용되고 기본적인 태스크이다. LIS 자체를 복원하는 것은 여기에 DP역추적을 추가하면 된다.
• 우선 여기에서는 앞에서 언급한 3가지 방법을 다 설명한다. 이후 활용부분에서는 이진탐색 방법만 언급할 예정.

• DP[i] 를 A[i]를 마지막 값으로 갖는 LIS의 길이라고 하면, 점화식은 다음처럼 간단하게 나온다
  • dp[i] = max_(j<i, A[j]<A[i]){dp[j]} + 1
• 앞선 원소들 중에서 값이 더 큰 원소들만 추리고, 그것들에 대해서 가장 큰 DP값을 찾으면 된다.
• 이 점화식을 나이브하게 계산하면, DP[i]를 구하기 위해서 모든 j<i 에 대해서 A[j]를 A[i]와 비교해야 한다. 이렇게 되면 DP테이블 한칸을 채우는데에 O(n), 총 O(n^2)이 걸린다.

• 가장 큰 DP값을 찾는 것에 구간 쿼리에서 사용하는 테크닉과 자료구조를 활용하면 이것을 좀 더 효율적으로 구할 수 있다.
• 구해야 하는 것은 A[j] 값이 얼마 이하인 j에 대해서 dp[j]의 최댓값이다. 구해야 하는 j범위의 dp값들이 연속된 구간에 저장되어있다면, 구간쿼리를 이용해서 최댓값을 빠르게 구할수 있을 것이다. 새로운 배열을 만들어서 dp[j]값들을 j 순서대로 저장하지 않고 A[j]의 순서대로 저장해둔다면, A[j] 값이 A[i]보다 작은 j에 대한 dp[j]값들이 연속된 구간에 저장된다.
• 구체적인 구현은 최댓값 세그먼트 트리를 이용하면 된다. dp[i]값은 max(T[0:A[i]])로 구하고, 구한 dp[i]값은 T[A[j]] := dp[j] 로 업데이트 시켜주는 방식으로 O(logn)에 처리가 된다. 전체 시간복잡도는 O(nlogn)이 된다. 쿼리의 범위가 항상 0에서부터 시작하기때문에, 최댓값임에도 불구하고 펜윅트리를 써도 상관없다.
• 하나의 쿼리 처리에 O(logn)이라고 쓰긴 했지만 조금 부연이 필요하다. dp[j]를 T[A[j]]에 저장하는 원리이기 때문에, T의 크기는 A의 원소 갯수가 아니라 A의 원소중 최댓값이 되어야 한다. 이 최댓값을 m이라고 하면, 세그먼트 트리나 펜윅트리로 구현할 경우 연산의 시간 복잡도는 O(logm)이 된다. 그러므로 만약 m의 범위가 n보다 매우 큰 경우에는, 좌표압축을 사용하거나 동적 세그먼트 트리를 사용해야지만 총 시간 복잡도가 O(nlogm)이 아닌 O(nlogn)으로 맞출수 있다.

• DP점화식의 계산을 다른방식으로 최적화해서, 원하는 값을 단순한 이진 탐색을 통해서 구하는 것도 가능하다
• 앞선 방법들은 j를 기준으로 dp[j]들을 저장해놓고, 조건을 만족하는 j에 대해서 dp[j]의 최댓값을 구한다는 식으로 접근했다.
• 이것을 다르게 접근하면, dp[j]값을 기준으로 j값들을 저장해놓고, 조건을 만족하는 j가 존재하는 가장 큰 dp[j]값을 찾는 방식으로 접근할 수 있다.
• 이 문제에서는 j의 조건은 A[j]<A[i] 인것이고, 같은 dp값을 갖는 j중에 저것을 만족하는 j가 있다는 것은, 가장 작은 A[j]값이 A[i]보다 작다는 뜻이다. 그러므로 가장 작은 A[j] 만 저장해두고 비교해도 충분하다. $ T[k]=min_{dp[j]=k}{A[j]} $ 가 되도록 T 배열을 유지한다면, dp[i]는 $ max_{T[k]<A[i]}{k} + 1 $ 로 구할 수 있다. 이때 T배열의 특징을 살펴보면 단조증가한다는 것을 알 수 있다. 따라서 저 max값을 구하는 과정을 그냥 이분탐색을 통해서 O(logn)에 계산할수 있다. 이렇게 dp[i]를 구하고 난 뒤, T[dp[i]]를 A[i]로 갱신해주면 끝이다.
• 모든 i에 대해서 계산이 끝난 뒤에, 계산 도중 얻었던 dp[i]들의 최댓값을 구하면 LIS의 길이가 된다. 굳이 이 값을 따로 들고 있을 필요 없이, T배열에 담아야 할 k값이 커질때마다 T배열의 크기를 증가시켜주는 방식으로 처리했다면, 그냥 T배열의 크기를 리턴해주면 된다.
• 총 시간복잡도는 세그먼트 트리를 이용한 방법과 마찬가지로 O(logn)이지만, 상수항이 작아서 훨씬 빠르게 돌고, 메모리도 적게 먹고, 코드 역시 훨씬 간단하다. 단점은 로직을 이해하기가 좀 더 헷갈릴수 있다는 것이고, 그로 인해서 활용하기에 어려움이 있을수 있다는 정도인데, 그 정도는 그냥 조금만 더 열심히 이해하면 해결되는 문제라서 패스.
  • 예를 들면, LIS의 개수를 구해야 하는 경우, 참고자료에서는 이진탐색으로는 불가능하고 세그트리 방식으로만 가능하다고 언급되어 있으나, 잘 변형하면 이진탐색으로도 가능하다.
• 실제 코드는 아래처럼 구현된다.

def lis_length_v1(seq) -> int:
    arr = []
    for val in seq:
        pos = bisect.bisect_left(arr, val)
        if pos == len(arr):
            arr.append(val)
        else:
            arr[pos] = val
    return len(arr)

• 이분탐색에 들어가기 전에, 현재값이 이전 최댓값보다 큰지를 먼저 확인해보고, 클 경우에는 이분탐색 없이 바로 뒤에 추가하고, 크지 않을 경우에만 이분탐색을 통해 저장할 위치를 찾는 방법이 있다. 얼핏보기에는 그냥 데이터셋에 따라서 효율적일수도 있고 비효율적일수도 있는 단순한 상수최적화 방법이라고 생각할수도 있긴 하지만, 그것보다는  더 이론적 배경이 있는 방법이다.
  • LIS의 길이가 L이라고 하면, 이 방법은 이분탐색을 들어가는 횟수를 L번 줄일수 있다. 그래서 이분탐색으로 인한 비교횟수가 (n-L)logL 번이 되는데, 이 값은 L=n/logn 일때가 최악의 경우이고, 이 때 비교횟수는 O(nlogn - nloglogn) 이 된다. 각 원소들을 최댓값과 비교해보기 위해 추가되는 연산은 O(n)이니까, 실제로 시간복잡도면에서도 득이 있는 방법이다.
  • 이 방법을 적용해서 조금 더 효율적으로 구현하면 다음처럼 된다.

def lis_length_v2(seq) -> int:
    arr = [seq[0]]
    for val in seq:
        if val > arr[-1]:
            arr.append(val)
        else:
            arr[bisect.bisect_left(arr, val)] = val
    return len(arr)

• 중복값을 포함하는 수열, 즉 non-decreasing subsequence 를 구하는 경우는 bisect_left를 bisect_right로 바꿔주면 된다
• longest decreasing subsequence 를 구하려면 두가지 방법이 있다
  • 하나는 그냥 수열을 뒤집어서, 거기에서 LIS를 구하는 것이다. 사실 이게 제일 간단하다
  • 아니면, bisect의 비교 기준을 반대로 바꿔주면 된다. 각 원소에 -를 붙여서 처리하는 것이 가능하면 그렇게 해줘도 되고, 수가 아닌 다른 타입이라면 거기에 맞춰서 key함수를 재정의해주면 된다.

• 큰 차이는 없지만, 디테일하게 나누면 두가지 구현법이 있다.
• 첫번째는 그냥 일반적인 DP 역추적 방식과 가장 비슷하게 복원하는 방법이다. prev 배열을 만들어서, 각 원소마다 그 앞에 와야하는 원소의 인덱스를 저장해두고 그것을 따라가면서 복원하면 된다.
  • 코드는 이런식이다

    • def lis_v1(seq: list[int]) -> list[int]:
          prev = []
          arr = [seq[0]]
          ind_arr = [0]
          for i, val in enumerate(seq):
              if val > arr[-1]:
                  prev.append(ind_arr[-1])
                  arr.append(val)
                  ind_arr.append(i)
              else:
                  lis_len = bisect.bisect_left(arr, val)
                  arr[lis_len] = val
                  ind_arr[lis_len] = i
                  prev.append(ind_arr[lis_len - 1] if lis_len > 0 else None)
      
          ret = []
          ind = ind_arr[-1]
          while ind is not None:
              ret.append(seq[ind])
              ind = prev[ind]
          return ret[::-1]

• 두번째 방법은 prev배열을 만들지 않고, 그냥 중간에 계속 계산했던 lis_len 값만을 배열에 저장해두고, 그것으로부터 복원하는 방식이다. lis의 길이가 L이었다면, 배열을 역순으로 훑으면서 L, L-1, …, 1 까지를 찾는 것이다. prev배열에서 복원할때보다 더 비효율적인것 같지만, 만드는 과정이 더 간단해져서 전체적으로 조금 더 효율적이다.

  • def lis_v2(seq: list[int]) -> list[int]:
        arr = [seq[0]]
        lis_lengths = []
        for val in seq:
            if val > arr[-1]:
                lis_lengths.append(len(arr))
                arr.append(val)
            else:
                lis_len = bisect.bisect_left(arr, val)
                lis_lengths.append(lis_len)
                arr[lis_len] = val            
    
        p = len(arr) - 1
        ret = []
        for val, lis_len in zip(reversed(seq), reversed(lis_lengths)):
            if lis_len == p:
                ret.append(val)
                p -= 1
        return ret[::-1]

  • 이 방법을 사용하자

• 가장 긴 증가하는 부분 수열 길이 구하기. n<1,000
• 가장 긴 증가하는 부분 수열 2 길이 구하기. n<1,000,000
• 가장 긴 증가하는 부분 수열 4 시퀀스 구하기. n<1,000
• 가장 긴 증가하는 부분 수열 5 시퀀스 구하기. n<1,000,000

• 랜덤으로 뽑은 순열에서 LIS 길이의 기댓값은 2*sqrt(n)이다.
  • https://math.stackexchange.com/questions/347072/what-is-the-expected-length-of-the-longest-increasing-subsequence-of-a-random-pe

• 최소 갯수의 원소들을 이동시켜서 시퀀스를 정렬된 상태로 만드는 문제.
• 역으로 이동하지 않을 원소의 관점에서 생각하면, 이동하지 않을 원소들은 정렬된 상태여야 하고, 이 원소들의 개수가 최대가 되어야 한다는 것이므로, LIS에 해당되는 원소들을 이동시키지 않는 것이 최적이다. 그러면 이동시켜야 하는 원소들의 개수는 {전체 수열의 길이} - {LIS의 길이} 가 된다.
• 이 문제를 다르게 정리하면, LIS는 현재 수열과 그 수열을 정렬해서 만든 수열의 Longest Common Subsequence라고 볼 수 있다.
• 일반적인 LIS 문제를 이렇게 바꿔서 LCS 알고리즘을 써서 푸는것은, 이미 정렬하는 과정에서 O(nlogn)이 걸리므로 비효율적이지만, 정렬된 수열을 이미 알고 있는 상태라면 (현재 수열이 어떤 정렬된 수열을 퍼뮤테이션해서 만들어진 경우), 이 방법을 통해서 더 효율적으로 푸는것도 가능하다.

• [To be filled]

• [To be filled]

• [To be filled]
• 2d-segment tree를 쓰는 것이 직관적
• 하지만 더 효율적인 것은 https://chw0501.tistory.com/24

• 배열을 커버하는 non-increasing subsequence의 최소 갯수는 longest increasing subsequence 의 길이와 같다.
  • 같은 개념으로, 배열을 커버하는 increasing subsequence의 최소 갯수는 longest non-increasing subsequence 의 길이와 같다.
• 증명은 https://cp-algorithms.com/sequences/longest_increasing_subsequence.html#smallest-number-of-non-increasing-subsequences-covering-a-sequence 참고. 어렵지 않다
• 위의 증명이 보고 이해하기 어렵지는 않지만, 막상 떠올리려면 잘 떠오르지 않을때도 있는데.. 딜워스의 정리를 공부하고 나서 보니 이것도 딜워스의 정리의 특정 케이스로 생각할수 있는 것 같다.
  • 딜워스의 정리는 부분순서집합에서 최소 경로 커버의 크기와 최대 반사슬의 크기가 같다는 정리이다.
  • LIS문제를 이렇게 생각해보자. (인덱스, 값)을 노드로 보고, 인덱스와 값이 모두 큰 노드쪽으로 파셜 오더가 있다고 생각하면 부분순서집합이 된다. 부분순서집합을 DAG로 변환하면, LIS를 찾는 것은 가장 긴 패스를 찾는것이 되고, 최소갯수의 increasing subsequence 로 모든 배열을 커버하는 것은 최소 경로 커버를 구하는 것이 된다. 또한 이 노드들의 부분집합중 위상관계가 없는 노드의 집합중 가장 큰 것 (=최대반사슬) 은 longest non-increasing subsequence 라는 것을 쉽게 이해할 수 있다.
  • 원래 이 정리는 이분 매칭을 공부하다가 보게 되었다. 부분순서집합에서 최소 경로 커버의 크기를 이분매칭으로 구하는 방법이 존재한다. 딜워스의 정리를 이용하면 최대 반사슬의 크기도 이분매칭으로 구할 수 있게 된다.
  • 다만 여기에서는 반대로, 최대 반사슬의 크기가 LIS의 길이와 같아서 이쪽을 더 쉽게 구할 수 있으므로, 이 결과를 이용해서 최소 경로 커버의 크기를 빠르게 구하는 데에 사용된다.
    • 바꿔 말하면 '최소 갯수의 non-increasing subsequence 로 배열을 커버하는 문제'를 이분 매칭으로도 풀수 있기는 하다는 말이다. 시간복잡도가 O(n^2.5)가 되므로 비효율적이라서 그렇지..
• 관련 문제
  • 16288 N⇐100 이라서, 그냥 O(n^2)으로 풀어도 된다.
  • Cow Jog N⇐100,000