Algorithm Guidecomplexity: O(n²)

최장 증가 부분 수열 (LIS)

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

01최장 증가 부분 수열 (LIS)

알고리즘 작동 원리 탐색

최장 증가 부분 수열을 찾습니다. 각 값에서 끝나는 가장 긴 증가 수열의 길이를 왼쪽부터 한 칸씩 채워 나갑니다.

모든 칸을 1에서 시작합니다. 어떤 값이든 혼자만으로 이미 길이 1짜리 증가 수열이기 때문입니다.

22 앞의 더 작은 값 중 가장 긴 수열은 10에서 끝납니다. 그 뒤에 이어붙이면 길이는 2입니다.

9 앞에는 더 작은 값이 없습니다. 이어붙일 데가 없으니 길이는 1에 머뭅니다.

33 앞의 더 작은 값 중 가장 긴 수열은 22에서 끝납니다. 그 뒤에 이어붙이면 길이는 3입니다.

21 앞의 더 작은 값 중 가장 긴 수열은 10에서 끝납니다. 그 뒤에 이어붙이면 길이는 2입니다.

50 앞의 더 작은 값 중 가장 긴 수열은 33에서 끝납니다. 그 뒤에 이어붙이면 길이는 4입니다.

41 앞의 더 작은 값 중 가장 긴 수열은 33에서 끝납니다. 그 뒤에 이어붙이면 길이는 4입니다.

60 앞의 더 작은 값 중 가장 긴 수열은 50에서 끝납니다. 그 뒤에 이어붙이면 길이는 5입니다.

가장 긴 증가 수열은 10 → 22 → 33 → 50 → 60 — 길이는 5입니다. 채워둔 값 중 가장 큰 것이 답이 됩니다.

10·

22·

9·

33·

21·

50·

41·

60·

Live Python

1def lis(arr):

# n = 8

2 n = len(arr)

3 dp = [1] * n

4 for i in range(1, n):

5 for j in range(i):

6 if arr[j] < arr[i]:

7 dp[i] = max(dp[i], dp[j] + 1)

8 return max(dp)

1 / 10

02 쉽게 이해하기

For Everyone

🔑핵심 동작

각 자리마다 그 자리로 끝나는 가장 긴 증가 부분 수열의 길이를 구해 두고, 앞의 결과에 이어 붙입니다.

💡쉽게 말하면

각 위치에서 끝나는 '가장 긴 증가 부분 수열' 길이를 표로 채워갑니다.

앞선 결과를 활용해 효율적으로 구해요.

📍어디에 쓰나

–추세 분석
–버전 호환성 판단
–수열 문제

03 파이썬 구현 코드

최장 증가 부분 수열 (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)

04 자주 묻는 질문

FAQ

최장 증가 부분 수열 (LIS)란 무엇인가요?+

최장 증가 부분 수열 (LIS)의 시간복잡도는 어떻게 되나요?+

최장 증가 부분 수열 (LIS)의 시간복잡도는 O(n²) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

최장 증가 부분 수열 (LIS)은(는) 어디에 사용하나요?+

추세 분석, 버전 호환성 판단, 수열 문제.

최장 증가 부분 수열 (LIS)를 쉽게 비유하면?+

각 자리마다 그 자리로 끝나는 가장 긴 증가 부분 수열의 길이를 구해 두고, 앞의 결과에 이어 붙입니다.

→ 동적 계획법 전체 보기Related

🧠피보나치 수열 (DP)

O(n)