LIS (Longest Increasing Subsequence)

LIS 최장 증가 부분 수열 알고리즘

LIS(Longest Increasing Subsequence, 최장 증가 부분 수열) 문제란 주어진 수열에서 오름차순으로 증가하는 부분 수열 중 가장 긴 길이를 찾는 문제를 의미함.

• 부분 수열(Subsequence): 원래 수열에서 일부 원소를 선택하여 만든 수열이며, 반드시 연속적일 필요는 없음.
• 증가하는 수열: 앞 원소보다 항상 큰 원소가 뒤에 오는 수열을 의미함.
• 최장(Longest): 가능한 증가 부분 수열 중 길이가 가장 긴 것을 의미함.

수열: [10, 20, 10, 30, 20, 50]

가능한 증가 부분 수열:
- [10, 20, 30, 50] → 길이 4
- [10, 20, 50] → 길이 3
- [10, 30, 50] → 길이 3

따라서 최장 증가 부분 수열의 길이는 4가 됨

LIS가 중요한 이유

LIS는 단순한 길이 계산 문제를 넘어서, DP(Dynamic Programming)와 이분 탐색 알고리즘을 동시에 학습할 수 있는 대표적인 문제임.

• 주식 데이터에서 상승 구간의 최대 길이 계산

• 데이터 최적화 및 패턴 분석

• 알고리즘 학습의 기본기 습득

풀이 방법

1. DP 풀이 (O(N^2))

def LIS(arr):
    n = len(arr)
    dp = [1] * n  # 최소 길이는 항상 1

    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]
print(LIS(arr))  # 출력: 4

2. 이분 탐색 풀이 (O(NlogN))

import bisect

def LIS(arr):
    lis = []
    for num in arr:
        pos = bisect.bisect_left(lis, num)
        if pos == len(lis):
            lis.append(num)
        else:
            lis[pos] = num
    return len(lis)

# 예제 실행
arr = [10, 20, 10, 30, 20, 50]
print(LIS(arr))  # 출력: 4

방식	시간 복잡도	장점	단점
DP	O(N²)	구현이 간단하고 직관적임	큰 입력에서는 시간 초과 발생 가능
이분 탐색	O(N log N)	큰 입력도 처리 가능	실제 LIS 수열을 구하는 것은 복잡함