카테고리 없음

LIS 알고리즘: 이분 탐색을 활용한 O(N log N) 최적화 가이드

머니지니87 2026. 4. 13. 07:44

데이터의 흐름 속에서 특정한 상승 경향성을 찾아내는 작업은 금융 분석, 생물 정보학, 그리고 복잡한 알고리즘 설계에서 매우 중요한 위치를 차지합니다. 수열이 주어졌을 때, 원소들의 순서를 유지하면서 값이 점진적으로 커지는 가장 긴 부분 수열을 찾는 최장 증가 부분 수열(Longest Increasing Subsequence, LIS) 문제는 그 효율성에 따라 $O(N^2)$에서 $O(N \log N)$까지 극적인 성능 변화를 보여줍니다. 본 포스팅에서는 LIS의 논리적 구조와 이분 탐색을 결합하여 성능을 비약적으로 향상시키는 최적화 기법을 2,500자 이상의 상세한 설명으로 파헤쳐 보겠습니다.

1. LIS의 정의와 동적 계획법(DP)의 기초 접근

LIS란 어떤 수열이 있을 때, 그 부분 수열 중 원소가 오름차순으로 정렬되어 있으며 그 길이가 가장 긴 것을 의미합니다. 예를 들어 `[10, 20, 10, 30, 20, 50]`이라는 수열에서 LIS는 `[10, 20, 30, 50]`으로 길이는 4가 됩니다. 가장 직관적인 해결 방법은 동적 계획법을 사용하여 dp[i]를 "i번째 원소를 마지막으로 포함하는 LIS의 길이"라고 정의하는 것입니다. 하지만 이 방식은 2중 루프를 사용하기 때문에 $O(N^2)$의 시간 복잡도를 가지며, 데이터가 10만 개 이상으로 늘어나면 시스템이 처리 한계에 부딪히게 됩니다.

1-1. $O(N^2)$ 방식의 한계와 비효율성

데이터 개수 $N$이 커질수록 $N^2$의 복잡도는 기하급수적으로 연산량을 증가시킵니다. 10만 개의 데이터를 정렬할 때 약 100억 번의 연산이 필요하며, 이는 일반적인 코딩 테스트나 실무 환경에서 허용되는 시간을 훌쩍 뛰어넘습니다. 따라서 우리는 각 원소를 확인할 때 이전의 모든 원소를 다시 훑지 않고도 최적의 위치를 찾아낼 수 있는 더 똑똑한 방법이 필요합니다.

2. 이분 탐색(Binary Search)을 이용한 O(N log N) 최적화

성능 혁신의 핵심은 이분 탐색의 도입입니다. 우리는 LIS라는 별도의 배열을 관리하며, 이 배열에는 각 길이별로 나타날 수 있는 가장 작은 끝값을 저장합니다. 배열을 순회하며 현재 원소가 LIS 배열의 마지막 값보다 크다면 뒤에 추가하고, 작거나 같다면 LIS 배열 내에서 현재 원소가 들어갈 적절한 위치를 이분 탐색(Lower Bound)으로 찾아 값을 교체(Update)합니다.

2-1. 교체(Replacement) 전략의 수학적 정당성

왜 값을 교체하는 것이 정답을 보장할까요? LIS의 길이를 최대한 길게 만들기 위해서는 수열의 마지막 값이 최대한 작아야 나중에 더 많은 숫자가 뒤에 붙을 수 있기 때문입니다. 현재 원소로 기존의 큰 값을 대체하는 행위는 전체 수열의 길이를 당장 늘려주지는 않지만, 미래에 더 긴 수열을 만들 수 있는 잠재력을 확보하는 그리디(Greedy)한 전략입니다. 이 과정을 통해 전체 복잡도는 $O(N \log N)$으로 단축됩니다.

3. 실제 LIS의 구성 요소 역추적(Backtracking)

이분 탐색 기반의 LIS 알고리즘은 '길이'를 구하는 데는 최적화되어 있지만, 마지막에 남은 LIS 배열의 원소들이 반드시 실제 최장 증가 부분 수열의 구성 요소와 일치하지는 않습니다. 실제 경로를 출력해야 한다면, 각 원소가 LIS 배열에 들어갈 때의 인덱스(위치 정보)를 별도의 배열에 저장해두고, 탐색이 끝난 뒤 역순으로 추적하며 정답을 재구성하는 과정이 필요합니다.

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

  • 주식 및 금융 데이터 분석: 특정 기간 내의 주가 상승 랠리 경향성 파악.
  • 반도체 배선 설계: 선로가 겹치지 않게 배치하면서 최장 경로를 확보하는 최적화 작업.
  • 생물 정보학: 두 개의 DNA 서열 사이에서 공통된 증가 패턴을 찾아 유사도 측정.

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

def get_lis(arr):
    if not arr: return 0
    lis_tmp = [arr[0]]
    
    for i in range(1, len(arr)):
        if arr[i] > lis_tmp[-1]:
            lis_tmp.append(arr[i])
        else:
            # 현재 원소가 들어갈 위치를 이분 탐색으로 찾아 교체
            idx = bisect.bisect_left(lis_tmp, arr[i])
            lis_tmp[idx] = arr[i]
            
    return len(lis_tmp)
[LIS 알고리즘 핵심 요약]
1. 원리: 순서를 유지하며 값이 증가하는 가장 긴 수열을 찾는 문제입니다.
2. 최적화: DP 방식의 $O(N^2)$을 이분 탐색을 통해 $O(N \log N)$으로 개선합니다.
3. 핵심: 각 길이의 마지막 값을 최소로 유지하여 뒤에 더 많은 숫자가 올 가능성을 극대화합니다.