LIS - 최장 증가 부분 수열

LIS

 

Longest Increasing Subsequence의 약자

 

최장 증가 부분 수열

 

길이가 N인 배열의 원소들을 골라 만든 부분 수열 중, 부분 수열의 원소들이 모두 오름차순으로 정렬되어 있고 가장 길이가 긴 수열이 '최장 증가 부분 수열'

 

예로, [ 6, 9, 1, 4, 10, 2, 3, 7]의 최장 증가 부분 수열은 [1, 2, 3, 7]

 

최장 증가 부분 수열의 길이 구하는 방법

1. dp

2. 이분 탐색

 

1. dp

 

가장 단순한 방법이지만

 

O(N^2) 시간복잡도를 가져 배열의 길이가 긴 경우에는 비효율적인 방법

 

numbers = [ 6, 9, 1, 4, 10, 2, 3, 7]


def LIS(arr):
    N = len(arr)
    dp = [1 for _ in range(N)]
    for i in range(N):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)


print(LIS(numbers))

 

알고리즘

 

1. 배열과 동일한 길이의 배열 선언하고 모든 원소 1로 초기화

2. 최장 증가 수열의 원소 k 앞의 모든 원소들은 k 보다 작을것이므로 해당 원소 앞 순서의 길이 중 가장 긴 것을 골라 1을 더한것을 기록

3. 2번 과정을 모든 원소에 대하여 실행

 

'dp[i] = i번째 인덱스에서 끝나면 최장 증가 수열의 길이' 임을 알면 이해하기 수월하다.

 

2. 이분 탐색 

 

시간복잡도가 O(N * logN)으로 dp보다 효율적이다.

 

배열을 순차적으로 탐색하며 최장 증가 부분 수열을 직접 만드는 방식

 

 

def bsearch_lis(arr):
    lis = [0]

    for a in arr:
        if lis[-1] < a:
            lis.append(a)
        else:
            left = 0
            right = len(lis)
            while left < right:
                mid = (left + right) // 2
                if lis[mid] < a:
                    left = mid + 1
                else:
                    right = mid
            lis[right] = a

    return len(lis) - 1

 

알고리즘

 

1. 최장 증가 수열을 기록할 배열 lis 생성. 구현 편의를 위해 0 저장

2. 원본 배열을 순차 탐색

3. 참조중인 원소의 값이 배열 lis의 마지막 원소값보다 크면 lis 맨끝에 이어붙임 (append)

4. 그렇지 않은 경우, 배열 lis에 참조중인 원소를 저장할 위치를 이분탐색을 통해 탐색하고 탐색한 위치에 참조중인 원소값 저장

5. 원본 배열의 모든 원소에 대하여 3,4 과정 수행