플레찍었으니 정리해보는 알고리즘 노트 6 - LIS(최장 증가 부분 수열)

최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 알고리즘이란?

주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 문제이다. 이때 부분수열이 연속적이거나 중복되지 않아도 된다.

 

LIS 알고리즘은 크게 시간복잡도가 O(n^2) 인 알고리즘과 O(n logn) 인 알고리즘 두 가지로 구현 가능하다.

 

1. O(n^2) 알고리즘

https://www.acmicpc.net/problem/14002

14002번: 가장 긴 증가하는 부분 수열 4

n = int(input())
lst = list(map(int,input().split()))
dp = [0]*n
indexList = [-1]*n
    
dp[0] = 0
indexList[0] = 0
maxlen = 0

for i in range(1,n):
    for j in range(maxlen,-1,-1):
        if lst[i] > lst[dp[j]]:
            dp[j+1] = i
            indexList[i] = j+1
            if j == maxlen:
                maxlen += 1
            break
        elif j == 0:
            dp[0] = i
            indexList[i] = 0

print(maxlen+1)
stack = []

i = n-1
while maxlen >= 0 and i >= 0:
    if indexList[i] == maxlen:
        stack.append(lst[i])
        maxlen -= 1
    i -= 1
    
while stack:
    print(stack.pop(),end = " ")

DP를 응용해서 구현한다.

주어진 수열을 순차적으로 돌면서 DP 배열에 오름차순으로 숫자를 집어넣으면 된다.

이미 배열에 숫자가 있을 경우 오름차순 정렬을 해치지 않는 곳으로 원래있던 숫자를 대신해서 집어넣으면 된다.

그 후 index배열에 각 수열의 숫자가 들어간 dp 배열의 인덱스를 저장하면 된다.

 

예) 10 20 10 30 50 40 이 수열로 주어졌을 때

수열 1번째 수 10 -> DP 배열: [10] (0번 인덱스에 10 삽입) , indexList [0]

수열 2번째 수 20 -> DP 배열: [10, 20] (1번 인덱스에 20 삽입), indexList [0,1]

수열 3번째 수 10 -> DP 배열: [10, 20, 30] (2번 인덱스에 30 삽입), indexList [0,1,2]

수열 4번째 수 30 -> DP 배열: [10, 20, 30]( 0번 인덱스에 10 삽입), indexList [0,1,2,0]

수열 5번째 수 50 -> DP 배열: [10, 20, 30, 50] (3번 인덱스에 50 삽입), indexList [0,1,2,0,3]

수열 6번째 수 40 -> DP 배열: [10, 20, 30, 40] (3번 인덱스에 40 삽입), indexList [0,1,2,0,3,3]

 

그 후 indexList의 맨 뒤에서부터 0이 될때까지 가장 먼저 나오는 숫자들만 탐색해보면 부분수열을 찾을 수 있다.

예) indexList [0,1,2,0,3,3]

제일 먼저 나오는 3 -> 5번 인덱스

제일 먼저 나오는 2 -> 2번 인덱스

제일 먼저 나오는 1 -> 1번 인덱스

제일 먼저 나오는 0 -> 0번 인덱스

 

따라서 최장 증가하는 부분 수열은 0,1,2,5번 인덱스인 10,20,30,40 이다.

 

2. O(nlogn) 알고리즘

https://www.acmicpc.net/problem/14003

14003번: 가장 긴 증가하는 부분 수열 5

 

n = int(input())
lst = list(map(int,input().split()))
dp = [0]*n
indexList = [-1]*n

maxlen = 0
dp[0] = lst[0]
indexList[0] = 0

for i in range(1,n):
    start = 0
    last = maxlen + 1
    c = 0
    
    while start < last:
        c = int((start+last)/2)
        if dp[c] < lst[i]:
            start = c + 1
        else:
            last = c
    
    dp[start] = lst[i]
    indexList[i] = start
    if start > maxlen:
        maxlen += 1

print(maxlen+1)

stack = []
i = n-1
while maxlen >= 0 and i >= 0:
    if indexList[i] == maxlen:
        stack.append(lst[i])
        maxlen -= 1
    i -= 1
while stack:
    print(stack.pop(),end = " ")

앞선 알고리즘에서 lower_bound를 이용해 시간복잡도를 줄였다.