Algorithm Guidecomplexity: O(n²)
최장 증가 부분 수열 (LIS)
수열에서 순서를 유지한 채 고를 수 있는 가장 긴 증가 부분 수열의 길이를 구합니다. dp[i]는 'i번째 원소로 끝나는 LIS 길이'라는 부분해로 정의되며, 앞쪽 작은 원소들의 부분해를 재사용해 O(2ⁿ) 완전 탐색을 O(n²)로 끌어내립니다.
01 알고리즘 작동 원리 탐색
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 쉽게 이해하기
For Everyone🔑비유
점점 커지는 수만 골라 가장 긴 줄을 만드는 것.
💡쉽게 말하면
각 위치에서 끝나는 '가장 긴 증가 부분 수열' 길이를 표로 채워갑니다.
앞선 결과를 활용해 효율적으로 구해요.
📍어디에 쓰나
- –추세 분석
- –버전 호환성 판단
- –수열 문제
03 파이썬 구현 코드
최장 증가 부분 수열 (LIS)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.
core_implementation.py
04 자주 묻는 질문
FAQ최장 증가 부분 수열 (LIS)란 무엇인가요?+
수열에서 순서를 유지한 채 고를 수 있는 가장 긴 증가 부분 수열의 길이를 구합니다. dp[i]는 'i번째 원소로 끝나는 LIS 길이'라는 부분해로 정의되며, 앞쪽 작은 원소들의 부분해를 재사용해 O(2ⁿ) 완전 탐색을 O(n²)로 끌어내립니다.
최장 증가 부분 수열 (LIS)의 시간복잡도는 어떻게 되나요?+
최장 증가 부분 수열 (LIS)의 시간복잡도는 O(n²) 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.
최장 증가 부분 수열 (LIS)은(는) 어디에 사용하나요?+
추세 분석, 버전 호환성 판단, 수열 문제.
최장 증가 부분 수열 (LIS)를 쉽게 비유하면?+
점점 커지는 수만 골라 가장 긴 줄을 만드는 것.
→ 동적 계획법 전체 보기Related
Guide Progress0%