LIS (최장 증가 부분수열) 시각화
수열에서 가장 긴 증가하는 부분수열을 찾는 DP와 이진탐색 기법을 학습하세요
동적 프로그래밍★★☆
속도
1 / 1LIS 길이: -LIS: -방법: DP O(n²)
프리셋
방법
현재 원소비교 대상LIS 원소DP/Tails 배열
각 단계를 클릭하면 해당 시점으로 이동합니다.
실행 버튼을 눌러 시작하세요.
LIS란?
수열에서 순서를 유지하며 값이 증가하는 가장 긴 부분수열입니다. O(n²) DP와 O(n log n) 이진탐색 두 가지 풀이가 있습니다.
사용 방법
- 1수열을 입력하거나 랜덤 생성하세요
- 2DP 방법과 이진탐색 방법을 전환하며 비교하세요
- 3DP 배열 또는 Tails 배열이 갱신되는 과정을 관찰하세요
- 4LIS에 포함된 원소가 하이라이트됩니다
동작 원리
- 1DP: dp[i] = arr[i]로 끝나는 LIS 길이, dp[i] = max(dp[j] + 1) for j < i where arr[j] < arr[i]
- 2이진탐색: tails 배열 유지, 새 원소가 tails 끝보다 크면 추가, 아니면 lower_bound 위치에 교체
- 3이진탐색 방식은 O(n log n)으로 대규모 입력에 적합
- 4역추적으로 실제 LIS를 복원합니다
실무 활용
- •Git의 patience diff 알고리즘에서 LIS 기반 매칭
- •네트워크 패킷 순서 복원
- •유전체학 — 유전자 서열 유사도 분석
- •주식 시세 분석 — 최장 상승 구간
비슷한 알고리즘
- •LCS — 두 수열의 공통 부분수열, LIS는 한 수열 내 증가 부분수열
- •편집 거리 — LCS/LIS와 관련된 문자열 DP 문제
- •Patience Sorting — LIS의 이진탐색 풀이와 동일한 아이디어의 정렬 알고리즘
학습 팁
- •O(n²) DP부터 완전히 이해한 후 이진탐색으로 넘어가세요
- •tails 배열이 항상 정렬 상태를 유지하는 이유를 고민하세요
- •역추적 과정을 직접 구현해보세요
자주 묻는 질문
Q. LIS가 유일한가?
A. 길이는 유일하지만 수열 자체는 여러 개일 수 있습니다.
Q. 감소가 아닌 비감소도 가능?
A. 네, lower_bound 대신 upper_bound를 사용하면 비감소(≤) LIS를 구할 수 있습니다.