LCS (최장 공통 부분수열) 시각화
두 문자열의 최장 공통 부분수열을 DP 테이블로 찾는 알고리즘
동적 프로그래밍★★☆
속도
1 / 1LCS 길이: -LCS 문자열: -
프리셋
일치계산 완료역추적
각 단계를 클릭하면 해당 시점으로 이동합니다.
실행 버튼을 눌러 시작하세요.
LCS란?
LCS(Longest Common Subsequence)는 두 문자열에서 순서를 유지하면서 공통으로 나타나는 가장 긴 부분수열을 찾는 알고리즘입니다. 부분수열은 연속일 필요가 없습니다. 예: 'ABCDE'와 'ACE'의 LCS는 'ACE'(길이 3)입니다.
사용 방법
- 1프리셋을 선택하거나 직접 두 문자열을 입력합니다 (최대 10자)
- 2실행 버튼을 눌러 DP 테이블 채우기를 시작합니다
- 3일치(초록) vs 불일치(빨강) 셀 색상으로 비교 결과를 확인합니다
- 4화살표 방향으로 역추적 경로를 파악합니다
- 5역추적 완료 후 LCS 문자열이 하단에 표시됩니다
동작 원리
- 1str1[i] == str2[j]이면 dp[i][j] = dp[i-1][j-1] + 1 (대각선 화살표)
- 2str1[i] != str2[j]이면 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (위 또는 왼쪽 화살표)
- 3dp[m][n]이 LCS의 길이이고, 화살표를 역방향으로 따라가며 LCS 문자열을 구성합니다
- 4시간 복잡도 O(m*n), 공간 복잡도 O(m*n)
실무 활용
- •git diff — 파일 변경 사항 비교에 LCS 변형이 사용됩니다
- •DNA/RNA 서열 정렬 — 생물정보학에서 유전자 유사도 분석
- •표절 검사 — 두 문서의 공통 구절 탐지
- •자동 병합 — 소스 코드 3-way merge에 LCS 기반 알고리즘 활용
학습 팁
- •먼저 'ABCDE' / 'ACE' 프리셋으로 간단한 예제를 풀어보세요
- •대각선 화살표가 나오는 셀이 LCS 문자에 해당합니다
- •역추적 경로(노란색)를 따라가면 LCS가 어떻게 구성되는지 이해할 수 있습니다
자주 묻는 질문
Q. 부분수열과 부분문자열의 차이는?
A. 부분수열(subsequence)은 순서만 유지하면 되고 연속일 필요가 없습니다. 부분문자열(substring)은 반드시 연속이어야 합니다. 'ABCDE'에서 'ACE'는 부분수열이지만 부분문자열은 아닙니다.
Q. LCS가 여러 개일 수 있나요?
A. 네, 같은 길이의 LCS가 여러 개 존재할 수 있습니다. 이 시각화에서는 화살표 방향에 따라 하나만 보여주지만, 모든 LCS를 찾으려면 역추적에서 분기를 탐색해야 합니다.