LIS 알고리즘: 최장 증가 부분 수열 최적화 기법 정리

데이터의 흐름 속에서 특정한 경향성을 찾아내는 작업은 매우 매력적입니다. 수열이 주어졌을 때, 원소들의 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분 수열을 찾는 최장 증가 부분 수열(Longest Increasing Subsequence, LIS) 문제는 알고리즘 테스트의 단골 손님입니다. 특히 데이터의 크기에 따라 $O(N^2)$의 직관적인 풀이부터 $O(N \log N)$의 고성능 풀이까지 다양한 접근 방식이 존재합니다. 본 포스팅에서는 LIS의 원리와 이분 탐색을 활용한 압도적인 최적화 과정을 상세히 기술하겠습니다.

1. LIS의 정의와 동적 계획법을 이용한 기본 접근

LIS란 어떤 수열이 주어졌을 때, 그 수열의 부분 수열 중 원소가 오름차순으로 유지되면서 길이가 가장 긴 것을 말합니다. 예를 들어 `[10, 20, 10, 30, 20, 50]`이라는 수열에서 LIS는 `[10, 20, 30, 50]`이며 길이는 4가 됩니다. 가장 기초적인 접근법은 DP를 사용하여 dp[i]를 "i번째 원소를 마지막으로 포함하는 LIS의 길이"라고 정의하는 것입니다. i 이전의 모든 원소 j를 탐색하며 arr[j] < arr[i]인 경우 dp[i] = max(dp[i], dp[j] + 1)을 수행합니다.

1-1. $O(N^2)$ 방식의 한계

이 방식은 2중 루프를 돌기 때문에 $O(N^2)$의 시간 복잡도를 가집니다. 데이터가 수천 개 수준이라면 문제가 없지만, $N$이 10만 개 이상으로 넘어가면 연산 횟수가 100억 번에 달해 실행 시간 초과(TLE)를 피할 수 없습니다. 따라서 우리는 더 효율적인 탐색 기법이 필요하며, 여기서 이분 탐색(Binary Search)의 결합이 등장합니다.

2. $O(N \log N)$ 최적화: 이분 탐색과 Lower Bound

고성능 LIS 알고리즘의 핵심 아이디어는 "최대한 작은 숫자로 끝나는 증가 수열을 유지해야 나중에 더 긴 수열을 만들 가능성이 높다"는 그리디한 관점에 있습니다. 우리는 LIS라는 별도의 배열을 관리합니다. 이 배열은 실제 LIS의 구성을 저장하는 것이 아니라, '길이가 k인 증가 수열 중 마지막 원소의 최솟값'을 저장하는 용도입니다.

2-1. 동작 프로세스와 교체 매커니즘

수열의 원소를 하나씩 확인합니다.
현재 원소가 LIS 배열의 마지막 값보다 크다면, 수열이 연장되는 것이므로 뒤에 추가합니다.
만약 작거나 같다면, LIS 배열 내에서 현재 원소가 들어갈 적절한 위치(현재 값보다 크거나 같은 값 중 가장 첫 번째 위치)를 이분 탐색(Lower Bound)으로 찾아 그 위치의 값을 현재 원소로 교체(Replace)합니다.

이 교체 작업은 전체 수열의 길이를 늘리지는 않지만, 수열의 끝부분을 더 작은 값으로 갱신함으로써 나중에 더 많은 숫자가 뒤에 붙을 수 있도록 '잠재력'을 높여주는 역할을 합니다.

3. 최적화된 복잡도 분석 및 실제 LIS 구성 찾기

이 알고리즘은 전체 $N$개의 원소에 대해 각각 $\log N$의 시간이 걸리는 이분 탐색을 수행하므로 전체 복잡도는 $O(N \log N)$이 됩니다. 단, 주의할 점은 위 과정에서 만들어진 LIS 배열이 실제 정답 수열과 일치하지 않을 수 있다는 점입니다. 실제 구성을 출력해야 한다면, 각 원소가 LIS 배열에 들어갈 때의 인덱스를 별도로 저장한 뒤 역추적(Backtracking)하는 과정을 추가로 거쳐야 합니다.

실무 및 문제 해결에서의 가치

LIS는 주식 시장의 상승 랠리 분석, 반도체 설계 시 선로 겹침 방지 최적화, 그리고 두 서열 간의 유사성을 판단하는 알고리즘 등에서 기반 로직으로 사용됩니다. 특히 $O(N \log N)$의 복잡도는 대용량 로그 데이터에서 경향성을 파악할 때 필수적인 성능 지표가 됩니다.


# 이분 탐색을 활용한 O(N log N) LIS 구현 (Python)
import bisect

def get_lis_length(arr):
    if not arr: return 0
    lis = [arr[0]]
    for i in range(1, len(arr)):
        if arr[i] > lis[-1]:
            lis.append(arr[i])
        else:
            # 현재 원소가 들어갈 위치를 이분 탐색으로 찾아 교체
            idx = bisect.bisect_left(lis, arr[i])
            lis[idx] = arr[i]
    return len(lis)

[LIS 알고리즘 핵심 요약]
1. 개념: 순서를 지키며 값이 증가하는 가장 긴 부분 수열을 찾는 문제입니다.
2. 최적화: DP 방식($O(N^2)$)의 한계를 이분 탐색($O(N \log N)$)으로 극복합니다.
3. 핵심 논리: 작은 값으로 끝나는 수열을 유지하여 뒤에 더 많은 원소가 붙을 확률을 높입니다.

kguidebook0001 님의 블로그