[알고리즘] 최장 증가 수열(LIS)

Algorithm

[알고리즘] 최장 증가 수열(LIS) - 이분 탐색

비번변경 2025. 6. 9. 18:56

개요

2025.05.26-[알고리즘] 최장 증가 수열(LIS) - DP에서 최장 증가 수열을 동적 계획법으로 찾는 방법을 정리했었다. 다만 동적 계획법의 경우에는 O(n^2)의 시간 복잡도를 가진다. 때문에 배열의 길이가 아주 큰 경우에는 보다 효율적인 방법을 사용할 필요가 있다.

이 글에서는 최장 증가 수열을 O(log n)의 시간 복잡도로 찾을 수 있는 이분 탐색을 사용한 방법을 정리해 본다.

최장 증가 부분 수열

이분 탐색을 활용할 때는 LIS를 기록하는 배열을 하나 생성한 뒤, 주어진 배열을 하나씩 살펴보면서 각 숫자가 증가수열에 들어갈 위치를 찾는 방식이다.

상세한 과정은 다음과 같다.

구현

1. 이분 탐색

숫자가 들어갈 위치를 찾는 이분 탐색 함수는 아래와 같다.

증가수열의 숫자가 들어갈 위치는 현재 값보다 작은 수들 중 최대값에 해당한다. 따라서 중간값보다 현재 값이 크면 구간의 시작(start)를 중간 지점보다 1 큰 값으로 갱신한다. 그리고 중간값보다 현재값이 작으면 구간의 끝(end)를 중간 지점으로 갱신한다.

def binary_search(arr, x):
    start, end = 0, len(arr) - 1
    while start < end:
        mid = (start + end) // 2
        if x > arr[mid]:
            start = mid + 1
        else:
            end = mid
    return end

탐색은 구간의 시작이 끝보다 크거나 같아질 때까지 반복하며, 반환값은 구간의 끝이 된다.

2. 증가 수열 생성

배열을 탐색하며 증가수열을 생성한다.

만약 증가 수열이 비어있거나 현재 값이 증가수열의 최댓값보다 크면 증가 수열의 끝에 값을 추가한다.

현재 값이 증가수열의 최대값보다 작으면 이분 탐색을 이용해 적절한 위치에 값을 경신한다.

def lis(nums):
    result = []

    for n in nums:
        if not result or n > result[-1]: result.append(n)
        else:
            i = binary_search(result, n)
            result[i] = n
    return result

증가 수열이 만들어지는 과정을 출력해 보면 다음과 같다.