LIS ( Longest Increasing Subsequence ) 알고리즘

이 게시물은 게시자의 이해를 위하여 작성됨.

" LIS ( Longest Increasing Subsequence ) 최장 증가 부분수열 알고리즘 "

최장 증가 부분수열 알고리즘은 N개의 배열의 일부 원소를 골라내서 만든 부분 수열의 각 원소가 이전 원소보다 크다는 조건을 만족하는 가장 긴 부분 수열을 의미.

 

[ DP를 이용하는 방법 ]

data = [10, 0, 20, 30]
for i in range(n):
    DP[i] = 1
    for j in range(i):
    	if data[j] < data[i]:
            DP[i] = max(DP[i], DP[j] + 1)

1. i = 0일 때, DP[0] = 1 /  j는 반복하지 않음. 

1

2. i = 1일 때, DP[1] = 1 / for j in range(1)이기에 반복 -> data[0] < data[1] 이 성립하지 않기에 넘어감.

1

1

3. i = 2일 때, DP[2] = 1 / for j in range(2)이기에 반복 -> data[0] < data[2] 가 성립

1

1

2

3 - 2. i = 2일 때, data[1] < data[2] 가 성립 max(2, 2) 이기에 그대로 2

1

1

2

4. i = 3일 때, DP[3] = 1 / for j in range(3)이기에 반복 -> data[0] < data[3] 가 성립

1

1

2

2

4 - 2. i = 3일 때, data[1] < data[3] 가 성립 max(2, 2) 이기에 그대로 2

1

1

2

2

4 - 3. i = 3일 때, data[2] < data[3] 가 성립 max(2, 3) 이기에 3으로 갱신

1

1

2

3

 

이 방법의 경우, 시간 복잡도가 O(n^2)임. -> 비효율적.

 

[ 이분탐색을 이용하는 방법 ]

이분탐색 (Binary Search) :  정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법.

=> 증가하는 부분수열을 찾을 것이기 때문에 정렬이 되어있다 생각해도 무방.

 

< 동작과정 >

1. 먼저 초기 data[0]의 값을 lis 배열의 맨 처음에 삽입.

data

10

0

20

30

lis

10

 

2. 다음 data[1]이 lis 배열의 어디에 들어갈 수 있는지 확인.

lis

0

0이 10보다 작기 때문에 맨앞에 삽입.

 

3. 다음 data[2]가 lis 배열의 어디에 들어갈 수 있는지 확인.

lis

0

20

20이 0보다 크기 때문에 뒤에 삽입.

 

4. 다음 data[3]이 lis 배열의 어디에 들어갈 수 있는지 확인.

lis

0

20

30

30이 20보다 크기 때문에 뒤에 삽입.

 

def binarySearch(left, right, goal):
    while left < right:
    	mid = (left+right)//2
        if lis[mid] < goal:
            left = mid + 1
        else:
            right = mid
    return right
 
if __name__ == "__main__":
    data = [10, 0, 20, 30]
    lis = [-1] * len(data)
    
    lis[0] = data[0]
    new = 0
    for i in range(1, len(data)):
    	if lis[new] < data[i]:
            new += 1
            lis[new] = data[i]
        else:
            lis[binarySearch(0, new, data[i])] = data[i]

 

위는 LIS의 단순 길이를 구하는 방법이다.

 

[ LIS의 원소를 구하는 방법 ]

원소를 구하기 위해서는 그 원소의 기록을 저장을 해둬야한다.

하지만 저장되는 것 처럼 binarySearch에 의해서 원래 위치에 값이 들어가는 것이 아니라 이후에 등장하는 작은 값이 덮어씌워진다. 그래서 각 숫자가 들어가는 인덱스를 기억해둔다.

 

< 동작 과정 >

1. 숫자가 lis 배열에 들어갈 때 몇번째 인덱스에 삽입되었는지를 저장.

2. 모든 숫자를 다보고 위치를 저장했다면 저장된 인덱스의 최대값부터 역순으로 돌아오면서 확인.

3.  그 최대값을 저장하고 -1한 값을 저장하고 0이 될때까지 반복하여 저장.

4. 그 저장된 값을 reverse 시키면 lis 원소.

 

def binarySearch(left, right, goal):
    while left < right:
        mid = (left+right)//2
        if lis[mid] < goal:
            left = mid + 1
        else:
            right = mid
    return right
 
if __name__ == "__main__":
    data = [10, 0, 20, 30]
    lis = [-1] * len(data)
    
    lis[0] = data[0]
    index = [0]
    new = 0
    for i in range(1, len(data)):
    	if lis[new] < data[i]:
            new += 1
            lis[new] = data[i]
            index.append(new)
        else:
            pos = binarySearch(0, new, data[i])
            lis[pos] = data[i]
            index.append(pos)
    result = []
    for i in range(len(data)-1, -1, -1)
    	if index[i] == new:
            result.append(data[i])
            new -= 1
    result.sort()
    print(result)