최장 증가 부분 수열 (LIS, Longest Increasing Subsequence)

구현 코드 예시

def lis_dp(arr):
    """O(n^2) — dp[i]는 i번째 원소로 끝나는 LIS의 길이."""
    if not arr:
        return 0
    n = len(arr)
    dp = [1] * n

    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)          # dp[n-1]이 아니다


import bisect

def lis_fast(arr):
    """O(n log n) — tails[k]는 길이 k+1 수열의 가능한 최소 끝값."""
    tails = []
    for x in arr:
        i = bisect.bisect_left(tails, x)    # x 이상이 처음 나오는 자리
        if i == len(tails):
            tails.append(x)                 # 전부 x보다 작다 → 길이 +1
        else:
            tails[i] = x                    # 그 자리를 더 작은 x로 교체
    return len(tails)

bisect_left와 bisect_right의 선택이 문제 조건을 가른다. 같은 값을 허용하지 않는 증가 수열이면 bisect_left, 같은 값을 허용하는 비감소 수열이면 bisect_right다. 함수 이름 하나 차이로 답이 달라지니 문제에서 "증가"인지 "감소하지 않는"인지 꼭 확인한다.

실제 수열을 복원하려면 각 자리를 차지한 원소의 인덱스와 그 직전 원소를 함께 기록한다.

def lis_restore(arr):
    """LIS 수열 자체를 복원한다."""
    if not arr:
        return []

    tails, tail_idx = [], []          # tail_idx[k] = tails[k]를 만든 원소의 인덱스
    prev = [-1] * len(arr)            # prev[i] = LIS에서 i 앞에 오는 원소의 인덱스

    for i, x in enumerate(arr):
        p = bisect.bisect_left(tails, x)
        if p == len(tails):
            tails.append(x)
            tail_idx.append(i)
        else:
            tails[p] = x
            tail_idx[p] = i
        prev[i] = tail_idx[p - 1] if p > 0 else -1

    result, cur = [], tail_idx[-1]    # 마지막 자리를 차지한 원소부터 거슬러 올라간다
    while cur != -1:
        result.append(arr[cur])
        cur = prev[cur]
    return result[::-1]

자주 하는 실수

• dp[n-1]을 답으로 반환한다. LIS가 마지막 원소로 끝난다는 보장이 없다. 반드시 max(dp)다.
• tails를 실제 LIS로 착각한다. 길이만 맞는다. 수열이 필요하면 별도 복원 로직이 필요하다.
• bisect_left와 bisect_right를 잘못 고른다. 중복 값이 있는 입력에서 답이 1씩 어긋난다. "증가"와 "비감소"를 구분한다.
• 부분 수열과 부분 배열을 혼동한다. LIS는 연속일 필요가 없다. 연속을 요구하는 문제는 훨씬 쉬운 다른 문제다.
• 빈 배열을 처리하지 않는다. max(dp)가 빈 리스트에서 예외를 던진다.
• n을 보지 않고 O(n²)를 쓴다. n이 10만이면 100억 번 연산이라 무조건 시간 초과다. 제약 조건을 먼저 읽는다.

면접에서 이렇게 물어본다

• LIS의 O(n²) 점화식을 세우고 상태의 의미를 설명해 보라.
• 왜 dp[i]를 "i로 끝나는 LIS 길이"로 정의하는가.
• O(n log n) 방법에서 tails 배열의 각 원소가 의미하는 바는 무엇인가.
• tails가 실제 LIS와 다를 수 있는 이유를 설명해 보라.
• 이분 탐색이 적용 가능한 이유, 즉 tails가 항상 정렬 상태인 이유는 무엇인가.
• 같은 값을 허용하는 경우 구현이 어떻게 달라지는가.
• 실제 LIS 수열을 복원하려면 무엇을 추가로 기록해야 하는가.