최장증가부분수열(LIS) - 파이썬 (DP,이분탐색)

이분 탐색 문제를 풀어보다가 최장증가수열 알고리즘으로 풀수있는 알고리즘이 있어 이론을 정리를 하려고 합니다. 

최장증가부분수열(LIS,Longest increasing subsequence) 이란 

주어진 원소 n개인 배열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 알고리즘입니다. 즉 각 원소가 이전 원소보다 크다는 조건을 만족하고 그 길이가 최대안 부분수열을 최장 증가부분수열입니다. 

 

예를 들어 아래와 같은 수열이 있다고 가정을 해봅시다 

[3, 5, 7, 9, 2, 1, 4, 8]

 

여기서 증가하는 부분수열을 만든다면 했을때 졍렬이 아닌 요소를 제외하는 방법으로 한다면 아래와 같이 여러가지가 나올수 있습니다.

[3,5,6,7]

[1,4,8]

[2,4,8]

... 등이 있지만 제일 긴 수열은 3,5,6,8 이 됩니다. 

이러한 LIS 알고리즘을 구하는 방식을 여러가지가 있지만 여기서는 DP 와 이분탐색을 이용하여 풀어보겠습니다.

1. DP 이용하기 : O(n^2)

---

dp(동적계획법) 을 이용하여 dp 테이블을 생성하고 리스트 요소에 번호를  저장하는 방식으로 푸는 방식입니다

i  : 각 요소의 인덱스 번호 

A : 리스트 안에 숫자

D : A[i]를 마지막으로 가지는 가장 긴 증가부분수열의 길이 

아래 그림으로 표현을 해봤습니다.(알고리즘의 규칙을 위해 0을 추가해두었습니다 즉 1번 인덱스 부터 시작입니다.)

i = 1 일때는 A[1] = 3 입니다 따라서 A[0] = 0 뒤에 붙을수 있습니다

i = 2 일때는 A[2] = 5 입니다 따라서 A[1] = 3 뒤에 붙을수 있습니다

이렇게 문제를 풀어가다보면 i = 5 일때 D의 값을 변화를 주어야합니다.

즉 A[5] = 2 이므로 A[0] = 0 뒤에 붙을수가 있습니다. 그래서 D[5] = D[0] +1 = 1 입니다

그렇다면 i = 7 일때는 어떻게 될까요 ? 

i = 7 일때는 A[7] = 4이므로 A[0] = 0,A[1] = 3,A[5]=2,A[6]=1 뒤에 붙을수가 있습니다. 따라서 D[x] =1  D[x]+1 = 2 의 값을 가지= 수 가 있습니다

그렇다면 i = 8 일때도 동일하게 적용이 됩니다.

i = 8 일때는 A[7] = 4이므로 A[0] = 0,A[1] = 3,A[5]=2,A[6]=1 ... A[7]=4  뒤에 붙을수가 있습니다. 따라서 뒤에 붙을수 있는 수중 가장 큰수인 A[3] =7,D[3] = 3 인 값에 D[3]+1 = 4의 값을 얻을수 있습니다. 

 

 

이렇게 해서 배열 D 값들중 가장 큰값 (D[4] = D[8]) = 4가 수열 [3, 5, 7, 9, 2, 1, 4, 8] 의 LIS 의 길이가 됩니다

 

코드로 구현을 한다면 아래와 같습니다 

 

# A 값 선언
A = [3, 5, 7, 9, 2, 1, 4, 8]
# DP 테이블 초기화
D = [1] * (A+1)
for i in range(1, len(A)):
    for j in range(0, i):
    	# 오름차순으로 전값 비교 
        if A[j] < A[i]:
            D[i] = max(D[i], D[j]+1)

print(len(A)-max(D))

 

2. 이분탐색 이용하기 : O(nlogn)

---

이분 탐색을 이용하는건 다음과 같은 의문에서 시작이 됩니다. 

"D[i]를 계산하기 위해 A[0]~A[i-1]를 전부 다 구해야할까? "

 

첫 번째 알고리즘에서 A[0] ~ A[i - 1]를 훑어본 것은 A[i]보다 작은 A[j]를 가지는 j들 중 가장 큰D[j]를 찾기 위함이었다. 여기서 다음과 같은 생각을 이끌어낼 수 있다.

 

"만약 D[j] = k를 만족하는 j 중 A[j]의 값이 가장 작은 j만 어딘가에 저장해 놓으면, 나중에 D[i] (i > j)를 계산할 때 그 값들만 참조하면 D[i]의 값을 쉽게 알 수 있다"

 

어딘가에 저장을 해놓은다는 의미는 무엇일까? 즉 D에 동일한 번호로 값이 할당이 되어야한다면 그 자리에 있던 값을 대체하다는것을 의미합니다. 

 

예를 들면 i = 5 일때 D = 1의 값을 A[5] = 2 로 대체하여 저장을 하는 방법입니다. 

 

 

코드로 구현한다면 다음과 같습니다. 

 

# A 선언
A = [3, 5, 7, 9, 2, 1, 4, 8]
# D 값 초기화
D = []
# D 초기값 넣기 
D.append(A[0])
# 이진 탐색 
def binary_search(start, end, target):
    while start <= end:
        mid = (start+end) // 2
        if D[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return start


for i in range(1, len(A)):
	# 마지막 요소를 비교 
    if D[-1] < A[i]:
    	# A[i] 가 크다면 D 요소에 마지막 으로 추가
        D.append(A[i])
    else:
    	# A[i] 가 작다면 이진 탐색
        idx = binary_search(0, len(D), A[i])
        # 이진 탐색으로 얻은 번호로 D에 저장
        D[idx] = A[i]

print(D)

 

이 방식을 Lower_Bound 라고 합니다.