[Python] 가장 긴 증가하는 부분 수열 (LIS)
LIS(Longest Increasing Subsequence) 알고리즘
주어진 수열에서 일부 원소를 제거해 순서를 유지한 채 가장 길게 증가하는 부분 수열을 찾는 문제다.
O(N^2) 풀이(DP)와 O(N log N) 풀이(이분 탐색)가 있다.
1️⃣ DP 풀이 (O(N^2))
문제: 백준 11053번
1
2
3
4
5
6
7
8
9
10
11
12
13
# dp
N = int(input())
dp = [0 for _ in range(N+1)]
# dp[i]: i번째 원소를 마지막으로 하는 증가하는 부분 수열들 중 가장 긴 것의 길이
A = [0] + list(map(int, input().split()))
for i in range(1, N+1):
max_num = 0
for j in range(i):
if A[j] < A[i]:
max_num = max(max_num, dp[j])
dp[i] = max_num + 1
print(max(dp))
dp로 풀 수 있다. 이중 반복문으로, 시간복잡도는 O(N^2)다.
문제: 백준 14002번
이 문제는 앞선 문제에서 추가로 부분 수열을 출력해야 하는 문제다.
이때 dp[i]가 가장 큰 값부터 역순으로 추적해야 한다. 역순으로 안 찾고 앞에서부터 찾으면, 다음에 나오는 더 작은(=최적화된) 값들을 놓치기 때문에 틀린다.
1
2
3
4
5
6
7
Input
7
10 20 30 21 22 23 40
Output
6
10 20 30 22 23 40 (땡!)
그래서 하단에 이렇게 코드를 추가해야 한다.
1
2
3
4
5
6
7
8
9
10
11
# 부분 수열 출력을 위한 역추적
ans = []
now = max(dp)
for i in range(len(dp)-1, 0, -1):
if dp[i] == now:
ans.append(A[i])
now -= 1
ans.reverse()
for elem in ans:
print(elem, end=' ')
print()
2️⃣ O(N log N) 풀이: 이분 탐색 활용
문제: 백준 12015번
첫번째 문제랑 똑같은데, 이번에는 N이 최대 1,000,000까지로 늘어나서 기존의 O(N^2)풀이로는 시간 초과가 발생한다. 그래서 이번에는 dp가 아닌, 이분 탐색을 이용한 LIS를 사용해야 한다.
과정
- 빈 리스트를 한 개 만든다(이름은
l로 했다). 이 리스트의 길이는 나중에 LIS의 길이가 된다. - 입력된 숫자를 한 개씩 본다.
- 현재
l의 마지막 원소보다 큰 경우,l에 그냥 추가한다. - 작거나 같은 경우, 이분 탐색을 이용해
l의 적절한 위치(lower bound)를 찾은 다음, 해당 위치의 값을 이걸로 교체한다. - 완성된 최종
l의 길이가 LIS의 길이와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input
7
3 5 7 1 2 8 6
과정:
1. [3]
2. [3, 5]
3. [3, 5, 7]
4. [1, 5, 7] (1이 들어와 적절한 위치에 대체)
5. [1, 2, 7] (2가 들어와 적절한 위치에 대체)
6. [1, 2, 7, 8] (8 추가)
7. [1, 2, 6, 8] (6이 들어와 적절한 위치에 대체)
결과: LIS 길이 = 4
Output
4
코드는 다음과 같이 작성했다(파이썬에서는 이분탐색을 위해 bisect 라이브러리의 bisect_left 함수를 사용해도 된다).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def lower_bound(arr, target):
left = 0
right = len(arr) - 1
while left < right:
mid = (left + right) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return right
N = int(input())
A = list(map(int, input().split()))
l = []
for i in range(N):
if i == 0:
l.append(A[i])
else:
if A[i] > l[-1]:
l.append(A[i])
else:
# lower bound 찾아서 갱신
index = lower_bound(l, A[i])
l[index] = A[i]
print(len(l))
이렇게 하면 시간복잡도가 O(NlogN)이 되어서 통과할 수 있다.
문제: 백준 14003번
마지막으로 이 문제를 보자. 이 문제에서는 O(NlogN) 으로 풀면서, 부분 수열 출력도 해야 한다. 이때 중요한 건 LIS 알고리즘으로 구한 l은 LIS의 길이만 유지하는 배열이지, 실제 LIS를 저장하는 것은 아니라는 점이다. 나는 처음에 이걸 간과해서 l을 그냥 출력했다가 틀렸습니다를 받았다(감자!).
1
2
3
4
5
6
7
Input
7
3 5 7 1 2 8 6
Output
4
1 2 6 8 (땡!)
부분 수열을 출력하기 위해서는 중간에 다른 추가적인 작업을 해줘야 한다. 매 요소에서 lower bound 찾아서 갱신하는 과정에서, 해당 요소의 lower bound가 얼마였는지를 따로 bounds 리스트를 만들어 저장해줬다. 그리고 마지막에 bounds를 역추적해서 부분 수열을 찾았다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
.
.
.
N = int(input())
A = list(map(int, input().split()))
l = []
# lower bound를 찾을 때마다 index를 저장해놓고, 그 index를 역추적해서 부분 수열을 찾아야 함
bounds = [0 for _ in range(N)]
for i in range(N):
if i == 0:
l.append(A[i])
bounds[i] = 0
else:
if A[i] > l[-1]:
l.append(A[i])
bounds[i] = len(l) - 1
else:
# lower bound 찾아서 갱신
index = lower_bound(l, A[i])
l[index] = A[i]
bounds[i] = index
print(len(l))
# 부분 수열 출력: 역추적해서 가장 최적화된 부분 수열을 찾아야 함
ans = []
now = max(bounds)
for i in range(len(bounds)-1, -1, -1):
if bounds[i] == now:
ans.append(A[i])
now -= 1
ans.reverse()
for elem in ans:
print(elem, end=' ')
print()
📖 정리
O(N^2)풀이 (DP)O(N log N)풀이 (이분 탐색)- LIS는 저장되지 않는다. 부분 수열 출력을 위해서는 따로 역추적 로직을 추가해야 한다.
어렵다…꼭 복습하자. 근데 전부 풀고 나니까 티어 점수가 엄청 올랐다😊