최장 공통 부분 수열
최장 공통 부분 수열은 두 수열의 순서를 유지하면서 두 수열 모두에 나타나는 가장 긴 부분 수열의 길이 또는 수열을 구한다 동적 계획법·문자열 비교 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를...
| 분류 | 알고리즘 · 동적 계획법·문자열 비교 |
|---|---|
| 핵심 문제 | 두 수열의 순서를 유지하면서 두 수열 모두에 나타나는 가장 긴 부분 수열의 길이 또는 수열을 구한다 |
| 방법 | 끝 문자가 같으면 앞선 부분 문제의 답에 1을 더하고, 다르면 두 접두사 중 하나를 한 칸 줄인 문제의 최대값을 사용한다 |
| 계산 비용 | 두 길이 n,m에서 전형적 O(nm) 시간·O(nm) 공간; 길이만 계산하면 O(min(n,m)) |
| 적용 조건 | 부분 수열은 원소가 연속할 필요가 없으며 문자 또는 원소 비교가 정의되어야 한다 |
| 관련 활용 | 버전 diff·서열 비교에 사용한다 |
| 관련 이론 | 자료구조, 계산 복잡도 |
| 참고 자료 | CP-Algorithms |
최장 공통 부분 수열은 두 수열의 순서를 유지하면서 두 수열 모두에 나타나는 가장 긴 부분 수열의 길이 또는 수열을 구한다 동적 계획법·문자열 비교 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한 명령어 조합과는 구별된다.[1]
계산 절차는 끝 문자가 같으면 앞선 부분 문제의 답에 1을 더하고, 다르면 두 접두사 중 하나를 한 칸 줄인 문제의 최대값을 사용한다. 역추적하면 실제 LCS를 복원할 수 있다. 각 단계의 상태가 무엇을 의미하는지 정의하고 초기값과 경계 입력을 검사하면 결과의 정확성을 증명하거나 테스트할 수 있다.
복잡도는 두 길이 n,m에서 전형적 O(nm) 시간·O(nm) 공간; 길이만 계산하면 O(min(n,m)) 적용 전제는 부분 수열은 원소가 연속할 필요가 없으며 문자 또는 원소 비교가 정의되어야 한다 실제 연산량·메모리 사용은 구현의 자료구조와 정수·실수 표현, 전처리 및 입력 크기에 따라 달라진다.
응용과 관련 기법을 보면 버전 diff·서열 비교에 사용한다. 연속된 부분 문자열을 찾는 문제와는 다르다. 같은 문제라도 최악 시간 보장, 메모리 요구 사항과 정밀도·확률적인 실패 가능성에 따라 적합한 알고리즘이 달라진다.[2]