[알고리즘] LCS(The longest common subsequence)-dynamic programming

(2021.10.10)

알고리즘 수업들으면서 정리하기 11탄

6주차 내용- LCS

 

optimal substructure 을 찾는 것에 중점을 두자

recurrence를 쓸 수 있어야 함

 

---

LCS(The longest common subsequence)

 

 

Definition[subsequence]

 

 

 

 

Definition[common subsequence]

 

만약 Z가 X의 subsequece 이면서, Y의 subsequence이면, Z는 X와 Y의 common subsequence라고 한다.

Z는 consecutive(연속적) 일 필요는 없으나 in order (순서대로) 여야한다.

 

 

 

Definition[Prefix of a subsequence]

 

X=<x1,x2,..,xm> 이라는 sequence에 대해

prefix of X (for i=0,1,..,m) 은 Xi=<x1,x2,..,xi> 를 의미한다. (처음부터 i번째 원소까지

 

 

Longest common subsequence

 

Find a subsequence common to both whose length is longest.

A subsequence doesn't have to be consecutive, but it has to be in order.

 

 

 

---

 

 

 

Naive approach for longest common subsequence

 

 

 

 

Dynamic programming for longest common subsequence

 

Dynamic programming은 4-step method 를 이용한다.

 

1. Charcterize the structure of an optimal solution: show that the problem has the optimal substructure
2. Recursively define the value of an optimal solution: Make recurrence of the optimal solution
3. Compute the value of an optimal solution, typically in a botton-up fashion
4. Construct an optimal solution from computed information

 

 

1. Characterize the structure of an optimal solution

 

 

 

2. Recursively define the value of an optimal solution

 

LCS(X,Y,m,n)
  if m==0 or n==0
    return 0
  else if X[m]==Y[n]
    return LCS(X,Y,m-1,n-1) + 1
  else 
    retrun max(LCS(X,Y,m-1,n),LCS(X,Y,m,n-1))

 

 

 

3. Compute the value of an optimal solution (typically in a bottum-up fashion)

 

아래의 테이블 채우기

출처: 교수님 강의노트

계산 과정 예시

 

 

 

4. Construct an optimal solution from computed information

 

채운 테이블 해석하여 LCS 값 도출해내기

 

 

 

 

 

LCS length코드

 

 

 

Print-LCS 코드

 

 

 

 

LCS의 time complexity

- b와 c table을 계산하는데에는 세타(mn)

- LCS print하는데에는 세타(m+n)