최장 증가 부분 수열(LIS)

목록에서 왼쪽부터 오른쪽으로, 앞의 숫자보다 큰 숫자를 골라 나가 보세요. 이런 사슬은 얼마나 길어질 수 있을까요? 퍼즐 책에 실릴 만큼 간단한 질문이지만, 그 답은 카드 게임, 고전적인 동적 계획법 표, 그리고 무작위 섞기에 관한 가장 아름다운 결과 중 하나를 이어 줍니다.

높이가 서로 다른 막대가 한 줄로 놓여 있고, 왼쪽에서 오른쪽으로 높아지는 막대들의 사슬이 주황색으로 표시되어 있다
높이가 서로 다른 막대가 한 줄로 놓여 있고, 왼쪽에서 오른쪽으로 높아지는 막대들의 사슬이 주황색으로 표시되어 있다

문제

숫자 목록이 주어질 때, 부분 수열은 그중 일부를 원래 순서대로 남긴 것입니다. 각 값이 앞의 값보다 크면 증가 부분 수열입니다. 최장 증가 부분 수열(LIS)은 이렇게 고른 것 중 가장 긴 것입니다. 값이 n개인 목록에는 부분 수열이 2ⁿ개 있으므로, 모두 확인하는 방법은 아주 짧은 목록에서만 통합니다.

표

len[i]를 정확히 위치 i에서 끝나는 최장 증가 부분 수열의 길이라고 합시다. 이 값은 그 값 하나만일 때의 1과, 값이 더 작은 앞 위치 j에 대한 1 + len[j] 중 가장 큰 값입니다. 각 위치가 앞의 모든 위치를 돌아보므로 표를 채우려면 n·(n − 1)/2번 비교해야 합니다. 답은 가장 큰 len[i]이며, 각 len[i]를 어느 j가 만들었는지 적어 두면 부분 수열을 거꾸로 읽어 낼 수 있습니다.

예제

3, 10, 2, 1, 20, 4, 6, 7, 5, 9를 생각해 봅시다. 위치별 길이는 1, 2, 1, 1, 3, 2, 3, 4, 3과 5입니다. 20은 3, 10을 늘리고, 4는 3을 늘리며, 6은 4를, 7은 6을, 9는 7을 늘립니다. 9부터 거꾸로 읽으면 3, 4, 6, 7, 9가 나오는데, 이것이 길이 5인 증가 부분 수열입니다.

더 빠른 방법: 페이션스 정렬

값을 카드처럼 여러 더미에 나눠 놓습니다. 각 값은 맨 위 카드가 자기보다 작지 않은 더미 중 가장 왼쪽 더미에 놓거나, 그런 더미가 없으면 오른쪽에 새 더미를 만듭니다. 더미의 개수가 LIS의 길이입니다. 더미들의 맨 위 카드는 항상 정렬되어 있으므로 알맞은 더미를 이진 탐색으로 찾을 수 있고, 전체 방법은 O(n log n) 단계가 걸립니다. 이름은 이와 비슷한 혼자 하는 카드 게임(페이션스, 솔리테어)에서 따왔습니다.

약간의 수학

1935년 폴 에르되시와 조지 세케레시는 서로 다른 수 n² + 1개로 이루어진 어떤 목록에도 길이 n + 1인 증가 또는 감소 부분 수열이 있음을 증명했습니다. 1961년 스타니스와프 울람은 n개의 수를 무작위로 섞었을 때 LIS의 길이가 얼마인지 물었습니다. n이 클 때 2√n에 가깝다는 답은 1977년 아나톨리 베르시크와 세르게이 케로프, 그리고 벤 로건과 래리 셰프가 밝혀냈습니다. 1999년에는 백진호, 퍼시 데이프트, 쿠르트 요한손이 그 요동의 정확한 모양을 찾아냈습니다. 바로 무작위 행렬 이론에 나오는 트레이시–위덤 분포입니다.

1992년 부다페스트의 학생 세미나에서의 에르되시 팔. 1935년 그와 세케레시 죄르지는 서로 다른 수 n² + 1개로 된 목록에는 길이 n + 1의 증가 또는 감소 부분 수열이 있음을 증명했다.
1992년 부다페스트의 학생 세미나에서의 에르되시 팔. 1935년 그와 세케레시 죄르지는 서로 다른 수 n² + 1개로 된 목록에는 길이 n + 1의 증가 또는 감소 부분 수열이 있음을 증명했다.
스타니스와프 울람의 초상
스타니스와프 울람의 초상

직접 살펴보기

앱을 열고 단계를 누르세요. 주황색 열은 지금 계산 중인 위치이고, 파란색 열은 그와 비교하는 앞 위치입니다. 더 긴 수열을 찾을수록 길이 행이 커지고, 앞 위치 행은 그 수열이 어디서 왔는지 기억합니다. 마지막에는 답이 주황색으로 거꾸로 읽혀 표 아래에 표시됩니다.

자주 묻는 질문

LIS의 시간 복잡도는 얼마인가요?

표를 쓰면 모든 위치가 앞의 모든 위치를 살피므로 O(n²)이고, 페이션스 정렬과 이진 탐색을 쓰면 O(n log n)입니다. 둘 다 O(n) 메모리가 필요합니다.

가장 긴 비감소 부분 수열은 어떻게 구하나요?

값이 같은 값 뒤에 올 수 있게 하면 됩니다. 즉 < 대신 ≤로 비교합니다. 앱에서는 같은 값 허용을 체크하세요. 페이션스 정렬에서는 각 값을 맨 위 카드가 자기보다 엄격히 큰 더미 중 가장 왼쪽 더미에 놓습니다.

최장 감소 부분 수열이란 무엇인가요?

비교 방향을 뒤집은 같은 문제이거나, 모든 값의 부호를 바꾼 목록의 LIS입니다. 에르되시–세케레시 정리에 따르면 충분히 긴 목록에는 항상 긴 증가 부분 수열이나 긴 감소 부분 수열이 있습니다.

무작위 목록의 LIS는 얼마나 긴가요?

서로 다른 수 n개를 무작위로 섞으면, n이 클 때 2√n에 가깝습니다. 보정값은 n의 6제곱근처럼 커지므로, 수가 천 개일 때 평균은 약 58로 2√1000 ≈ 63보다 조금 작습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

최장 증가 부분 수열 해 보기