채운 칸
일치한 쌍
지금까지 최장

  • 채우는 중
  • 읽는 칸
  • 답

최장 공통 부분 수열 더 알아보기

최장 공통 부분 수열(LCS)

두 단어에 같은 순서로 공통으로 들어 있는 글자는 무엇일까요? 최장 공통 부분 수열이 그 답이며, diff 도구, 맞춤법 검사기, DNA 비교가 모두 이를 바탕으로 합니다. 두 단어를 입력하고 그 글자들로 이루어진 표가 채워지는 과정을 본 다음, 모서리에서부터 답을 거꾸로 따라가 보세요. 재생을 눌러 표가 채워지는 과정을 보거나, 단계와 뒤로로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 두 단어를 입력하세요. 첫 번째 단어는 표의 왼쪽을 따라 세로로, 두 번째 단어는 위쪽을 따라 가로로 놓입니다. 각 칸에는 그 행과 열까지의 글자들의 최장 공통 부분 수열 길이가 들어갑니다. 마지막에는 오른쪽 아래 칸에서부터 거꾸로 글자를 읽어 냅니다. 새 예제는 다른 단어 쌍을 고릅니다. 보드를 선택한 상태에서 화살표 키는 단계 이동, 스페이스 바는 재생과 일시 정지, Home과 End는 처음과 끝으로 이동합니다.

작동 원리

  1. 두 단어를 입력하세요. 첫 번째 단어는 표의 왼쪽을 따라 세로로, 두 번째 단어는 위쪽을 따라 가로로 놓입니다.
  2. 재생을 누르거나, 단계와 뒤로로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다.
  3. 각 칸이 두 글자를 비교하는 과정을 본 다음, 주황색 경로를 모서리에서부터 거꾸로 따라가며 답을 읽으세요.

표의 원리

각 칸에는 첫 번째 단어의 그 행까지의 글자와 두 번째 단어의 그 열까지의 글자의 최장 공통 부분 수열 길이가 들어갑니다. –로 표시된 행과 열은 빈 단어를 나타내므로 0입니다. 칸의 두 글자가 같으면 그 칸은 왼쪽 위 칸보다 1 큽니다. 다르면 두 글자 중 하나는 답에 들어가지 않으므로, 칸은 위 칸과 왼쪽 칸 중 큰 값을 가져옵니다.

글자를 거꾸로 읽기

오른쪽 아래 칸이 답의 길이입니다. 글자를 찾으려면 거기서 시작하세요. 두 글자가 일치하는 곳에서는 그 글자가 부분 수열에 들어가고 왼쪽 위로 이동합니다. 그렇지 않으면 위 칸과 왼쪽 칸 중 큰 쪽으로 이동합니다. 가는 길에 모은 글자를 거꾸로 읽으면 최장 공통 부분 수열 하나가 됩니다. 같은 길이의 다른 것이 있을 수도 있으며, 거꾸로 읽기는 그중 하나를 찾습니다.

자주 묻는 질문

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

부분 문자열은 RACER 안의 ACE처럼 서로 붙어 있는 글자들입니다. 부분 수열은 순서는 유지하지만 글자를 건너뛸 수 있으므로, ACE는 ABCDE의 부분 수열이기도 합니다. 최장 공통 부분 문자열은 비슷한 표를 쓰는 다른 문제입니다.

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

길이가 m과 n인 단어라면 표에 m·n개의 칸이 있고 각 칸을 한 단계에 채우므로, 작업량은 O(m·n)입니다. 10,000줄짜리 텍스트 두 개라면 1억 개의 칸이 되므로, diff 도구는 같은 아이디어를 바탕으로 한 더 영리한 방법을 씁니다.

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

아닙니다. ABCBDAB와 BDCABA에는 길이가 4인 서로 다른 공통 부분 수열이 세 개 있습니다. BCBA, BCAB, BDAB입니다. 표는 길이를 알려 주고, 거꾸로 읽기는 그중 하나를 고릅니다.

LCS로 두 단어가 얼마나 비슷한지 알 수 있나요?

어느 정도는 그렇습니다. 길이가 m과 n이고 최장 공통 부분 수열의 길이가 k인 두 단어는, m − k개의 글자를 지우고 n − k개를 넣으면 서로 바꿀 수 있습니다. 글자 바꾸기도 허용하는 편집 거리가 더 나은 척도인 경우가 많습니다.

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

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

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

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

편집기로 이동