Oh My Algorithm
Algorithm Guidecomplexity: O(n²)

최장 증가 부분 수열 (LIS)

수열에서 순서를 유지한 채 고를 수 있는 가장 긴 증가 부분 수열의 길이를 구합니다. dp[i]는 'i번째 원소로 끝나는 LIS 길이'라는 부분해로 정의되며, 앞쪽 작은 원소들의 부분해를 재사용해 O(2ⁿ) 완전 탐색을 O(n²)로 끌어내립니다.

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step
TAP OR HOVER
Longest Increasing Subsequence
10·
22·
9·
33·
21·
50·
41·
60·

최장 증가 부분 수열(LIS)을 구합니다. 각 위치에서 끝나는 가장 긴 증가 수열의 길이를 dp에 채워 전체 최댓값을 찾습니다.

Logic Node1 / 10

02 파이썬 구현 코드

최장 증가 부분 수열 (LIS)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py
def lis(arr):
    n = len(arr)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)
Guide Progress0%