[Algorithm][Python]최장 증가 부분 수열(LIS) 알고리즘 + 코드

이번에 알아 볼 알고리즘은 최장 증가 부분 수열, 통칭 LIS(Longest Increasing Subsequence)입니다. 어떤 수열이 입력으로 주어질 때 해당 수열에서 증가하는 부분 수열의 최대 길이를 구하는 문제에서 볼 수 있습니다. 약간 변형을 해서 사용하면 LCS 알고리즘과도 비슷합니다.

 

사실 구현만 한다고 했을 때는 굳이 따로 포스팅을 해야할 만큼 거창한 풀이 방법이 있는 것은 아닙니다. 동적 계획법이 익숙하신 분들에게는 그냥 우리가 머리로 생각하듯이 처음부터 원소를 하나씩 순차적으로 탐색하면서 부분 수열의 길이를 세면 되는 거라 코드 작성도 쉬운 편이라고 생각하지만, 제 개인적인 경험으로는 그냥 이런 걸 처음봐서 증가 부분 수열이 무슨 소린지 이해하는 것이 시간이 더 걸렸던 것 같습니다.

 

글로 과정을 조금 풀어서 작성해보면, 예를 들어 입력이 1 5 2 1 4 3 4 5 2 1 이렇게 주어진다고 하겠습니다. 이 때 LIS를 구하는 간단한 방법은 현재 원소를 부분 수열의 마지막 원소로 하는 가장 긴 부분 수열의 길이를 저장하는 것입니다. 몇가지만 해보면,

1) i == 1

첫번째 원소는 1로 첫번째 원소는 딱히 비교할게 없기 때문에 자동으로 최장 길이는 1이 됩니다.

2) i == 2

두번째 원소는 5로 첫번째 원소부터 비교해올 때 1보다 크기 때문에 최장 길이는 2가 됩니다.

3) i == 3

세번째 원소는 2로 첫번째 원소부터 비교해올 때 1보다 크고, 5보다 작기 때문에 최장 길이는 2가 됩니다.

4) i == 4

네번째 원소는 1로 1보다 크지 않기 때문에 최장 길이는 1이 됩니다.

뒤에 있는 원소들도 다 같은 방법으로 작성해보면,

수열	1	5	2	1	4	3	4	5	2	1
길이	1	2	2	1	3	3	4	5	2	1

이렇게 되겠네요.

 

동적 계획법

이번엔 코드로 한 번 확인해보겠습니다.

# 1. dp

def f(n, arr):
    dp = [1 for _ in range(n)]
    for i in range(n):
        for j in range(i):
            if arr[i] > arr[j]: # 현재 원소가 처음부터 비교해오는 원소보다 크면
                if dp[i] < dp[j]+1:
                    dp[i] = dp[j]+1
    return dp

a = list(map(int, input().split()))
print(f(len(a), a)

함수의 파라미터는 편한대로 수정하셔도 되고, dp 테이블의 초기화도 0으로 하셔도 무방합니다. 저는 그냥 한 줄 덜 쓰려고 1로 초기화했어요.

 

다만 동적 계획법의 경우 구현은 쉽지만 시간복잡도가 $O(N^2)$으로 사용 상황에 따라 성능이 좋지 않을 수 있겠죠. 그래서 위의 방법을 조금 변형시켜서 푸는 방법이 있습니다.

 

이진 탐색

Binary Search, 이진 탐색 또는 이분 탐색이라고 불리는 방법입니다. 이 포스팅을 작성한 주된 이유라고 말씀 드릴 수 있을 것 같습니다. 사실 위의 문제에서 이걸 어떻게 적용시키는지 바로 떠오르진 않는데요. 차근차근 알아봅시다.

 

먼저 입력받은 수열을 하나씩 순차적으로 탐색하는 것 까지는 동일합니다. 다만 부분 수열의 길이를 저장하는 것이 아니라 이진 탐색을 통해 현재 위치의 수가 어느 위치에 들어갈지를 정하기 위해서 값을 저장한다는 점이 동적 계획법과의 차이가 되겠네요.

 

리스트에 값을 갱신하게 되는 경우, 즉 부분수열의 마지막 값보다 현재 선택된 원소의 값이 더 크기가 작을 때는 이분 탐색을 통해서 부분 수열 중에서 현재 값보다 작은 원소의 위치를 찾습니다. 그렇게 해서 나온 위치의 다음 위치에 현재 값을 갱신시켜주면 완료되는거죠. 일단은 어떻게 진행되는지 한 번 글로 풀어서 써보겠습니다. 입력 수열은 동일하게 1 5 2 1 4 3 4 5 2 1 을 사용하도록 하죠. 몇가지만 해보면,

1) i == 1

첫번째 원소는 1로 첫번째 원소는 딱히 비교할게 없기 때문에 자동으로 1이 들어갑니다.

수열	1
부분수열	1

2) i == 2

두번째 원소는 5로 첫번째 원소부터 비교해올 때 1보다 크기 때문에 1의 뒤에 추가하겠습니다.

수열	1	5
부분수열	1	5

3) i == 3

세번째 원소는 2로 마지막 원소인 5보다 작기 때문에 이진 탐색을 통해 2가 들어갈 위치를 찾습니다. 2는 1보다 크기 때문에 1이 있는 위치인 0의 바로 다음 위치에 2를 집어넣습니다(이미 있던 5는 이 과정에서 2로 갱신됩니다).

수열	1	5	2
부분수열	1	2

4) i == 4

네번째 원소는 1로 2보다 크지 않기 때문에 이진 탐색을 수행하게 됩니다. 조건문을 어떻게 작성하느냐에 따라 다르겠지만 0번 인덱스의 1과 같기 때문에 0번 인덱스를 갱신해도 되고 무시해도 됩니다.

수열	1	5	2	1
부분수열	1	2

뒤에 있는 원소들도 다 같은 방법으로 작성해보면,

수열	1	5	2	1	4	3	4	5	2	1
부분수열	1	2	3	4	5

이렇게 되겠네요.

 

코드로 작성해보면 이렇게 됩니다.

# 2. binary search

def f():
    subs = [a[0]]
    for i in range(1, n):
        if a[i] < subs[-1]:
            start = 0
            end = len(subs)-1
            while start < end:
                mid = (start + end)//2
                if a[i] > subs[mid]:
                    start = mid+1
                else:
                    end = mid
            subs[start] = a[i]
        elif a[i] > subs[-1]:
            subs.append(a[i])
    return len(subs)

n = int(input())
a = list(map(int, input().split()))
print(f())

이렇게 이진 탐색을 사용해서 코드를 작성하면 시간복잡도가 $O(NlogN)$이 됩니다. 원소를 하나씩 탐색하기 때문에 n, 이분 탐색을 하기 때문에 logn을 곱한 만큼의 연산이 이뤄집니다.