최장 공통 부분수열(LCS) 계산기
두 글의 최장 공통 부분수열과 DP 표를 구하고, 붙어 있어야 하는 최장 공통 부분문자열과 나란히 견줍니다. 어디가 지워지고 더해졌는지도 diff처럼 보여 줍니다.
첫 번째 글
두 번째 글
최장 공통 부분수열 (LCS)
BCBA
길이 4글자 · 7글자 대 6글자
지움 · 더함 · 나머지는 그대로
ABDCABDAB
| ε | B | D | C | A | B | A | |
|---|---|---|---|---|---|---|---|
| ε | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| B | 0 | 1 | 1 | 1 | 1 | 2 | 2 |
| C | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
| B | 0 | 1 | 1 | 2 | 2 | 3 | 3 |
| D | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
| A | 0 | 1 | 2 | 2 | 3 | 3 | 4 |
| B | 0 | 1 | 2 | 2 | 3 | 4 | 4 |
사용 방법
- 1비교할 두 글을 각각 넣습니다.
- 2글자·단어·줄 중 무엇을 한 단위로 볼지 고릅니다.
- 3LCS와, 붙어 있어야 하는 최장 공통 부분문자열을 견줍니다.
- 4diff에서 어디가 그대로이고 어디가 지워지고 더해졌는지 확인합니다.
자주 묻는 질문
부분수열은 순서만 지키면 떨어져 있어도 되고, 부분문자열은 붙어 있어야 합니다. "ABCBDAB"와 "BDCABA"의 최장 공통 부분수열은 길이 4지만, 붙어 있어야 한다는 조건을 걸면 길이 2가 최대입니다. 가장 흔한 오해가 이 둘을 섞어 쓰는 것입니다.
두 글자가 같으면 대각선 값 + 1, 다르면 왼쪽과 위 중 큰 값을 가져오는 DP 표를 채우고 오른쪽 아래 칸을 읽습니다. 첫 행과 첫 열은 빈 문자열과의 공통이라 0입니다. 편집 거리 표와 모양은 같지만 최솟값이 아니라 최댓값을 채운다는 점이 반대입니다.
두 글에서 공통으로 남는 가장 긴 부분수열을 찾으면, 거기 못 낀 것들이 곧 지운 것과 더한 것입니다. 그래서 교체를 빼고 넣고 지우기만으로 고치는 횟수가 정확히 m + n − 2×LCS가 됩니다. 다만 표 크기가 두 길이의 곱이라 실제 diff 도구는 Myers 알고리즘 같은 더 빠른 방법을 씁니다.
두 글자가 같으면 대각선 값 + 1, 다르면 0으로 되돌리는 표를 채우고 표 전체에서 가장 큰 값을 찾습니다. «다르면 0»이 «붙어 있어야 한다»를 그대로 옮긴 것이며, 그래서 답이 오른쪽 아래 칸이 아니라 표 어디에나 있을 수 있습니다.
있습니다. 길이는 하나로 정해지지만 그 길이를 가진 부분수열이 여러 개일 수 있고, 표를 되짚을 때 어느 쪽을 먼저 잡느냐에 따라 다른 것이 나옵니다. 이 계산기는 «지움»을 먼저 잡는 규약을 쓰며, 교재의 답과 모양이 달라도 길이가 같으면 둘 다 맞습니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 세는 단위에 따라 답이 달라집니다. «나는 밥을 먹었다»와 «나는 빵을 먹었다»는 단어로 보면 공통이 2개지만 글자로 보면 조사와 공백까지 낱낱이 세어 더 길게 나옵니다.
- 글자 단위는 유니코드 NFC로 정규화한 뒤 코드포인트로 셉니다. 이모지처럼 여러 코드가 모여 한 글자로 보이는 문자는 나뉘어 셉니다.
- 계산량이 두 길이의 곱(O(mn))이라 400단위까지만 봅니다. 표는 한 변이 30단위 이하일 때만 그립니다.
- 유사도 2·LCS ÷ (m+n)는 파이썬 difflib의 ratio와 같은 꼴입니다. 다만 difflib는 LCS가 아니라 «가장 긴 일치 블록»을 재귀로 찾는 방식이라 값이 조금 다를 수 있습니다.
- 줄 단위로 보면 빈 줄은 버리고 셉니다. 실제 diff 도구는 빈 줄도 한 줄로 세므로 결과가 다를 수 있습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.