최장 증가 부분수열(LIS) 계산기
수열을 넣으면 최장 증가 부분수열의 길이와 실제 수열, DP 표를 함께 보여 줍니다. 이분탐색 방법이 남기는 배열이 왜 답이 아닌지도 나란히 확인할 수 있습니다.
공백이나 쉼표로 구분합니다. 60개까지 봅니다.
최장 증가 부분수열
2 → 3 → 4 → 5
길이 4 · 같은 길이의 답 1가지
굵은 것이 고른 자리입니다
2 6 8 3 4 5 1
| i | 값 | D[i] (여기서 끝나는 길이) | 앞자리 | 그 길이의 가짓수 |
|---|---|---|---|---|
| 0 | 2 | 1 | — | 1 |
| 1 | 6 | 2 | 0 | 1 |
| 2 | 8 | 3 | 1 | 1 |
| 3 | 3 | 2 | 0 | 1 |
| 4 | 4 | 3 | 3 | 1 |
| 5 | 5 | 4 | 4 | 1 |
| 6 | 1 | 1 | — | 1 |
계산 방법
- 1수열을 공백이나 쉼표로 구분해 넣습니다.
- 2같은 값이 이어져도 되는지(증가·비감소)를 고릅니다.
- 3LIS의 길이와 실제로 고른 자리를 확인합니다.
- 4DP 표에서 D[i]와 앞자리를 따라가면 어떻게 되짚는지 볼 수 있습니다.
자주 묻는 질문
D[i]를 «i번째로 끝나는 증가 부분수열의 최대 길이»로 두고, 앞쪽에서 자기보다 작은 값들 중 가장 긴 것에 1을 더합니다. 답은 D의 최댓값이며 마지막 값이 아닙니다. 어디서 왔는지를 함께 적어 두면 실제 수열을 되짚어 낼 수 있습니다.
아닙니다. 그 배열은 «길이 k인 증가 수열의 마지막 값 중 가장 작은 것»만 모아 둔 것이라 길이만 답이고 내용은 대개 부분수열조차 아닙니다. 2 6 8 3 4 5 1을 넣으면 배열이 [1, 3, 4, 5]가 되는데, 1은 원래 수열의 맨 뒤에 있어 이 순서로는 나올 수 없습니다. 실제 수열을 내려면 각 값이 몇 번째 자리에 들어갔는지를 따로 기록해 되짚어야 합니다.
«앞보다 커야» 하는지 «같아도 되는지»에 따라 답이 달라집니다. 2 2 2는 증가로 보면 길이 1, 비감소로 보면 길이 3입니다. 이분탐색 쪽에서는 이 차이가 자기 자리를 찾을 때 같은 값을 왼쪽으로 볼지 오른쪽으로 볼지(lower_bound와 upper_bound)로 나타납니다.
있습니다. 길이는 하나로 정해지지만 그 길이를 갖는 부분수열은 여럿일 수 있습니다. 2 1 3에서는 2→3과 1→3이 모두 길이 2입니다. 이 계산기는 그중 하나를 보여 주고 몇 가지가 있는지 따로 세어 알려 줍니다.
부분수열은 순서만 지키면 떨어져 있어도 되고, 부분배열(연속 구간)은 붙어 있어야 합니다. LIS는 부분수열이므로 2 6 8 3 4 5에서 2·3·4·5처럼 떨어진 자리를 고를 수 있습니다. 붙어 있어야 한다는 조건을 걸면 훨씬 짧아집니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 여러 답이 있을 때는 가장 먼저 완성되는 것 하나를 보여 줍니다. 길이가 같으면 어느 것이나 옳은 답입니다.
- «같은 길이의 답 가짓수»는 DP로 센 정확한 값입니다. 다만 수열이 길고 값이 겹치면 이 수가 아주 커질 수 있습니다.
- 비교 횟수는 규약에 따른 값입니다. O(n²) 쪽은 모든 쌍을 한 번씩 보고, 이분탐색 쪽은 원소마다 자리를 찾는 비교만 셉니다.
- 숫자는 60개까지 봅니다. DP 표를 화면에 모두 그리기 위한 한계이며, 알고리즘 자체는 훨씬 긴 수열도 다룰 수 있습니다.
- 소수와 음수도 그대로 다룹니다. 값의 크기 비교만 하므로 정수일 필요는 없습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.