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

전에서 관련 알고리즘을 찾아보고 코딩 문제를 해결했던 것 같은데 오랜만에 다시보니 기억이 나지 않아 이번에 정리해보고자 한다. 언어는 python을 사용해서 진행해보고자 한다.

 

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

해당 알고리즘은 DP(Dynamic Programming) 문제로 자주 나오고 있으며 O(N^2)의 시간복잡도를 가지고 있는 알고리즘과 O(NLogN)의 시간복잡도를 가지고 있는 알고리즘이 존재한다.

 

---

[개념]

LIS는 어떤 수열에서 만들 수 있는 부분수열 중에서 가장 길면서 오름차순을 유지하는 수열이다. 여기서 부분 수열이란 주어진 수열에서 일부 수를 뽑아내어 만든 수열을 의미한다. 

2

5

3

1

4

7

6

 

예를 든다면 위에 주어진 수열에서 부분 수열은 아래의 예처럼 뭐든지 될 수 있다.

2

3

1

4

7

 

3

1

6

 

그 중 LIS는 가능한 부분수열들 중 가장 길면서 오름차순을 유지해야 하기 때문에 이러한 수열이 LIS가 될 수 있을 것이다.

2

3

4

7

 

2

3

4

6

이처럼 LIS와 관련한 문제에서는 LIS 결과가 1개가 아닌 여러 개가 나올 수 있기 때문에 1) LIS의 길이를 묻거나 2) 될 수 있는 수열이 뭔지 여러 개의 정답을 요구한다던가 3) 나올 수 있는 수열 중 합이 가장 큰 값을 구하도록 요구한다.

 

---

[알고리즘]

1) O(N^2)의 시간복잡도를 가지는 알고리즘( 길이만 구하는 경우 )

 

O(N^2)의 시간복잡도를 가진다는 의미는 어느정도 예상이 가듯이 이중 for문이 들어간다는 이야기일 것이다. 그만큼 간단하지만 런타임이 오래 걸릴 것이라고 예상할 수 있다.

 

알고리즘 Logic

1. 주어진 수열과 같은 크기의 dp 배열을 선언하고 해당 배열에 1로 초기화를 시킨다. dp[i] = i번째 원소를 포함하는 LIS의 최대 원소 개수 2.  현재 위치(i)보다 이전에 있는 원소(j)가 작은지 확인한다. ( 0 <= j <  i ) 3. 작은 경우, dp[i]와 dp[j] +1 중 dp의 최댓값을 구하고 이를 dp[i]에 넣는다. 4. dp의 원소 중 가장 큰 원소가 LIS의 최대 길이가 된다.

 

arr	2	5	3	1	4	7	6
dp	1	2	2	1	3	4	4

 

i = 4인 경우를 생각해보면,

i = 4, j = 0  dp[4] = 1( init data)

arr[0]= 2 <  4 =arr[4]   dp[4] = max(dp[0], dp[4]) + 1 = 1 + 1 = 2

 

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

arr[1]= 5 >  4 =arr[5] 

 

i = 4, j = 2 dp[4] = 2

arr[2]= 3 <  4 =arr[4]   dp[4] = max(dp[2], dp[4]) + 1 = 3

 

i = 4, j = 3 dp[4] = 3

arr[3]= 1 <  4 =arr[4]   dp[4] = max(dp[3], dp[4]) + 1 = 3 + 1 = 4

 

length = int(input());

arr = list(map(int, input().split()));
dp = [1 for i in range(length)];

for i in range(length):
    for j in range(i):
    	if (arr[j] < arr[i]):
        	dp[i] = max(dp[i], dp[j] + 1);

print(max(dp));

=> 2중 for문으로 O(N^2)의 시간복잡도를 가지게 된다.

=> 앞에 있는 원소들과 계속하게 비교하게 되어 불필요한 반복이 일어나고 있다.

---

2) O(NLogN)의 시간복잡도를 가지는 알고리즘( 길이만 구하는 경우 )

 

시간을 가장 만만하게 줄일 수 있는 아이디어로는 이진탐색으로 LogN의 시간복잡도로 줄일 수 있을 것이다. 다만 이진탐색을 하기 위한 기본 조건이 정렬인 만큼 정렬에 신경을 써야한다. 

또한 현재는 길이에만 관심이 있기 때문에 최대한 앞에서 낮은 수들을 골라야 긴 수열을 만들기에 유리하다.

i = arr 순회 idx

알고리즘 Logic

1. dp를 arr[0]으로 초기화시킨다. dp = 만들 수 있는 LIS들 중 하나. 2.  현재 존재하는 dp의 맨 마지막 원소(-1)보다 현재 위치(i)의 원소가 더 크다면 dp에 맨 뒤에 추가한다. 3. 현재 존재하는 dp의 맨 마지막 원소보다 현재 위치의 원소가 작거나 같다면 기존 dp에서 현재 위치의 원소가 들어갈 자리를 찾아서 해당 위치에 있는 원소 대신에 들어간다. 4. dp의 길이를 출력한다.

1) i = 0 (초기화)

arr	2	5	3	1	4	7	6
dp	2

 

2)  i = 1 dp[-1] <  arr[1]     

=>  dp에 arr[1]를 추가

arr	2	5	3	1	4	7	6
dp	2	5

 

3)  i = 2 dp[-1] >  arr[2]     

=> 맨 마지막 원소보다 작으므로 [2,5] 배열에서 arr[2]의 자리를 이진탐색을 통해 찾고 해당 위치에 있는 원소를 대체

arr	2	5	3(i)	1	4	7	6
dp	2	3

 

4)  i = 3 dp[-1] >  arr[3]   

=> 맨 마지막 원소보다 작으므로 [2,3] 배열에서 arr[3]의 자리를 이진탐색을 통해 찾고 해당 위치에 있는 원소를 대체

arr	2	5	3	1(i)	4	7	6
dp	1	3

 

5)  i = 4 dp[-1] <  arr[4]   

=>  dp에 arr[4]를 추가

arr	2	5	3	1	4(i)	7	6
dp	1	3	4

 

6)  i = 5 dp[-1] <  arr[5]

 =>  dp에 arr[5]를 추가

arr	2	5	3	1	4	7(i)	6
dp	1	3	4	7

 

7)  i = 6 dp[-1] >  arr[6]  

=> 맨 마지막 원소보다 작으므로 [1,3,4,6] 배열에서 arr[6]의 자리를 이진탐색을 통해 찾고 해당 위치에 있는 원소를 대체

arr	2	5	3	1	4	7	6(i)
dp	1	3	4	6

import bisect;

length = int(input());
arr = list(map(int, input().split());
dp= [arr[0]];

for i in range(1, length):
    if dp[-1] < arr[i]:
        dp.append(arr[i]);
    else:
        idx = bisect.bisect_left(dp, arr[i]);
        dp[idx] = arr[i];

print(len(dp))

=> 밖에 있는 for문과 내부의 bisect(이진탐색)으로 N*LogN의 시간 복잡도를 가지게 된다.

=> 이러한 방법으로는 LIS의 길이만 구할 수 있다.

---

+a) LIS를 이루는 부분 수열 자체를 구해야 하는 경우

 

O(N^2)의 시간복잡도를 가지는 알고리즘의 결과.

arr	2	5	3	1	4	7	6
dp	1	2	2	1	3	4	4

 

알고리즘 Logic

1. dp에서 최댓값을 가지는 idx를 구해서 idx를 줄여가면서 차례대로 수가 나오는 것(-1씩 떨어도록)을 채택한다. 2. 나온 수를 reverse시키면 LIS가 나오게 된다.

 

arr	2(V)	5	3(V)	1	4(V)	7	6(V)
dp	1	2	2	1	3	4	4

 

maxL = max(dp)
maxIdx = dp.index(maxL)
lis = [];

while (maxIdx >= 0):
	if dp[maxIdx] == maxL:
    	lis.append(arr[maxIdx]);
        maxL -= 1;
    maxIdx -= 1;
    
lis.reverse();
print(lis)

 

관련문제

2023.02.03 - [코테/LeetCode] - [python3] 1626. Best Team With No Conflicts