[알고리즘] - 최장 증가 수열 (LIS, Longest Increasing Subsequence)

1. DP로 푸는 방법

 

만약 list에 [8,9,2,1,4,6,7,10] 이 있다면, 여기서 최장 증가 수열은 [1,4,6,7,10] 이다.

처음부터 끝까지 순차적으로 기준을 잡은 뒤 앞의 숫자와 비교한다.

 

만약 기준이 앞의 숫자보다 크다면 앞의 숫자의 최장 증가 + 1(기준)와 현재까지 구한 기준 숫자의 최장 증가 길이 중 더 큰 값을 선택한다.

 

코드로 보면 다음과 같다.

def lis(li):
    if not li:
        return 0

    # dp[i] : i번째 인덱스에서 끝나는 최장 증가 수열의 길이
    dp = [1] * len(li) 

    for i in range(len(li)): # 기준이 되는 숫자
        for j in range(i): # 기준보다 앞쪽에 있는 숫자들
            if li[i] > li[j]: # 기준 숫자가 앞쪽 숫자보다 크다면 (증가하는 경우)
                # 현재 길이와, 앞쪽 숫자 뒤에 붙였을 때의 길이 중 더 긴 것을 선택
                dp[i] = max(dp[i], dp[j] + 1) 
    
    # dp 배열 중 가장 큰 값이 전체 수열의 LIS 길이가 됨
    return max(dp)

# 예시 실행
my_list = [8, 9, 2, 1, 4, 6, 7, 10]
print(f"최장 증가 수열의 길이: {lis(my_list)}")

 

시간복잡도는 O(N^2)이다.

 

 

2. 이분 탐색으로 푸는 방법

 

앞서 살펴본 DP 방식은 구현이 직관적이지만, N이 커질 경우 O(N^2)의 시간 복잡도를 가지므로 시간 초과가 발생할 수 있다.

이를 해결하기 위해 이분 탐색을 활용하면 O(Nlog N)으로 시간을 단축할 수 있다.

 

이 방식의 핵심은 "증가 수열을 만들되, 최대한 작은 숫자로 채워넣어 뒤에 더 많은 숫자가 올 수 있는 가능성을 열어두는 것"이다.

 

1) 현재 숫자 > 새로운 배열의 마지막 숫자 : 새로운 배열에 추가하기

2) 현재 숫자 < 새로운 배열의 마지막 숫자 : 새로운 배열 내부에서 현재 숫자가 들어갈 자리를 찾아 그 값을 교체함. (만약 10 20 인데 현재 숫자가 1이라면, 1 20 으로 교체된다.)

 

코드는 다음과 같다.

from bisect import bisect_left

def lis_binary_search(li):
    if not li:
        return 0

    # LIS의 길이를 계산하기 위한 임시 배열
    c = [li[0]]

    for item in li[1:]:
        # 1. 현재 숫자가 배열의 마지막 숫자보다 클 경우: 뒤에 붙인다.
        if item > c[-1]:
            c.append(item)
        # 2. 작거나 같을 경우: 들어갈 자리를 찾아 교체한다.
        else:
            # bisect_left: item이 들어갈 가장 왼쪽 인덱스를 반환
            idx = bisect_left(c, item)
            c[idx] = item

    return len(c)

# 예시 실행
my_list = [8, 9, 2, 1, 4, 6, 7, 10]
print(f"최장 증가 수열의 길이: {lis_binary_search(my_list)}")