[Algorithm] 최장 증가 수열 (LIS)

DP 문제를 풀다보니 자주 등장하는 유형이 있어 구글링을 해보니 '최장 증가 부분 수열'이라는 유형이였다.

 

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

• DP 문제로 자주 나오는 유형
• O(N^2)의 시간 복잡도 아니면 O(NlogN)의 시간 복잡도를 가진다.
• 어려운 문제의 경우 당연히 후자..

 

개념

• 단어 그대로 가장 긴 증가하는 부분 수열을 구하는 것
• 어떤 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 '오름 차순을 유지하면 증가하는 부분 수열'
• 즉, 만들 수 있는 부분 수열 중 가장 길면서 오름차순을 유지하는 수열이 LIS

위의 여러 수열 중 가장 길이가 긴 수열은 [2,3,5,6,7] 뿐만 아니라 [1,3,5,6,7]도 가능하다. LIS는 반드시 하나인 것은 아니다!

 

알고리즘

#  O(N^2)의 시간복잡도

 

[참고] 백준 11503번 https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

1. 수열의 길이와 같은 DP배열을 하나 선언한다.
2. 수열을 처음부터 끝까지 순서대로 1개씩 탐색한다. (현재 위치 = i)
   1. dp[i]에 넣을 값을 초기화해준다.(val)
   2. 현재 위치(i)보다 이전에 있는 원소(j)가 현재 원소보다 작은지 체크한다. (크거나 같으면 LIS 원소가 될 수 없다.)
   3. 작다면, 현재 위치의 이전 숫자 중, dp 최댓값을 구하고 그 길이에 1을 더해주면된다.

n = int(input())

arr = list(map(int, input().split()))
# 1
dp = [1 for i in range(a)]
# 2
for i in range(a):
	for j in range(i):
    	if arr[i] > arr[j]:
        	# 3
            dp[i] = max(dp[i], dp[j]+1)
            
print(max(dp))

11053번의 예제 1 [10, 20, 10, 30, 20, 50] 리스트를 예로 들어보자. i=4 라고 가정

• i = 4, j = 0 이면 arr[4] =20 arr[0]=10이므로 dp[4] = 2가 된다.
• i = 4, j = 1 이면 arr[4] =20 arr[1]=20이므로 continue
• i = 4, j = 2 이면 arr[4] =20 arr[2]=10이므로 dp[4] = 3가 된다.
• i = 4, j = 3 이면 arr[4] =20 arr[3]=30이므로 continue

위와 같이 구한다면 현재 위치 이전의 모든 수를 훑어보기 때문에 O(N^2)

 

 

# O(NlogN) - Binary Search

 

[참고] 백준 12015  https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

처음 푼 것과 같이 DP로 풀게 되면 시간 초과의 늪에 빠진다...

이진 탐색 방식을 이용하여 dp[i]를 구하기 위해 dp[0] ~ dp[i-1]의 최댓값을 저장해준다면 반복하지 않아도 되는 것을 알 수 있다.

1. dp를 arr[0]로 초기화
2. 현재 위치(i)가 이전 위치의 원소들보다 크면 dp에 추가
3. 현재 위치(i)가 이전 위치의 원소보다 작거나 같으면, bisect.bisect_left로 이전 위치의 원소 중 가장 큰 원소의 index 값을 구한 후 dp의 index 원소를 arr[i]로 바꿔준다.
   • bisect.bisect_left(arr,x): arr가 정렬되어있따는 가정하에 x값이 들어갈 위치 반환
   • 즉 기존 dp가 1236이고 현재 위치의 값이 5라면 dp의 6인덱스에 5를 넣어준다.
4. dp의 길이를 출력해주면 된다.

import bisect

x = int(input())
arr = list(map(int, input().split()))

dp = [arr[0]]

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

print(len(dp))

• 이 경우 N개의 수들에 대해 이진 탐색을 진행하므로 O(NlogN)의 시간 복잡도

다만, 이 경우, LIS의 원소들을 구할 수 없기 때문에 추가적인 작업을 해주어야 한다.

또한, 수열의 크기가 1,000,000과 같이 큰 수열이라면 첫번째 방법으로는 풀 수 없다.. 

 

어려운 문제는 더 공부한 이후에 업데이트 해야겠다!