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

 

 

 

 

 

 

🧐 부분 수열(Subsequence)

길이 n인 수열(sequence, ordered list) $S = a_1, a_2, ... a_n$ 이 주어졌을 때,

수열 $S' (= a_{i1}, a_{i2}, ..., a_{ik})$ 가 $1 \leq i1 < i2 < ... < ik \leq n$ 를 만족할 경우,

$S'$ 를 $S$ 의 subsequence라 합니다.

 

 

 

 

 

 

 

🧐 증가 수열(Increasing sequence)

수열 S = $a_1, a_2, ..., a_n$ 에 대하여

$a_1 < a_2 < ... < a_n$ 일 때, increasing sequence라 합니다.

 

 

 

 

 

 

🧐 감소하지 않는 수열(Non-decreasing sequence)

수열 S = $a_1, a_2, ..., a_n$ 에 대하여

$a_1 \leq a_2  \leq ...  \leq a_n$ 일 때, non-decreasing sequence라 합니다.

 

 

 

 

 

 

 

 

 

🧐 최장 증가 부분 수열(Longest Increasing Subsequence, LIS)

어떠한 수열 S 에 대하여, S에서 가장 긴 증가 부분 수열을 LIS라 정의합니다.

 

 

 

 

 

 

 

 

 

 

 

🧐 LIS 구하기

DP 문제를 해결하는 방법에 맞추어 LIS의 길이를 구하는 문제를 해결해 보도록 하겠습니다.

 

 

1. 문제를 정확하게 정의합니다.

Problem: $S = a_1, a_2, ..., a_n$ 에서 LIS의 길이 구하기

 

 

 

2. 정의된 문제에 대한 Subproblem을 세웁니다.

Subproblem:
첫 i개의 요소들($a_1, a_2, ..., a_i$)로 이루어진 수열에서,
$a_i$로 끝나는 증가하는 부분수열들 중 가장 긴 부분수열의 길이 구하기

$a_i$로 끝나는 증가하는 부분수열들 중 가장 긴 부분수열의 길이를 L(i)로 정의하겠습니다.

 

 

 

 

3.  Subproblem을 이용하여 Recurrence Relation을 세웁니다.

recurrence relation:
$L(i) = 1 + max_{j<i, \; a_j < a_i}L(j)$
즉 i보다 작은 모든 j들 중, $a_j$ < $a_i$ 를 만족하는 j에 대한 L(j)값들 중 최댓값에 1을 더한 것이 L(i)가 됩니다.

 

S의 LIS의 길이는 $max_{i=1}^{n}L(i)$ 가 됩니다.

 

 

 

 

 

 

 

 

 

 

 

 

🧐 Pseudocode

 

 

 

 

 

 

 

 

 

 

🧐 예시

 

 

 

이를 통해 LIS의 길이는 4라는 것을 알 수 있습니다.

 

 

 

 

 

 

 

 

 

 

 

🧐 실제 최단 경로 구하기

실제 LIS를 구하고 싶다면 L(i) = L(j) + 1 로 업데이트 할 때마다 해당 LIS의 직전 요소가 $a_j$ 라는 것을 따로 저장해준 후,

이를 따라 역추적하는 과정을 통해 알아낼 수 있습니다.

 

 

 

 

위의 예시의 경우 아래와 같이 직전 요소를pre로 따로 저장해 준 후,

8(->6), 6(->5), 5(->2), 2(->0) 을 통해 LIS를 구할 수 있습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 시간 복잡도

L(i) 를 계산할 때 조건에 맞는 L(i) 를 검색 : $O(i - 1)$

이때 i 는 n 번 진행되므로, 총 $O(n^2)$

모든 L(i) 계산 뒤, 해당 값이 제일 큰 i 찾기 : $O(n)$

따라서 총 $O(n^2)$ 의 시간 복잡도를 갖습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🧐 이분 탐색을 이용한 더 빠른 알고리즘

https://ttl-blog.tistory.com/486

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