Dynamic Programming - 최장 공통 부분 서열 (LCS)

최장 공통 부분 서열 (LCS)

• 두 문자열의 유사도 측정.
• 이때 연속이 아니더라도 허용한다.
• 구하고자 하는 것은 LCS의 길이
• X = (x1, … xm)
• Y = (y1, … yn)

---

일반적인 방법 - O(2^m)

LCS 구하기
X의 모든 부분 서열을 구하여 Y의 부분 서열인지를 비교한다.
X의 부분 서열(집합)의 수는 2^m 이므로
최소 O(2^m)의 시간이 걸린다.

---

DP - O(n²)

DP를 이용하여 LCS(i, j)를 계산한다.
이때 LCS(i, j)는 xi와 yj의 LCS이다.
그리고 최종 답은 LCS(m, n) 이다.

i=0 혹은 j=0 일때 비교할 게 없으므로
⇒ LCS(i, j) = 0

LCS 를 계산하기 위해 집합을 나눠보자
1. 만약 xi = yj 이라면
⇒ LCS(i, j) = LCS(i-1, j-1) + 1 (뒤에 +1 은 xm = yn 을 반영한 길이)
2. 만약 xi ≠ yj 이라면
xi을 제외한 LCS와, yj을 제외한 LCS중 최대값이 LCS이다.
⇒ LCS(i, j) = Max(LCS(i-1, j), LCS(i, j-1))

---

1958번: LCS 3