최장 증가 부분 수열(LIS)-개념

최장 증가 부분 수열 문제는 동적 계획법(DP)로도 풀 수 있는 유명한 알고리즘 문제입니다.

 

최장 증가 부분 수열 정의

 

어떤 임의의 수열이 주어질 때, 이 수열에서 몇개의 수들을 제거해서 부분수열을 만들 수 있습니다.

이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라고 합니다.

 

먼저 예시를 들겠습니다.

[2,11,4,55,7,9,13,3] 이라는 수열이 있습니다. 이제 이것을 최장 증가 부분 수열로 정리 하겠습니다.

1. 11 제거 [2,4,55,7,9,13,3]

2. 55제거 [2,4,7,9,13,3]

3. 3제거 [2,4,7,9,13]

이렇게 LIS가 나올수 있는데 한 수열 내에서 여러개의 LIS가 나올수 있습니다.

 

먼저 O(N^2) 알고리즘에 대해서 설명하겠습니다.

 

O(N^2)

 

먼저 dp[ ]라는 리스트를 정의 하겠습니다.

dp[i]는 array[i]를 마지막 값으로 가지는 가장 긴 증가 부분 수열의 길이입니다.

array[i]가 어떤 증가부분수열의 마지막 값이 되기 위해서는 array[i]가 추가되기 전 증가부분수열의 마지막 값이 array[i]보다 작은 값이여야 합니다.

따라서 array[i]를 마지막 값으로 가지는

'가장 긴'

증가부분수열의 길이는 array[i]가 추가될 수 있는 증가부분수열 중 가장 긴 수열의 길이에 1을 더한 값이 됩니다.

 

먼저 테이블을 통해 LIS를 구하는 과정을 보겠습니다.

 

 

먼저 초기 dp 값을 1로 지정해 주겠습니다. 왜냐하면 처음 LIS의 길이는 1부터 시작하기 때문입니다.

 

index	0	1	2	3	4	5	6	7
array	2	11	4	55	7	9	13	3
dp	1

이제 i=1일때를 확인하겠습니다. 먼저 array[1] = 11입니다. 11은 array[0]=2 뒤에 붙을 수 있습니다. 따라서 dp[1] = dp[0] + 1 = 2입니다.

 

index	0	1	2	3	4	5	6	7
array	2	11	4	55	7	9	13	3
dp	1	2

다음은 i=2일때를 확인하겠습니다.

array[2] = 4입니다. 4는 array[0]= 2 뒤에 붙을수 있습니다.

따라서 dp[2] = dp[0] + 1 = 2입니다.

 

index	0	1	2	3	4	5	6	7
array	2	11	4	55	7	9	13	3
dp	1	2	2

다음은 i=3일때를 확인하겠습니다.

array[3] = 55입니다. 55는 array[0],array[1],array[2]에 붙을 수 있습니다. 여기서 dp의 최댓값은 2이므로 dp[3] = dp[2] + 1 = 3 입니다.

 

 

index	0	1	2	3	4	5	6	7
array	2	11	4	55	7	9	13	3
dp	1	2	2	3

마찬가지로 다른 숫자들도 쭉쭉 진행하겠습니다.

 

index	0	1	2	3	4	5	6	7
array	2	11	4	55	7	9	13	3
dp	1	2	2	3	3	4	5	2

이제 LIS는 dp들 중에서 최댓값인 항목입니다. 따라서 5가 LIS인것을 확인할 수 있습니다.

 

O(N log N)일때

 

두번 째 알고리즘은 첫 번째 알고리즘을 개량한 형태입니다. 두 번째 알고리즘은 다음과 같은 의문에서 시작합니다.

dp[i]를 계산하기 위해 꼭 array[0] ~ array[i-1]을 다 봐야하는가?

위에 있는 알고리즘에서 array를 전체다 훑어본 것은 array[i]보다 작은 array[j]를 가지는 j들 중에서 가장 큰 dp[j]를 찾기 위함입니다.

만약 dp[j] = k를 만족하는 j 중 array[j]의 값이 가장 작은 j만 어딘가에 저장해 놓으면, 나중에 dp[j]

 

먼저 시작은 위에있는 알고리즘과 같습니다.

 

index	0	1	2	3	4	5	6	7
array	2	11	4	55	7	9	13	3
dp	1

하지만 여기서 다른점은 하나의 표가 더 있다고 생각하겠습니다. 그리고 이 표를 X라 하겠습니다.

dp[i] : [1]

array[i] : [2]

 

---

 

이제 index가 1일때를 보겠습니다.

array[1] = 11입니다. 이때 X를 살펴보면 가장 마지막 array[i]가 2이고 이것은 11보다 작습니다. 이 말은 현재 array[1] 앞의 수들로 만든 가장 긴 증가 부분 수열 중 마지막 값이 2인 증가 부분 수열이 있다는 말입니다. 그리고 array[1]을 그 뒤로 붙일 수 있습니다. 따라서 dp[1] = dp[0] + 1 = 2입니다.

 

index	0	1	2	3	4	5	6	7
array	2	11	4	55	7	9	13	3
dp	1	2

테이블 X

dp[i] : [1,2]

array[i] : [2,11]

---

다음은 index가 2일때를 보겠습니다.

array[2] = 4입니다. 이때 X를 살펴보면 가장 마지막 array값이 11이고 이것은 4보다 큽니다.

또한 4는 2와 11사이의 값입니다. 따라서 dp[2] = 1+1 = 2입니다.

테이블 x에서 dp[i] = 2일때 array[i]의 값은 11인데 index가 2일때 4가 더 작으므로 4로 갱신해 주겠습니다. 이말은 LIS의 길이가 2인 수열중 끝이 11로 끝나는 수열과 끝이 4로 끝나는 수열중 끝 값이 더 작은 4를 x에 저장해 놓겠다는 것입니다.

갱신한 값들은 다음과 같습니다.

 

index	0	1	2	3	4	5	6	7
array	2	11	4	55	7	9	13	3
dp	1	2	2

테이블 X

dp[i] = [1,2]

array[i] = [2,4]

---

다음은 index가 3일때를 보겠습니다.

array[3] = 55입니다. 이때 x를 살펴보면 마지막 array값이 4이고 이것은 55보다 작습니다.

따라서 dp[2] = 2 + 1 = 3입니다.

 

index	0	1	2	3	4	5	6	7
array	2	11	4	55	7	9	13	3
dp	1	2	2	3

테이블 X

dp[i] = [1,2,3]

array[i] = [2,4,55]

---

다음은 index가 4일때를 보겠습니다.

array[4]는 7입니다. 이때 x를 살펴보면 마지막 array값이 55이고 이것은 7보다 큽니다.

또한 7은 4와 55사이 수 입니다. 따라서 55를 이제 7로 갱신하겠습니다.

 

index	0	1	2	3	4	5	6	7
array	2	11	4	55	7	9	13	3
dp	1	2	2	3	3

테이블 x

dp[i] = [1,2,3]

array[i] = [2,4,7]

---

다음은 index가 5일때를 보겠습니다.

array[5] = 9이고 x를 살펴보면 마지막 array[i]가 7이고 이것은 9보다 작습니다.

따라서 dp[3] = 3+1 = 4

 

index	0	1	2	3	4	5	6	7
array	2	11	4	55	7	9	13	3
dp	1	2	2	3	3	4

테이블 x

dp[i] = [1,2,3,4]

array[i] = [2,4,7,9]

---

다음은 index가 6일때를 보겠습니다.

array[6] = 13이고 x를 살펴보면 마지막 array[i]가 9이고 이것은 13보다 작습니다.

따라서 dp[4] = 4+1 = 5

 

index	0	1	2	3	4	5	6	7
array	2	11	4	55	7	9	13	3
dp	1	2	2	3	3	4	5

테이블 x

dp[i] = [1,2,3,4,5]

array[i] = [2,4,7,9,13]

---

마지막으로 index가 7일때를 보겠습니다.

array[7] = 3이고 x를 살펴보면 마지막 array[i]가 13이고 이것은 3보다 큽니다.

또한 3은 2와 4 사이의 숫자입니다. 따라서 4를 3으로 갱신하겠습니다.

또한 dp[7] = 1+1 =2로 갱신하겠습니다.

 

index	0	1	2	3	4	5	6	7
array	2	11	4	55	7	9	13	3
dp	1	2	2	3	3	4	5	2

테이블 x

dp[i] = [1,2,3,4,5]

array[i] = [2,3,7,9,13]

 

여기서 테이블 x는 항상 오름차순으로 정렬되어 있으므로 이진탐색을 이용할 수 있습니다. 이진 탐색을 이용해서 현재 array[i]보다 작은 a[j]를 테이블 x에서 찾습니다. 그리고 그 a[j]에 해당하는 dp값에 1을 더하면 dp[i]를 쉽게 구할 수 있습니다. 따라서 이것은 O(NlogN)의 시간 복잡도를 가집니다.