#4 최장 증가 부분수열(Longest Increasing Subsequence) 알고리즘

 최장 증가 부분수열은 주어진 수열의 부분수열 중 모든 원소가 이전의 원소보다 크다는 조건을 만족하는 것 중 가장 긴 것을 의미한다.  부분수열(Subsequence)은 기존 수열에서의 순서는 지켜져야하지만 연속한 수일 필요는 없다.  이번에는 주어진 수열에서 최장 증가수열과 그 길이를 찾아내기 위한 LIS 알고리즘에 대해 정리한다.

 

1. O(N^2)의 방법

가장 간단한 방법은 이중 for문을 돌려 동적계획법으로 구하는 것이다.

수열의 i 번째 숫자가 들어왔을 때, i-1까지의 수열들 중에 그 숫자를 추가하여 길이를 늘릴 수 있는 가장 긴 수열을 찾아 i번쨰 숫자를 덧붙인것을 i번째 수열로 한다.

점화식으로 표현한다면 dp[i] = dp[j] + [seq[i]] for j in range(i) if (seq[j] < seq[i] and len(dp[j]) +1 > len(dp[i])) 가 된다.  i-1까지의 j인덱스에서 j번째 숫자, 즉 수열의 마지막이 i번째 숫자보다 작으면서 현재 구해놓은 i번째 수열 후보보다 더 긴 경우를 찾는 것이다.  이를 구현한 코드는 다음과 같다.

import sys


def sol14002(n, seq):
    lis = [[] for _ in range(n)]
    for i in range(n):
        lis[i] = [seq[i]]
        for j in range(i):
            if seq[j] < seq[i] and len(lis[j]) + 1 > len(lis[i]):
                lis[i] = lis[j] + [seq[i]]
    res = max(lis, key = lambda x:len(x))
    return f'{len(res)}\n'+' '.join(map(str, res))


if __name__ == '__main__':
    input = sys.stdin.read
    n, *seq = map(int, input().split())
    print(sol14002(n, seq))

백준 온라인저지(Baekjoon Online Judge)의 14002번 문제(https://www.acmicpc.net/problem/14002)에 제출한 코드이다. 

 

 

2. O(NlogN)의 방법

좀 더 빠른 방법으로 LIS를 구할 수도 있다.  마찬가지로 i번째 숫자가 들어왔을 때, lis 리스트의 마지막 요소보다 i번째 숫자가 크다면 숫자를 리스트에 append, 그렇지 않다면 리스트 내의 i번째 숫자보다 크거나 같은 수 중 가장 작은 수를 i번째 수로 대체한다.  길이만을 구한다면 이것으로 충분하지만 LIS 자체를 구하려면 그 때마다 i번쨰 숫자가 차지하는 위치(인덱스)를 저장해둘 필요가 있다.  이후 그 인덱스를 통해 LIS의 각 인덱스에 들어갈 수 있는 숫자를 찾아 LIS를 알아낼 수 있다.  이를 구현한 코드는 다음과 같다.

import sys
from bisect import bisect_left

def sol14003(n, seq):
    lis, path = [], []
    for i in range(n):
        num = seq[i]
        if not lis or num > lis[-1]:
            lis.append(num)
            path.append(len(lis)-1)
        else:
            p = bisect_left(lis, num)
            lis[p] = num
            path.append(p)
    
    l = len(lis) - 1
    res = []
    for p, num in list(zip(path, seq))[::-1]:
        if p == l:
            res.append(str(num)+' ')
            l -= 1
    res.append(str(len(lis))+'\n')
    return ''.join(res[::-1])
    
    
if __name__ == '__main__':
    input = sys.stdin.read
    n, *seq = map(int, input().split())
    print(sol14003(n, seq))

백준 온라인저지(Baekjoon Online Judge)의 14003번 문제(https://www.acmicpc.net/problem/14003)에 제출한 코드이다. 

 

코딩테스트에서 응용될 여지가 충분해보이기 때문에 잘 기억해둘 필요가 있을 것 같다.