-
동적 계획법을 최적화하는 9가지 방법 (Chapter 3)
동적 계획법을 최적화하는 9가지 방법 (Chapter 3) 이 글은 Chapter 2에서 계속된다. 8. Circular LCS 두 문자열 $S, T$ 가 주어질 때 둘의 LCS를 구하는 문제는 잘 알려져 있고, $n = S, m = T$ 일 때 $O(nm)$ 보다 빨리 하기 힘든 것으로도 유명하다. Circular LCS 문제는 $S$ 를 Cyclic shift 할 수 있을 때, 각 cyclic shift에 대해서 LCS를 계산하는 문제이다. 기호로 표현하면, 모든 $0 \le i \le S - 1$ 에 대해, $LCS(S[i:]...
-
비트 연산을 활용하여 두 문자열의 LCS 빠르게 구하기
이 포스트에서는 두 문자열 $A[1..n]$, $B[1..m]$의 최장 공통 부분 수열(이하 LCS)을 $O(nm/w)$ 시간에 구하는 방법에 대해 서술합니다. Lloyd Allison, Trevor I. Dix의 A bit-string longest-common-subsequence algorithm을 보고 작성한 글입니다. 일반적으로 LCS를 구하는 방법 $T[i][j]$를 $A[1..i]$와 $B[1..j]$의 LCS 길이로 정의하면, 아래와 같은 점화식이 성립한다는 사실이 잘 알려져 있습니다. \[T[i][j] = \begin{cases} 0 & \text{if $i=0$ or $j=0$} \\ T[i-1][j-1]+1 & \text{if $A[i] = B[j]$} \\ \max(T[i-1][j],T[i][j-1])& \text{otherwise} \end{cases}\] $0 \le T[i][j] - T[i][j-1] \le 1$이므로, 새로운...