최장 증가 수열

최장 증가 수열 (LIS : Longest Increasing Subsequence)

최장 증가 수열이란 주어진 수열의 부분수열중 증가하면서 가장 길이가 긴 부분수열을 의미한다. 예를 들어, 주어진 수열 {10, 20, 10, 30, 20, 50} 이라면, 최장 증가 수열은 {10, 20, 30, 50} 이며 길이는 4이다. 최장 증가 수열은 동적계획법과 이분탐색으로 해결할 수 있다. 대표적인 문제로는 백준 14002와 백준 14003을 참고하면 좋을 것 같다.

동적계획법(DP)를 이용한 풀이의 시각화 자료를 보고싶다면 링크를 참고하는 것을 추천한다. 참고로 위 링크에서는 다양한 알고리즘 기법들의 시각화 자료를 제공한다.

동적계획법을 이용한 풀이 (파이썬)

흔히 DP라 불리는 동적계획법은 $O(n^2)$ 의 시간복잡도가 소요된다.

seq = [10,20,10,30,20,50]
n = len(seq)
dp = [1 for _ in range(n)]
subseq = [[i] for i in seq]

## 최장 증가 수열의 길이를 DP에 저장 & 수열의 각 인덱스에서 나올 수 있는 최장 증가 수열을 저장
for i in range(n):
    for j in range(i):
        if seq[i] > seq[j] and dp[j]+1 > dp[i]:
            dp[i] = dp[j] + 1
            subseq[i] = subseq[j] + [seq[i]]
## 위에서 구한 최장 증가 수열의 길이와 동일한 길이를 갖는 최장 증가 수열을 찾는 과정
LIS = []
LIS_length = max(dp)
for sub in subseq:
    if len(sub) == LIS_length:
        LIS = sub
print(LIS)

## output
## [10, 20, 30, 50]

이분탐색을 이용한 풀이 (파이썬)

동적계획법을 이용하여 최장 증가 수열 문제를 풀면 위에서도 언급했듯이 $O(n^2)$ 의 시간복잡도가 소요된다. 이를 개선하기 위해서 이분탐색을 활용하며, 이분탐색의 시간복잡도는 $O(logn)$ 이며, 최장 증가 수열 문제를 해결할때는 $O(nlogn)$ 으로 개선시킬 수 있다. 원리는 다음과 같다.

배열의 마지막 요소보다 새로운 수가 크다면 배열에 넣는다.
그렇지 않다면, 이분 탐색을 통해 새로운 수가 들어갈 자리에 넣어준다.

from bisect import bisect_left

INF = 1e9
seq = [10,20,10,30,20,50]
n = len(seq)
idx = [0] * (n+1)
cmp = [-INF]
maxVal = 0

for i in range(n):
    if cmp[-1] < seq[i]:
        cmp.append(seq[i])
        idx[i] = len(cmp) - 1
        maxVal = idx[i]
    else:
        idx[i] = bisect_left(cmp, seq[i])
        cmp[idx[i]] = seq[i]

LIS = []
for i in range(n, -1, -1):
    if idx[i] == maxVal:
        LIS.append(seq[i])
        maxVal -= 1
LIS.reverse()

print(LIS)
## output
## [10, 20, 30, 50]

나올 수 있는 면접 질문

최장 증가 수열 손코딩
최장 증가 수열을 만약 $O(n^2)$ 로 풀었다면, 시간복잡도를 개선하는 방법

참고

기여자

_{Junho Moon}
📦