최장 증가 부분 수열 (LIS) 알고리즘 - DP

LIS 알고리즘이란?

Longest Increasing Subsequence의 줄임말로, 주어진 수열에서 오름차순으로 정렬할 수 있는 가장 긴 부분 수열을 찾는 문제이다. 수열의 길이가 n일 때 O(n logn)의 시간복잡도로 해결이 가능하다. 

 

예를 들어보자. 주어진 리스트가 [1, 4, 5, 2, 3, 6, 7, 8, 5] 라고 하면, LIS는 [1, 2, 3, 6, 7, 8]이 된다. 

LIS 알고리즘을 구현하는 방법은 완전탐색, Dynamic Programming, Binary Search가 있다. 

우선 DP에 대해서 알아본다.

---

다이나믹 프로그래밍 - O(N^2)

0번 인덱스만으로 부분 수열을 구성하는 경우는 길이가 1이다. 즉 최소 길이는 1이다. 

그 뒤로는 이전 인덱스의 모든 값과 비교한다. 각 인덱스에서 해당 인덱스까지 나올 수 있는 부분 수열의 최대 길이는 dp라는 리스트로 초기화한다. 초기에는 dp = [1, 1, ..., 1]이 된다.

 

1번 인덱스가 0번 인덱스보다 큰 경우는 ( list[0], list[1] ) 의 부분수열을 만들 수 있다. 

dp[2]는 dp[0], dp[1]과 비교한다. 예를 들어 2번 인덱스의 값이 1번 인덱스의 값보다 큰 경우는 1번 인덱스까지 부분된 부분수열에 list[2]의 값을 추가한 (list[0], list[1], list[2])의 부분수열이 만들어진다. 

 

이러한 과정을 반복하면 dp[ k ]를 구하기 위해서는 array[ j ], (k = 0, 1, .., k-1) 에 대해서 array[ k ]와 비교한 후, array[ k ]가 array[j]보다 큰 경우, dp[ k ] = dp[ j ] + 1로 업데이트한다.

 

이 때, dp[k]가 이미 dp[j] + 1보다 큰 경우는 업데이트를 하지 않는다.(최대 길이를 구하기 때문)

이 과정은 array[ j ] < array[ k ]를 만족하는 j에 대해서 dp[ j ]의 최댓값에 1을 더하는 것과 같다.

 

이렇게 구해진 dp 리스트의 최댓값이 최대 증가 부분 수열의 길이이다.

N = int(input())
lst = list(map(int, input().split()))
dp = [1] * N

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

print(max(dp))