Algorithm Guidecomplexity: O(n²)
최장 증가 부분 수열 (LIS)
수열에서 순서를 유지한 채 고를 수 있는 가장 긴 증가 부분 수열의 길이를 구합니다. dp[i]는 'i번째 원소로 끝나는 LIS 길이'라는 부분해로 정의되며, 앞쪽 작은 원소들의 부분해를 재사용해 O(2ⁿ) 완전 탐색을 O(n²)로 끌어내립니다.
01 Explore How It Works
Interactive Step-by-StepHOVER OR SCROLL
Longest Increasing Subsequence
10·
22·
9·
33·
21·
50·
41·
60·
최장 증가 부분 수열(LIS)을 구합니다. 각 위치에서 끝나는 가장 긴 증가 수열의 길이를 dp에 채워 전체 최댓값을 찾습니다.
Logic Node1 / 10
Live Python
02 Understand It Simply
For Everyone🔑Analogy
점점 커지는 수만 골라 가장 긴 줄을 만드는 것.
💡In Plain Words
각 위치에서 끝나는 '가장 긴 증가 부분 수열' 길이를 표로 채워갑니다.
앞선 결과를 활용해 효율적으로 구해요.
📍Where It's Used
- –추세 분석
- –버전 호환성 판단
- –수열 문제
03 Python Implementation
A clean, readable reference implementation of the core logic of 최장 증가 부분 수열 (LIS).
core_implementation.py
04 Frequently Asked Questions
FAQWhat is 최장 증가 부분 수열 (LIS)?+
수열에서 순서를 유지한 채 고를 수 있는 가장 긴 증가 부분 수열의 길이를 구합니다. dp[i]는 'i번째 원소로 끝나는 LIS 길이'라는 부분해로 정의되며, 앞쪽 작은 원소들의 부분해를 재사용해 O(2ⁿ) 완전 탐색을 O(n²)로 끌어내립니다.
What is the time complexity of 최장 증가 부분 수열 (LIS)?+
The time complexity of 최장 증가 부분 수열 (LIS) is O(n²). Follow the step-by-step visualization to see exactly why.
Where is 최장 증가 부분 수열 (LIS) used?+
추세 분석, 버전 호환성 판단, 수열 문제.
What's a simple analogy for 최장 증가 부분 수열 (LIS)?+
점점 커지는 수만 골라 가장 긴 줄을 만드는 것.
Guide Progress0%