[Algorithm] 최장 증가 부분 수열(LIS)

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다.

• {6, 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 경우, LIS는 {2, 5, 8, 7} 이고, 길이는 4
• {2, 5}, {2, 7} 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것은 {2, 5, 8, 7}
• {10, 20, 10, 30, 20, 50} 이라는 배열이 있을 경우, LIS는 {10, 20, 30, 50} 이고, 길이는 4

D[i] = arr[i]를 마지막 원소로 가지는 부분 수열의 최대길이 라고 정의할 때, 가장 긴 증가하는 부분 수열을 계산하는 점화식을 작성해보면, 다음과 같다. (DP 테이블의 값은 모두 1로 초기화한다.)

 

모든 0 <= j < i 에 대하여, D[i] = max(D[i], D[j] + 1) if arr[j] < arr[i]

 

이를 소스코드로 작성해보면 다음과 같다.

 

x = 수열 A의 크기

arr = 수열 A를 이루고 있는 A(i)를 담은 배열

dp = arr[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이

 

x = int(input())

arr = list(map(int, input().split()))

dp = [1 for i in range(x)]

for i in range(x):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

 

dp[i]의 값을 1로 초기화하고 현재 위치(i)보다 이전에 있는 원소(j)가 작은지 확인한다. (크거나 같으면 가장 긴 부분 수열이 될 수 없음) 작다면 현재 위치의 이전 숫자 중 dp의 최댓값을 구하고 그 길이에 1을 더해주면 된다.

 

이 코드의 시간복잡도는 N개의 수들에 대해서 현재 위치 이전의 모든 수를 다 훑어봐야 하므로 O(N^2)의 시간복잡도를 가진다. 따라서 문제에 따라서 시간 초과가 뜰 수도 있다.

 

그렇다면 N개의 수들에 대해서 현재 위치 이전의 모든 수를 훑어보지 않고 풀 수 있는 방법은 없을까?

dp[i]를 구하기 위해 dp[0] ~ dp[i]의 최댓값을 알고 있다면 반복을 할 필요가 없지 않을까? 따라서 이진 탐색 알고리즘을 이용하여 다음과 같이 소스코드를 짤 수도 있다.

 

x = 수열 A의 크기

arr = 수열 A를 이루고 있는 A(i)를 담은 배열

dp = arr[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이

 

x = int(input())

arr = list(map(int, input().split()))

dp = [1 for i in range(x)]

for i in range(x):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

 

dp를 arr[0]으로 초기화하고 현재 위치(i)가 이전 위치의 원소들보다 크면 dp에 추가한다.

현재 위치(i)가 이전 위치의 원소보다 작거나 같으면, bisect.bisect_left로 이전 위치의 원소 중 가장 큰 원소의 index값을 구한다. 그리고 dp의 index 원소를 arr[i]로 바꿔준다.

 

이 코드의 시간 복잡도는 N개의 수들에 대해 이진 탐색을 진행하므로 O(NlogN)의 시간 복잡도를 가진다.

 

 

LIS의 길이뿐만 아니라 원소들까지 구하고 싶다면 어떻게 해야할까? 이는 다음과 같이 코드를 작성하면 된다.

x = 수열 A의 크기

arr = 수열 A를 이루고 있는 A(i)를 담은 배열

dp = arr[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이

max_dp = 가장 긴 증가하는 부분 수열의 길이

max_idx = max_dp의 위치

lis = 가장 긴 증가하는 부분 수열을 담을 배열

 

x = int(input())
arr = list(map(int, input().split()))

dp = [1 for i in range(x)]

for i in range(x):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j] + 1)

max_dp = max(dp)
print(max_dp)

max_idx = dp.index(max_dp)
lis = []

while max_idx >= 0:
    if dp[max_idx] == max_dp:
        lis.append(arr[max_idx])
        max_dp -= 1
    max_idx -= 1

lis.reverse()
print(*lis)

 

max_idx의 값부터 시작하여 거꾸로 순회하며 arr의 원소를 추가하면 된다.