빅데이터 1인 1프로젝트 PART 2
PART 2에서는 LCS 문제와 그 변형 문제를 정의하고, 이를 해결하기 위한 다양한 방법을 알아보겠다.
Longest Common Subsequence 문제 정의
정의: 부분 수열(subsequence)은 문자열 $S$에서 0개 이상의 문자를 제거하여 얻을 수 있는 문자열이다.
정의: 부분 문자열(substring)은 문자열 $S$의 연속한 일부를 택해 얻을 수 있는 문자열이다.
정의: 두 문자열 $S, T$의 LCS는 $S$의 부분 수열이면서 동시에 $T$의 부분 수열인 문자열 중 길이가 가장 긴 문자열이다.
정의: LCS 문제는 두 입력 문자열 $S, T$의 LCS의 길이를 계산하는 문제이다.
LCS의 변형 문제
Circular LCS
정의: 문자열 $S$에서 $\lvert S \rvert$는 $S$의 길이이다.
정의: 문자열 $S$에서 $S[i]$는 $S$의 $i$번째 문자이다. 여기서 인덱스는 $0$-based indexing을 따른다.
정의: 문자열 $S$에서 $S[i:j]$는 $S[i], S[i+1], S[i+2], \dots, S[j-1]$를 순서대로 이은 문자열이다. $i = 0$이거나 $j = \lvert S \rvert$인 경우에는 각각 $i$ 또는 $j$를 생략할 수 있다.
정의: 두 문자열 $S, T$에 대해 $S + T$는 $S$와 $T$를 순서대로 이어 붙인 문자열이다.
정의: Circular LCS는 두 문자열 $S, T$에 대해 모든 $0 \le i < \lvert S \rvert$에 대하여 $S[i:] + S[:i]$와 $T$의 LCS 길이를 구하는 문제이다.
ALCS (All-substrings Longest Common Subsequence)
정의: ALCS는 두 문자열 $S, T$에 대해 $S$와 $T$의 모든 부분 문자열 쌍의 LCS 길이를 구하는 문제이다.
Semi-local LCS
정의: 문자열 $S$의 접두사는 어떤 $0 \le i \le \lvert S \rvert$에 대해 $S[:i]$인 문자열이다.
정의: 문자열 $S$의 접미사는 어떤 $0 \le i \le \lvert S \rvert$에 대해 $S[i:]$인 문자열이다.
정의: Semi-local LCS는 두 문자열 $S, T$에 대해 다음을 모두 구하는 문제이다.
- $S$와 $T$의 ALCS
- $T$와 $S$의 ALCS
- $S$의 모든 접두사와 $T$의 모든 접미사의 LCS 길이
- $S$의 모든 접미사와 $T$의 모든 접두사의 LCS 길이
LCS에 접근하는 방법
LCS를 해결하는 대표적인 방법은 아래와 같다.
고전적 LCS 문제를 해결하는 방법
- Dynamic Programming을 사용한 $O(nm)$ 시간의 풀이
- Bitset을 이용해 DP 풀이의 시간을 $O\left(\frac{nm}{w}\right)$로 최적화하는 풀이
- Hirschberg’s Algorithm을 사용해 공간 복잡도를 $O(n + m)$으로 최적화하는 풀이
LCS 변형 문제를 해결하는 방법
Circular LCS
- Bitset을 이용한 최적화
- Quadratic Ad-hoc
- 분할 정복을 이용한 최적화
ALCS
- 변화량을 관찰해 망원합을 이용하는 방법: 시간 복잡도는 $O(nm)$이다.
- Unit Monge Matrix를 이용한 방법: 시간 복잡도는 $O(n \log^2 n + q \log n)$이다.
참고한 글
- https://koosaga.com/243
- https://koosaga.com/245
- https://koosaga.com/315
- https://koosaga.com/316
- https://qwerasdfzxcl.tistory.com/m/28
- https://arxiv.org/abs/0707.3619