-
비트 연산을 활용하여 두 문자열의 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 길이로 정의하면, 아래와 같은 점화식이 성립한다는 사실이 잘 알려져 있습니다. $0 \le T[i][j] - T[i][j-1] \le 1$이므로, 새로운 배열 $D[i][j] = T[i][j] - T[i][j-1]$을 정의하면 각 원소는 0 또는 1입니다. 따라서 $D$을 bitset을 통해 관리하도록 하겠습니다. 관찰 예를...
-
Segment Tree를 활용한 2D Range Update/Query
이 포스트는 Nabil Ibtehaz, Mohammad Kaykobad, Mohammad Sohel Rahman의 Multidimensional segment trees can do range queries and updates in logarithmic time 논문에서 핵심 아이디어를 가져와 작성한 것입니다. 독자가 1/2차원 세그먼트 트리와 Lazy propagation에 대한 지식을 알고 있다고 가정하고 글을 작성합니다. 아래에 제시된 코드는 모두 Kotlin으로 작성하였습니다. 목표 이 글의 목표는 2차원 세그먼트 트리를 이용해 크기의 2차원 배열 에 다음과 같은 연산을 시간에 수행하는 것입니다. Update: 모든 와 주어진 값 에 대해 Query: 구하기 실제로는 교환법칙과...