가장 긴 증가하는 부분 수열
[10, 20, 10, 30, 20, 50]이라는 수열이 있을 때, 오름차순으로 증가하는 부분 수열 중 가장 길이가 긴 수열을 의미한다. 그리고 그 가장 긴 수열의 길이를 찾아주는 알고리즘이 LIS 알고리즘이다. 즉, 위 수열에서는 [10, 20, 30, 50]이 가장 긴 증가하는 부분수열이고 길이는 4이다.
DP
dp를 이용한 방법은 수열의 값을 하나씩 비교하기 때문에 시간 복잡도가 O(n^2)이다. dp를 이용하여 최장 증가 부분 수열의 길이를 찾는 과정을 살펴보자.
과정
증가 부분 수열의 길이가 1이기 때문에 먼저 아래와 같이 dp의 초기값을 1로 설정한다.
array[1]을 살펴보면 array[0]과 비교했을 때 더 크기 때문에 dp[1]에는 dp[0]+1인 2가 들어간다
다음으로 array[2]를 살며보면 array[0]과 비교했을 때 값이 동일하기 때문에 dp[2]에는 dp[2] 그대로 이다. 다음, array[1]과 비교했을 때 값이 더 작기 때문에 dp[2]의 값은 그대로 이다.
array[3]을 살펴보면 array[0]과 비교했을 때 더 크기 때문에 dp[3]은 1증가한 2를 갖는다. array[1]과 비교했을 때도 값이 더 크기 때문에 dp[3]은 dp[1]+1인 3을 갖는다. array[3]과 비교했을 때도 값이 더 크지만 dp[3]=3이고 dp[2]+1=2를 비교했을 때 dp[3]이 더 크기 때문에 값이 변하지 않는다.
이런 방식으로 마지막 인덱스까지 반복하면 아래와 같이 된다.
그렇기 때문에 최장 증가 부분 수열의 길이는 dp 배열의 최댓값이 4가 된다.
코드
n = int(input()) # 수열의 길이
array = list(map(int, input().split())) # 주어진 수열
# DP 테이블 1로 초기화
dp = [1] * n
for i in range(1, n):
for j in range(0, i):
if array[j] < array[i]:
dp[i] = max(dp[i], dp[j] + 1)
# 가장 긴 증가하는 부분 수열의 길이값
result = max(dp)
print(result)Binary Search
이분 탐색을 이용한 방법은 모든 수열의 값을 일일히 비교하지 않아도 되기 때문에 시간 복잡도가 O(nlogn)이다. 이분 탐색으로 할 때는 x와 dp 두가지가 필요하다.
과정
dp[0]에는 1 x에는 배열의 첫번째 값을 넣어주고 시작한다.
array[1]의 값이 x배열의 마지막 값인 10보다 크기 때문에 x 배열에 array[1]을 넣어준다. dp에는 증가 부분 수열의 길이가 1증가했기 때문에 dp배열의 마지막 값에서 1 증가한 값을 넣어준다.
다음으로 array[2]를 보면 x의 마지막 값보다 작기 때문에 x 배열 어디에 들어갈 수 있을지 이분탐색을 이용해 찾는다. array[2]의 값은 x[0]에 들어갈 수 있기 때문에 x[0]을 array[2]의 값으로 바꾸어준다.
array[3]을 보면 x의 마지막 값보다 크기 때문에 x 배열의 뒤에 값을 넣어주고 dp도 마지막 값에서 1증가한 값을 넣어준다.
위 과정을 반복하면 아래와 같은 결과가 나온다.
그렇기 때문에 최장 증가 부분 수열의 길이는 4이고 수열의 값들을 x인것을 확인할 수 있다. 최장 증가 부분 수열의 길이만 알 수 있는 dp와는 달리 최장 증가 부분 수열도 찾을 수 있다.
코드
from bisect import bisect_left
array = [5, 2, 1, 4, 3, 5]
dp = [1]
x = [array[0]]
for i in range(1, len(array)):
if array[i] > x[-1]: # 현재 값이 x 배열의 마지막 값보다 클 경우
x.append(array[i]) # x 배열에 현재 값을 추가해 주고
dp.append(dp[-1] + 1) # 증가 부분 수열의 길이를 1 증가시킨다.
else: # 그렇지 않을 경우
idx = bisect_left(x, array[i]) # 현재 값이 x 배열의 몇 번째 인덱스에 들어갈 수 있는지를 찾아서
x[idx] = array[i] # x 배열의 idx 위치에 현재 값을 넣어준다.