채운 칸
비교 횟수
지금까지 최장

  • 채우는 중
  • 읽는 칸
  • 답

최장 증가 부분 수열에 대해 더보기

최장 증가 부분 수열(LIS)

숫자 목록에서 순서를 유지한 채, 각 숫자가 바로 앞 숫자보다 크도록 몇 개까지 고를 수 있을까요? 최장 증가 부분 수열이 그 답입니다. 목록을 입력하고, 동적 계획법이 각 위치마다 그곳에서 끝나는 가장 긴 수열을 구하는 과정을 지켜보세요. 재생을 눌러 표가 채워지는 것을 보거나, 단계와 뒤로로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 숫자 목록을 입력하세요. 표에는 각 위치마다 그 위치에서 끝나는 가장 긴 증가 수열의 길이와, 그 수열이 이어 가는 앞 위치가 기록됩니다. 줄어들지 않는 수열을 찾으려면 같은 값 허용을 체크하세요. 마지막에는 수열을 마지막 값부터 거꾸로 읽어 냅니다. 새 예제는 다른 목록을 만듭니다. 보드를 선택한 상태에서 화살표 키는 단계 이동, 스페이스 바는 재생과 일시 정지, Home과 End는 처음과 끝으로 이동합니다.

작동 원리

  1. 숫자 목록을 쉼표나 공백으로 구분해 입력하세요. 줄어들지 않는 수열을 찾으려면 같은 값 허용을 체크하세요.
  2. 재생을 누르거나, 단계와 뒤로로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다.
  3. 각 위치가 앞의 모든 위치와 비교되는 모습을 본 다음, 가장 긴 수열이 주황색으로 거꾸로 읽히는 것을 확인하세요.

표의 작동 방식

표에는 세 행이 있습니다. 값, 각 위치에서 끝나는 최장 증가 부분 수열의 길이, 그리고 그 수열이 이어 가는 위치입니다. 값 하나만으로도 길이 1인 수열입니다. 그다음 앞의 모든 위치를 확인합니다. 그 위치의 값이 더 작으면 거기서 끝나는 수열을 지금 값으로 늘릴 수 있고, 길이는 그 수열보다 1 늘어납니다. 이런 연장 중 가장 긴 것이 선택되고, 그 위치가 세 번째 행에 들어갑니다.

수열 거꾸로 읽기

최장 증가 부분 수열은 길이가 가장 큰 위치에서 끝납니다. 거기서부터 세 번째 행은 그 앞에 어느 위치가 오는지 알려 주고, 그 위치의 세 번째 행은 다시 그 앞에 어느 위치가 오는지 알려 줍니다. 앞에 오는 위치가 없는 위치에 이를 때까지 계속합니다. 이 값들을 순서대로 읽으면 답이 됩니다. 같은 값 허용을 체크하면 값이 같은 값 뒤에도 올 수 있으므로, 줄어들지 않는 가장 긴 수열을 얻습니다.

자주 묻는 질문

부분 수열과 부분 배열은 어떻게 다른가요?

부분 배열은 이웃한 값들의 한 덩어리입니다. 부분 수열은 순서를 유지하지만 값을 건너뛸 수 있습니다. 그래서 3, 10, 2, 1, 20에서 3, 10과 20은 사이에 2와 1이 있어도 증가 부분 수열을 이룹니다.

LIS 알고리즘은 얼마나 빠른가요?

표 방식은 모든 위치 쌍을 비교합니다. 값이 n개면 n·(n − 1)/2번 비교합니다. 페이션스 정렬은 O(n log n)에 해냅니다. 길이마다 그 길이의 수열을 끝내는 가장 작은 값을 기억하고, 새 값을 이진 탐색으로 제자리에 놓습니다.

최장 증가 부분 수열은 하나뿐인가요?

항상 그렇지는 않습니다. 1, 3, 2, 4에서는 1, 3, 4와 1, 2, 4가 모두 길이 3입니다. 표는 길이를 알려 주고, 거꾸로 읽기는 그중 하나를 찾습니다.

최장 증가 부분 수열은 어디에 쓰이나요?

파일이나 유전체를 비교할 때 쓰입니다. 일부 방법은 먼저 일치하는 줄을 찾은 뒤 그 위치들의 증가 부분 수열을 구합니다. 일정 계획과 상자 쌓기 퍼즐에도 쓰이고, 수학에서는 무작위로 섞은 목록의 LIS 길이가 유명한 연구 대상입니다.

어딘가로 데이터가 전송되나요?

아니요. 모든 계산은 브라우저에서 이루어지며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.

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

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

편집기로 이동