[알고리즘] LIS(최장 증가 부분 수열)

LIS 알고리즘

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

arr = [10, 30, 10, 40, 30, 50] 배열이 있다고 하자.
이때 가장 긴 증가하는 부분 수열의 길이를 구하라고 하면, 답은 [10, 30, 40, 50]의 길이인 4이다.

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

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

소스코드를 보자

arr = [10, 30, 10, 40, 30, 50]
n = len(arr)
dp = [1] * n
 
for i in range(1, n):
  for j in range(i):
    if arr[j] < arr[i]:
      dp[i] = max(dp[i], dp[j] + 1)
      
print(dp)
print(max(dp))
'''
[1, 2, 1, 3, 2, 4]
4
'''

---

if문을 만족할 때마다 dp를 출력해보았다.

arr = [10, 30, 10, 40, 30, 50]

• i = 1

[1, 2, 1, 1, 1, 1]

• i = 2

• i = 3

[1, 2, 1, 2, 1, 1]
[1, 2, 1, 3, 1, 1]
[1, 2, 1, 3, 1, 1]

• i = 4

[1, 2, 1, 3, 2, 1]
[1, 2, 1, 3, 2, 1]

• i = 5

[1, 2, 1, 3, 2, 2]
[1, 2, 1, 3, 2, 3]
[1, 2, 1, 3, 2, 3]
[1, 2, 1, 3, 2, 4]
[1, 2, 1, 3, 2, 4]

관련 문제 정리

• (백준) 병사 배치하기