LIS(최장 증가 부분 수열) (1차원 DP부터 이분탐색)

LIS (Longest Increasing Subsequence) 란?

• 어떤 수열에서 순서를 바꾸지 않고, 값이 점점 증가하는 부분 수열 중
  가장 긴 것의 길이를 구하는 문제입니다.

예시:

수열: [10, 20, 10, 30, 20, 50]  
→ LIS: [10, 20, 30, 50] → 길이 = 4

 

여기서 말하는 “부분 수열”은
연속된 값이 아니어도 되고, 원래 순서를 유지하기만 하면 됩니다.

 

 

 

---

 

이 문제, 왜 중요한가요?

 

• LIS는 1차원 DP의 대표 문제입니다.
• 또한, 이분 탐색을 접목한 시간 최적화 기법까지 등장하는 알고리즘 진화 사례이기도 합니다.
• 실무에서도 아래와 같은 패턴으로 자주 등장합니다:

실전 분야	활용 사례
주식 분석	오름차순으로 수익을 최대화하는 거래 흐름 탐색
게임 점수/레벨 분석	상승하는 상태 유지 구간 추적
문자열 비교	사전순 증가 수열 찾기 (ex: 알파벳 정렬)
연속 데이터 분석	최소 편집으로 증가 패턴 만들기

---

 

 

브루트포스 방식은 어떤가요? (O(2ⁿ))

가장 단순하게 생각하면, 가능한 모든 부분 수열을 만들고,

그중에서 오름차순이며 가장 긴 것을 찾을 수 있습니다.

 

하지만 이 경우 시간복잡도는 O(2ⁿ) - 사실상 사용이 불가능합니다.

 따라서 우리는 DP(동적 프로그래밍)을 사용해야 합니다.

 

---

 

DP로 푸는 방식 – O(n²)

• dp[ i ] : 수열의 i번째까지 고려했을 때 i를 끝으로 하는 LIS의 최대 길이

arr = [10, 20, 10, 30, 20, 50]
dp  = [1,  2,  1,  3,  2,  4]

 

점확식

dp[i] = max(dp[j] + 1)  
(단, j < i 이고 arr[j] < arr[i])

 

즉, 이전에 본 원소들 중, 나보다 작았던 것들 중에서 

가장 길었던 부분 수열의 길이에 +1 해주는 방식

 

---

 

Python 구현 (O(n²))

def lis_dp(arr):
    n = len(arr)
    dp = [1] * n  # 초기: 모두 자기 자신 하나로 LIS 가능

    for i in range(n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

 

 

기본 예제

arr = [10, 20, 10, 30, 20, 50]
→ LIS 길이 = 4 ([10, 20, 30, 50])

arr = [3, 5, 7, 2, 8, 6, 10]
→ LIS 길이 = 5 ([3, 5, 7, 8, 10] or [2, 6, 8, 10] 등)

---

이분 탐색 적용 (O(n log n))

실제 LIS를 구하는 게 아니라, 길이만 구한다

LIS를 만들 수 있게 가장 작은 수로 리스트를 유지

arr = [10, 20, 10, 30, 20, 50]

temp = []
→ temp = [10]
→ 20 > 10 → append → [10, 20]
→ 10 → lower_bound = 0 → replace → [10, 20]
→ 30 > 20 → append → [10, 20, 30]
→ 20 → lower_bound = 1 → replace → [10, 20, 30]
→ 50 → append → [10, 20, 30, 50]

이 리스트는 실제 LIS는 아니지만 길이는 같음

 

Python 구현 (O(n log n))

import bisect

def lis_binary(arr):
    result = []
    for num in arr:
        idx = bisect.bisect_left(result, num)
        if idx == len(result):
            result.append(num)
        else:
            result[idx] = num
    return len(result)

 

---

 

이분 탐색 방식과 DP 방식 비교

항목	DP 방식	이분 탐색 방식
구현 난이도	쉽다	약간 복잡
시간복잡도	O(n²)	O(n log n)
실제 LIS 출력	가능 (역추적 필요)	따로 구현해야 함
실전 추천	n ≤ 1,000	n ≤ 1,000,000

 

---

 

LIS 전체 수열 복원 (DP 방식 + 역추적)

def get_lis(arr):
    n = len(arr)
    dp = [1] * n
    prev = [-1] * n

    for i in range(n):
        for j in range(i):
            if arr[j] < arr[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                prev[i] = j

    # LIS 길이와 끝 인덱스
    length = max(dp)
    idx = dp.index(length)

    # 역추적
    lis = []
    while idx != -1:
        lis.append(arr[idx])
        idx = prev[idx]

    return list(reversed(lis))

 

---

요약

• LIS는 1차원 수열에서의 가장 긴 증가 패턴을 찾는 문제
• DP 방식 (O(n²))은 개념 이해와 수열 복원에 유리
• 이분 탐색 방식(O(n log n))은 속도 최적화에 강력
• 실전에서는 문제의 크기와 목적(LIS 길이만? 전체 수열도?) 에 따라 방법 선