LIS의 길이를 구하는 3가지 알고리즘

본 포스트는 데스크탑에 최적화되어 있습니다.

0. Index

들어가며

문제 소개

완전탐색

3.1. 아이디어 얻기

3.2. 실제 코드

3.3. 시간복잡도

동적 계획법

4.1. 아이디어 얻기

4.2. 실제 코드

이진 탐색을 통한 최적화

5.1. 패러다임 바꿔 생각하기

5.2. 실제 코드

5.3. 시간복잡도

마치며

자료 출처

1. 들어가며

오늘 다루는 문제는 유명한 LIS다. 특정 플랫폼의 문제가 아닌, 유명한 예제가 될 수 있는 문제가 생각보다 없다는 것은 내 잘못된 생각이었다. 종만북을 다시 공부하면서 LIS가 꽤나 유명한 문제라는 것을 알게 됐고 그에 대한 풀이를 준비했다. 이번에는 세 가지 방법을 준비했는데: 완전탐색과 동적 계획법, 이진 탐색을 통한 최적화 알고리즘이 있다. 가끔 우리의 익숙한 생각 패러다임 자체를 변화시키면 문제를 더 쉽게 해결할 수 있는 순간들이 있는데 세 번째 풀이가 딱 그런 것 같다. 알고리즘이 어렵지도 않고 꽤나 우아하다.

간만에 문제다운 문제를 다루게 됐는데 얼마나 걸릴지 모르겠다. 있을지도 모르는 익명의 독자들을 위해 도움이 될 수 있도록 해보겠다.

여기서 다룬 두 풀이는 종만북의 풀이를 많이 참고했고 마지막 풀이는 핵심 아이디어를 통해 직접 구현했다.

2. 문제 소개

LIS는 Longest Increasing Subsequence 의 약자로 한글로는 ‘최장 증가수열’, 또는 ‘최대 증가 부분수열’로 불린다. LIS는 어떤 수열에서 특정 부분을 지워서 만들어낼 수 있는 증가 부분수열(increasing subsequence) 중 가장 긴 수열을 말하는데 이때 부분수열의 숫자들은 원 배열에서 위치가 이어져 있지 않아도 된다는 주요한 특징이 있다.

또 보통 증가는 순증가(strictly increaing)와 단조증가(monotonically increasing)로 나눌 수 있다. 순증가는 \([1, 2, 3]\) 처럼 뒤의 숫자가 앞의 숫자보다 무조건 큰 경우를 말하고, 단조증가는 \([1, 2, 2, 3]\)처럼 뒤의 원소가 앞의 원소 이상인 증가를 말한다. 단조증가 수열의 대표적인 예가 피보나치 수열인데 피보나치 수열의 처음을 어떻게 잡아도 반드시 초반에 1이 두 번 반복되기 마련이다. LIS는 보통 순증가하는 부분수열을 대상으로 한다.

예를 들어 원 배열이 \([1, 4, 6, 8, 3, 5, 6, 7]\)일 때 \([1, 6, 8]\), \([4, 6, 8]\), \([1, 7]\)은 증가 부분수열인데, 이 중 가장 긴 부분열은 \([1, 3, 5, 6, 7]\)이 된다. 이때 중간의 \(4, 6, 8\) 등은 생략한 것을 알 수 있다.

LIS를 직접 구하는 등 LIS에 관한 많은 문제를 만들 수 있지만 이 포스트에서는 수열의 순증가 LIS의 길이를 구하는 방법을 다루도록 한다.

3. 완전탐색

3.1. 아이디어 얻기

가장 일차원적으로는 증가 부분수열을 모두 만들어보면서 그중 가장 긴 증가 부분수열의 길이를 구하면 될 것 같다. 즉 완전탐색으로 생각해보자. 가능할까?

lis example1

다음은 어떤 수열 \(arr\)이다. 이 수열에서 수많은 증가수열을 만들 수 있는데 그중 하나를 만들어보자.

lis example2

만든 수열은 \([4, 5, 6, 7]\)로 무난한 예시다. 이 부분수열을 \(S\)라고 할 때 이를 통해 우리는 적어도 두 가지를 알 수 있다.

정수 i, j에 대해 i < j이면, S[i] < S[j]다.(0 <= i, j <= |S|)
정수 i, j에 대해 S[i] < S[j]이면, 원 배열 arr에서의 S[i], S[j] 두 수의 위치 전후관계는 같다.(0 <= i, j <= |S|)

이 두 명제는 LIS의 정의상 명확하다.

그렇다면 이 명제를 활용해서 LIS의 길이를 구하는 함수를 만들자.

이 함수는 완전탐색답게 모든 증가 부분수열을 고려한다. 함수는 배열을 받아 원 배열에서 증가 부분수열의 첫 수를 선택하고, 그 다음 수가 될 수 있는, 위의 두 명제처럼 첫 수보다 원 배열에서 뒤에 있고 큰 후보값들의 배열을 추려 재귀해나가면 될 것 같다. 재귀가 가능한 것은 숫자를 하나 선택할 때마다 같은 과정을 진행할 수 있기 때문이다.

이때 증가수열이 생성되면서, 다시 말해 재귀함수가 진행되면서 내 앞의 숫자가 어떤 숫자였는지는 중요하지 않다. 이미 내가 선택되었다는 것은 그 이전의 숫자가 나보다는 작은 숫자라는 것을 말해주고, 또 여기서는 길이만 구하기 때문에 앞선 콜에서 이전값의 길이 1만을 계속 더해나가면 되기 때문이다.

이 아이디어를 코드로 옮기자.

3.2. 실제 코드

실제 코드는 다음과 같다.

def lis(arr):
    if not arr:
        return 0
    
    ret = 1
    for i in range(len(arr)):
        nxt = []
        for j in range(i+1, len(arr)):
            if arr[i] < arr[j]:
                nxt.append(arr[j])
        ret = max(ret, 1 + lis(nxt))
    return ret	

매우매우 짧은데 각 부분을 설명하면 다음과 같다.

if not arr:
   return 0

배열이 빈 값이면 당연히 답은 0이다. 이 조건은 단순히 예외처리뿐 아니라 재귀가 진행되면서 종료될 base case이기도 하다.

ret = 1
for i in range(len(arr)):
    nxt = []
    for j in range(i+1, len(arr)):
        if arr[i] < arr[j]:
            nxt.append(arr[j])
    ret = max(ret, 1 + lis(nxt))
return ret	

ret 을 초기화한다. 위의 조건식에 부합되지 않았다는 것은 원소가 하나는 들어있다는 뜻이기 때문에 최소값 1로 설정한다.

다음 코드가 중요하다. for문이 2중으로 중첩되어 있는데 각 for문의 역할은 다음과 같이 구분된다:

첫 번째 for문은 배열에서 증가수열의 시초가 될 첫 수를 선택한다. 이 완전탐색 함수는 모든 증가부분수열을 다루기 때문에 입력된 배열의 모든 수가 증가수열의 첫 번째 숫자가 될 수 있다.
두 번째 for문은 앞서 살핀 두 가지 조건을 만족하는 다음 수들의 후보를 배열로 추린다.

두 번째 for문이 종료되면 nxt 에는 이 수(arr[i])로 만들 수 있는 증가 부분수열의 두 번째 값들의 후보가 담긴다. 그 후에 ret 을 nxt 를 활용한 재귀식의 값들의 최대값으로 경신해나간다.

1 + lis(nxt) 코드를 주목해야 한다. 각 함수는 나보다 앞선 값이나 생성되던 중간의 배열을 알 필요가 전혀 없다. 따라서 재귀를 호출할 때 arr[i] 의 크기 1만 더해주면 완성된 증가 부분수열의 길이를 구할 수 있는 것이다. 재귀가 깊어지면서 1은 계속 더해지기 때문에 더 이상 나보다 크고 뒤에 있는 원소를 발견할 수 없어 입력이 []이 됐을 때 0을 반환하며 종료하고 그 수들의 합이 곧 정답이 된다.

3.3. 시간복잡도

이 코드의 시간복잡도를 계산해보자. 나는 처음 이 코드를 보고 언뜻 시간복잡도가 바로 생각나지 않았다. 아무래도 시간복잡도에 큰 영향을 미치는 반복문과 재귀함수가 한 블락에 묶여있어서 그런 것 같다. 어떻게 이해할까 하다가 그림을 그려보니 감을 잡을 수 있었다. 시간이 가장 오래 걸리는 경우는 배열이 정렬됐을 때이다. 가령 \([1, 2, 3, ..., N]\) 같은 입력에는 자기 자신이 곧 lis가 되고 증가 부분수열도 제일 많이 생성된다.

이 장을 적기 전에는 난 시간복잡도가 \(O(N^3)\)이 될 것이라 믿고 있었고 그에 맞게 작성하려고 그림을 컴퓨터로 그리고 있었는데 아무리 생각해도 저거보단 크게 보여서 연구하고 찾아보았다. 결국 틀렸다는 것을 알게 됐고 그동안 열심히 그린 그림을 폐기하게 됐다. 이 가슴아픈 상황을 누가 알아주려나..? Buy me a coffe..

뻘소리고 내가 이 알고리즘의 시간복잡도를 추론한 방법을 살펴보자. 입력이 \([1, 2, ..., N]\)과 같은 상황일 때 재귀호출되는 lis 입력 nxt 는 특정 원소 n의 다음부터 원소의 끝 수 N까지의 연속된 배열이다. 가령 \([n+1, n+2, ..., N]\)과 같겠는데 이때 같은 문제를 이름을 조금 바꿔서 다음과 같이 정의하자.

lis(i) := i번째 원소부터 끝까지의 최장 증가수열의 길이

이때 i를 0부터 시작하면 1부터 시작해서 끝까지 lis 를 계속해서 호출해 나갈텐데 종료할 때까지의 수형도를 그려보자. 너무 커지면 손과 가슴이 아프기 때문에 수열을 \([1, 2, 3]\), 즉 크기를 3으로 해서 호출해보자. 이 상황에서 lis(3) 은 답이 0으로 고정된다.(즉 기저사례다.) 빈 수열은 답을 0으로 해야할 수밖에 없으니까.

이 함수의 호출과정을 수형도로 그려보면 다음과 같다.

tree graph of lis example

크기가 3일 때의 함수 콜 과정을 수형도로 표현할 결과 함수가 종료되는 시점인 lis(3) 호출이 8번 일어났다. 8은 무슨 의미일까. 그렇다. \(2^3 = 8\)이 되고 이 완전탐색의 시간복잡도는 \(O(2^N)\)이 된다. 다른 수를 넣어서 수형도를 그려봐도 좋다.

이 알고리즘은 종만북의 코드를 거의 그대로 가져왔는데 사실 조금 다른 형태의 완전탐색을 구현할 수도 있다. 부분수열을 만들었을 때 어떤 인덱스의 수를 포함하거나, 안 하거나의 두 가지 수로 나뉜다는 것을 활용하는 것인데 이때도 시간복잡도는 동일하다.

4. 동적 계획법

앞서 살펴본 완전탐색은 작정하고 LIS 문제를 낸 테스트에서는 반드시 떨어지게 되어 있다. 현실적으로도 \(O(2^N)\)은 너무 크기 때문에 더 나은 해결책을 모색해야 한다. 다행히 완전탐색의 중복을 해결해 동적 계획법으로 코드를 개선할 수 있다. 이 장에서는 이에 대해 살펴보자.

4.1. 아이디어 얻기

앞선 장에서 나는 코드 자체에서 시간복잡도를 측정하기 어려워서 함수 호출의 수형도를 그렸고, 장의 마지막에 다른 풀이도 있다는 것을 짤막하게 소개하고 끝냈다. 하지만 애초에 다른 풀이의 코드를 작성했다면 시간복잡도를 측정하기 훨씬 쉬웠을 것이다. 그 코드는 i번째 수를 포함하거나, 안 하거나 해서 만들어지는 두 수열에 재귀호출을 중첩시켜 나가기 때문에 확실하게 한 호출에서 두 번의 재귀호출이 보이기 때문이다. 이런 알고리즘의 종류로 피보나치 수열을 완전탐색으로 구하는 것이 있는데 이런 경우 보통 시간복잡도는 \(O(2^N)\)이 된다.

열심히 그리던 다른 그림을 폐기하면서까지, 또 수형도를 그리다가 크기가 4인 수열은 수형도가 너무 커져서 크기를 3으로 줄이면서까지 수형도를 그린 이유는 뭘까? 굳이 내가 이런 선택을 하면서까지 수형도를 그린 이유는 이 수형도를 통해 동적 계획법의 가능성을 확실히 발견할 수 있기 때문이다.

다시 한 번 그림을 보자. lis(i) 는 i 번째 인덱스의 수부터 원 수열의 끝까지의 lis의 길이를 반환하는데 여기에는 수많은 인덱스의 lis 호출이 쓰였다. lis(1), lis(2) 가 반복되는 것을 확실히 알 수 있다. 이들을 완전탐색에서는 전부 중복 계산하는데 캐싱을 통해 재계산을 없애자!

lis(i) 를 수식화해보면 다음과 같겠다.

\[ \text{수열을 } arr, \text{크기를 } N \text{이라고 하자.} \]

\[ lis(start) = MAX \bigg( \forall next \in [start+1, N-1] \hspace{1mm} \& \hspace{1mm} arr[start] < arr[next] \hspace{3mm} | \hspace{3mm} lis(next) + 1 \bigg) \]

내 나름의 수식을 해석해보면 |를 기준으로 해서

왼편은 두 조건을 모두 만족하는 next 에 대해서,
오른편은 lis(next) + 1 를 실행하고,
그 값들의 최대값이 정답이 된다는 뜻이 된다.

수식의 기호들의 의미는 이전 알고리즘 포스트에서 조금 설명했다.

좋아, 수식으로까지 정리됐으면 코드는 gum이다.(잇몸 아님.) 바로 코드로 들어가자.

4.2. 실제 코드

위에 나온 수식에 캐싱을 더해 동적 계획법 코드를 작성해보면 다음과 같다.

import math


def lis(arr):
    arr = [-math.inf] + arr
    N = len(arr)
    cache = [-1] * N

    def find(start):
        if cache[start] != -1:
            return cache[start]

        ret = 0
        for nxt in range(start+1, N):
            if arr[start] < arr[nxt]:
                ret = max(ret, find(nxt) + 1)

        cache[start] = ret
        return ret

    return find(0)

코드를 보면 논리가 놀라울 정도로 완전탐색과 유사함을 알 수 있다. 이는 당연한 것으로 핵심 아이디어를 완전탐색에서 가져왔기 때문이다. 우리는 다만 여기에 캐싱을 추가해서 중복계산을 없앴다.

염두할 것은 Sequence arr 의 0 번째 인덱스에 음의 무한을 넣었다는 것. 이것은 [100, 1, 2, 3]과 같이 원 Sequence의 첫 번째 값이 가장 큰 값일 때를 대비하기 위한 것이다. 우리는 find(0) 로 재귀함수를 시작하고 맨 처음 이 함수는 다른 값들 중 0번째 값보다 더 큰 값이 있을 때 재귀한다. 하지만 첫 번째 값이 가장 큰 값일 때는 find의 재귀가 실행되지 않기 때문에 첫 번째값이 절대 가장 큰 값이 될 수 없도록 강제로 음의 무한을 더한다.

시간복잡도는 어떻게 될까? 우리가 채워야 하는 cache 의 크기는 N 이다. 그리고 캐시를 채우는 각 find 호출마다 N 의 반복문이 호출되기 때문에 시간복잡도는 \(O(N^2)\)가 된다. 완전탐색의 시간복잡도와 \(2\)와 \(N\)의 위치만 뒤바꼈는데 압도적인 성능격차를 느낄 수 있다.

5. 이진 탐색을 통한 최적화

이 방법은 정말 어썸하다. 내 많은 알고리즘 포스트들이 그렇듯, 이 포스트도 이 기발한 알고리즘을 기념하기 위한 긴 세레나데라고 할 수 있겠다. 프로그래밍 세계에서는 간단하고 성능 좋은 것을 세련됐다라고 표현하는데 이번 장을 통해 이 알고리즘이 간단하고 성능도 좋다는 것을, 다시 말해 세련됐음을 확인할 것이다.

들어가보자.

5.1. 패러다임 바꿔 생각하기

완전탐색과 동적 계획법 알고리즘은 궤를 같이했다. 그도 그럴 것이 완전탐색의 중복 문제를 해결하는 방법이 곧 동적 계획법 알고리즘이었기 때문이다. 핵심 아이디어는 변하지 않았다. 이번에는 문제 자체를 다르게 접근하자.

자, 우리는 수열 \(arr\)을 입력받았다. 이제 이 미지의 수열을 하나씩 건너가며 lis를 만들어나간다고 하자. 이때 우리는 이 수열이 정수 수열이라는 것만 알고 그 크기 등은 모르는 상태다.

어떤 수열의 원소를 4개를 먼저 살피니 \([5, 6, 1, 2]\)였다고 하자. 현재까지의 lis는 \([5, 6]\), \([1, 2]\)다. 뒤에 더 많은 숫자가 있지만 일단은 지금의 정보가 최선이다.

다음엔 어떤 수열의 첫 5개의 숫자가 다음과 같다고 하자: \([5, 6, 7, 1, 2, ...]\). 현재까지의 lis는 \([5, 6, 7]\)이다. lis를 위한 우리의 위대한 여정을 계속한다고 할 때 현재까지의 lis 정보가 의미있을까? 그건 상황에 따라 다른데 크게 두 가지 경우로 나눌 수 있다.

의미없다. \([1, 2]\)가 최종적인 lis의 시초가 될 수 있다. 알고 보니 원 수열이 \([5, 6, 7, 1, 2, 3, 4]\)일 수도 있으니까. 이때는 중간 lis 수열 \([5, 6, 7]\)의 정보가 무의미하다.
의미있다. 원 수열이 \([5, 6, 7, 1, 2]\)에서 끝나버린다면 현재까지의 lis인 \([5, 6, 7]\)의 크기 3이 곧 답이 된다.

다시 말하지만 우리는 현재까지의 수 이상의 미지의 수는 아직 모르는 상태다. 그렇기 때문에 중간에 생기는 lis가 무의미할 수도, 의미있을 수도 있는 상황이기에 애매하다. 결국 우리의 인생처럼 무의미와 의미의 경계에서 헤매게 되는걸까…?

잠깐, 불확실의 살얼음을 걷는 내 인생에도 아직 확실한 것은 남아 있다. 마찬가지로 여기까지의 불완전한 수열(\([5, 6, 7, 1, 2]\))까지만 봤을 때도 확실한 것들이 있다. 길이가 1인 증가 부분수열들의(\([5], [6], ...[2]\)) 마지막 값 중 최소의 값은 1이고, 길이가 2인 증가 부분수열들의(\([5, 6], [1, 2]\)) 마지막 값 중 최소의 값은 2이다. 길이가 3인 증가 부분수열의(\([5, 6, 7]\)) 마지막 값 중 최소의 값은 3이다.

그리고 증가 부분수열의 크기가 같다면, 이때 마지막 값의 크기가 작은 것의 정보를 유지하는 것이 유리하다. 가령 배열의 첫 네 원소가 \([5, 6, 1, 2]\)일 때 크기가 2인 증가 부분수열은 \([5, 6]\)과 \([1, 2]\)이 있다. 그 다음 수가 무엇이 될지는 모르겠지만 작은 정보를 유지할 때는 lis를 문제없이 구할 수 있다. 가령 원 수열의 바로 뒤의 수이자 마지막 수가 3일 때나 11111일 때 모두 \([1, 2]\)는 lis를 만들어낼 수 있다.(\([1, 2, 3], [1, 2, 11111]\)) 하지만 \([5, 6]\)은 3일 때 lis를 이어가지 못한다.(\([5, 6, 3]\)) 즉, 같은 크기의 증가수열에서 최소의 마지막 값만 기억하면 문제를 풀어낼 단서를 찾을 수 있다.

앞선 lis(i) 는 i 인덱스부터 시작하는 부분배열의 lis의 길이를 구하는 것이었다면 이번에는 \(C\)라는 배열을 관리하는데 \(C[i]\)라는 문제는 다음과 같이 정의된다.

C[i] = 길이가 i인 증가수열들 중에서 최소의 마지막 값

입력이 빈 배열이 아닐 경우 lis의 길이의 최소값은 1이고, 최대값은 배열의 크기 자체다. 그래서 우리는 |arr| + 1 크기의 배열을 준비한다. | |은 집합의 크기를 산정하는 수학기호다. 크기를 1 늘리는 이유는 배열의 크기 자체를 인덱싱 가능하게 하기 위해서다. 우리는 원 배열을 순회해 나가면서 C 배열의 각 값을 최소값으로 다듬을 예정이기 때문에 일단 무한으로 초기화해놓자. 그리고 크기가 0인 증가 부분수열은 다루지 않기 때문에 음의 무한으로 초기화해놓는다.

원 배열을 \([5, 6, 7, 1, 2]\)까지 진행했을 때 C 배열은 다음과 같을 것이다:

\[C = [-inf, 1, 2, 7, inf, inf]\]

이것이 이해되어야 식을 유도할 수 있다. 여기서 \(C[i]\)가 무한이 아닌 i의 최대값이 lis의 길이가 됨을 알 수 있다. i 가 3일 때가 7인데 현재까지의 lis의 크기는 3이 된다. C의 원소들의 정확한 값은 중요하지 않다. 각 크기의 증가 부분수열은 매우 많을 수 있는데 우리는 각 크기의 증가 부분수열의 마지막 값 중 최소값만 계속 다듬어 나간다. 이렇게 다듬어 나가는 과정을 거치다보면 어느 순간 원소의 끝에 도달할 수 있을테고 그때 우리는 \(C[i]\)가 무한이 아닌 가장 큰 i를 통해 lis의 길이를 반환할 수 있게 된다.

자, 이제 다듬는 과정을 조금만 더 살펴보자. \(C[i]\)은 처음에 모두 양의 무한으로 시작할텐데 어떻게 최소값으로 깎아나가는가?(0번째 인덱스는 무시한다.) 앞선 중간 탐색과정의 \(C\) 배열을 더 활용하자. 현재 원 배열을 순회 중에 있고 다음 원소를 살펴본다. 이때는 다음과 같은 경우의 수가 있겠다.

\[ \text{순회하는 다음 수를 }n \text{, }
\text{지금까지 찾은 중간 lis의 길이를 } count \text{, }
\text{C[count]의 원소를 } last \text{라고 하자.} \]

\[ n \text{의 크기에 따라, } \displaylines{ \begin{cases} C[count+1] = n & \quad \text{if } last < n \\ C[i] = n & \quad \text{if } C[i-1] < n <= C[i] \end{cases} } \]

\(n\)의 크기에 따라 크게 두 가지의 경우의 수가 있는데 첫 번째는 쉽게 이해된다. 현재 탐색할 수 \(n\)이 C 배열의 마지막 수보다 크면 새로운 lis의 출현이기에 C에 바로 붙이면 된다. 가령 \(C = [1, 2, 7, inf, inf]\)인데 숫자가 10이라면 바로 7뒤에 붙여 \(C = [1, 2, 7, 10, inf]\)가 될 것이다. lis의 길이(count)도 4로 경신된다.

그 다음이 중요하다. 만약 \(n\)이 C의 무한이 아닌 수열의 최소값과 최대값의 사이에 있을 때는 어떻게 하는가? 우리는 그 뒤에 몇 개의 수가 더 오는지, 그들의 대소관계는 모른다. 하지만 최소한 C의 각 숫자를 최소로 다듬어놓으면 뒤에 등장하는 숫자에 최선으로 대응할 수 있고, 무엇보다 답을 찾을 수 있다.

만약 C가 \([1, 2, 7, inf, inf]\)이고, \(n\)이 3일 때, 확실한 것은 이 \(n\)은 1, 2, 7보다 어떻게든 뒤에 등장하는 수이고, 또 1, 2 보다는 큰 수라는 점이다. 그러면 앞선 두 조건을 만족해 \([1, 2, 3]\)만으로 부분 증가수열이 성립되고 따라서 \([1, 2, 7]\)을 유지하는 것보다 \([1, 2, 3]\)을 유지하는 것이 뒤에 오는 수들에 대응하기 더 쉬워진다. 가령 그 다음수가 5라면 \([1, 2, 3, 5]\)로 lis의 길이를 경신하는 것이 가능할 것이다.

따라서 두 번째 경우에는 \(C[i-1] < n <= C[i]\)인 \(i\)를 찾아 그 인덱스의 C를 \(n\)로 경신한다. 여기서는 7이 3으로 경신되는 것이 된다.

그리고 결정적으로 일차원 배열에서 이 조건에 맞는 수를 탐색하는 일이 남는데 현재 이 수열은 오름차순 정렬된 상태가 유지된다. 그렇다면 \(O(N)\)의 순차탐색이 아닌 \(O(NlogN)\)의 이진 탐색을 써도 충분하다!

이 조건을 맞춰서 \(C\) 배열을 다듬어나가면 lis의 크기를 파악하는 이 문제를 쉽게 해결할 수 있다.

5.2. 실제 코드

앞서 살펴본 통찰을 코드로 옮기면 다음과 같다.

def lis(arr):
    if not arr:
        return 0

    # C[i] means smallest last number of lis subsequences whose length are i
    INF = float('inf')
    C = [INF] * (len(arr)+1)
    C[0] = -INF
    C[1] = arr[0]
    tmp_longest = 1

    # Find i that matches C[i-1] < n <= C[i]
    def search(lo, hi, n):
        if lo == hi:
            return lo
        elif lo + 1 == hi:
            return lo if C[lo] >= n else hi

        mid = (lo + hi) // 2
        if C[mid] == n:
            return mid
        elif C[mid] < n:
            return search(mid+1, hi, n)
        else:
            return search(lo, mid, n)


    for n in arr:
        if C[tmp_longest] < n:
            tmp_longest += 1
            C[tmp_longest] = n
        else:
            next_loc = search(0, tmp_longest, n)
            C[next_loc] = n

    return tmp_longest

코드는 크게 변수 초기화, 이진 탐색 코드 구현, \(C\) 배열을 다듬는 과정으로 나뉘는데 각 부분을 따로 살펴보면 다음과 같다.

# C[i] means smallest last number of lis subsequences whose length are i
INF = float('inf')
C = [INF] * (len(arr)+1)
C[0] = -INF
C[1] = arr[0]
tmp_longest = 1

\(C\) 배열을 무한으로 초기화한다. 이제 각 인덱스에 맞는 길이의 증가 부분수열의 마지막 값 중 최소값으로 경신될 예정이다. 이중 0번 인덱스는 안 쓰이기 때문에 음의 무한으로 초기화했고, 첫 번째 값은 배열의 첫 번째 값으로 재할당했다. 배열의 첫 원소 자신도 길이가 1인 증가수열이다. 다음은 tmp_longest 라는 변수로 lis의 길이값을 추적한다. 입력이 빈 배열이 아니면 최소값이 1이기 때문에 값을 1로 설정해놓는다.

# Find i that matches C[i-1] < n <= C[i]
def search(lo, hi, n):
    if lo == hi:
        return lo
    elif lo + 1 == hi:
        return lo if C[lo] >= n else hi

    mid = (lo + hi) // 2
    if C[mid] == n:
        return mid
    elif C[mid] < n:
        return search(mid+1, hi, n)
    else:
        return search(lo, mid, n)

다음은 조건에 맞는 인덱스 i 를 찾는 이진 탐색 코드다. 다른 부분은 일반 이진 탐색 코드와 동일한데 첫 번째 elif 문을 눈여겨보자. 크기가 2인 배열에서 어지간하면 두 번째 값을 반환하는데(hi), C가 \([2, 3]\)일 때는 \(n\)이 1일 시 \([1, 3]\)처럼 첫 번째 값이 경신되어야 하기 때문에 hi 가 아닌 lo 를 반환해야 한다. 참고하자.

이진 탐색을 쓰기 위해서는 배열이 항상 정렬이 되어 있다는 조건이 필요한데 직접 확인해보면 알 수 있듯이 어떤 배열을 순회하더라도 중간에 오름차순 조건이 깨지지 않는다. 이진 탐색을 위해서는 반복문을 돌면서도 C 배열의 오름차순 조건이 지켜지는지 확인하는 것을 잊지 말자. 여기서는 문제없다.

for n in arr:
    if C[tmp_longest] < n:
        tmp_longest += 1
        C[tmp_longest] = n
    else:
        next_loc = search(0, tmp_longest, n)
        C[next_loc] = n

return tmp_longest

C 배열을 경신하는 핵심 코드다. tmp_longest 는 C의 무한 직전의 인덱스이자 중간 lis의 길이를 다루는 변수다. \(n\)이 \(C[tmp\_longest]\) 변수보다 크면 lis가 더 길어지기 때문에 크기를 1 키우고 그 인덱스에 \(n\)을 집어넣는다.

반대로 그보다 작다면 이진 탐색 코드를 써서 \(n\)이 경신해야 할 위치를 반환한다. 이때 search 함수의 두 번째 인자가 길이 변수인 것을 확인하자. C 배열의 크기를 두지 않아도 된다. 애초에 C에는 많은 무한값도 같이 있기 때문에 그 전부를 훑어주지 않아도 된다.

과정을 통해 C를 완전히 경신했으면 최종 lis의 길이를 반환하면 된다.

지금까지 이진 탐색을 통한 최적화 알고리즘 코드를 살펴봤다.

5.3. 시간복잡도

이 알고리즘의 시간복잡도를 살펴보자. 동적 계획법의 시간복잡도가 \(O(N^2)\)였는데 이보다는 나으면 좋겠다. 과연 그럴까?

시간복잡도는 원 배열을 순회하고(\(O(N)\)) 각 순회에서 이진 탐색하는(\(O(logN)\)) 과정이 묶여 있다. 따라서 시간복잡도는 \(O(NlogN)\)이 될 것 같은데 그거보다 사실 더 좋다.

각 탐색 과정에서 두 번째 인자를 lis의 길이 변수(tmp_longest)로 줬는데 이 변수는 결국 lis의 길이로 수렴한다. lis의 길이를 \(K\)라고 할 때 \(K <= N\)는 언제나 성립하기에 따라서 \(O(NlogK) <= O(NlogN)\)도 성립하고 최종적인 시간복잡도는 \(O(NlogK)\)가 된다. 이는 탐색의 두 번째 값을 배열의 크기로 고정하지 않고 유동적인 변수를 썼기에 가능한 성과기도 하다.

6. 마치며

lis의 길이를 구하는 세 가지 알고리즘을 살펴봤다. 와 힘들었다. 세 번째 알고리즘을 설명하는 데 꽤 많은 텍스트가 소모됐는데, 나는 나름 최대한 풀어서 설명한다고 했는데 다 쓰고 보니 ‘너무 많은가?’하는 생각도 든다. 앞선 포스트들을 돌아보건대 텍스트가 길어지면 사람들은 그 포스트의 가치는 쳐다도 안 보고 지레 겁을 먹고 ‘뒤로 가기’ 버튼을 누른다. 이 포스트에서는 세 번째 알고리즘이 중요하다. 혹시 세 번째 알고리즘이 너무 어렵게 설명됐거나 텍스트가 너무 길다고 생각하면 댓글을 남겨주시면 어떻게든 수정해보도록 하겠다.

간만에 신경을 써서 알고리즘 포스트를 작성했다. 많은 분들에게 도움이 된다면 더는 바랄 것이 없겠다.

이상 포스트를 마칩니다.

7. 자료 출처

Time complexity of LIS algorithms: leetcode
『알고리즘 문제 해결 전략』 8장 ‘동적 계획법’, 구종만, 인사이트(insight)