LCS(최장 공통 부분 수열 - longest common subsequence) DP

LCS가 처음이라면 아래에서 우선 재귀적 방법과 메모이제이션 방법을 익히고 오자.

designatedroom87.tistory.com/117

LCS(최장 공통 부분 수열 - longest common subsequence) 재귀적 방법 & 중복제거의 메모이제이션

점화식은 아래와 같이 4가지 경우가 있다고 하였다.

1. 두 문자열의 맨 마지막 원소가 같은 원소로 끝나는 경우(LCS에 포함이 되는 경우)

2. 두 문자열의 맨 마지막 원소가 모두 LCS에 포함이 되지 않는 경우

3. 문자열 Y의 맨 마지막 원소가 LCS에 포함이 되는 경우

4. 문자열 X의 맨 마지막 원소가 LCS에 포함이 되는 경우

LCS(Xi,Yj)는 각 Case1~4중에 가장 큰 값이다.

 

우리가 앞에서 만든 점화식이 위이다.

이 점화식을 토대로 Table의 데이터를 채워나가면 된다.

우선 앞에서 본 대로 각 0행과 0열에는 0으로 세팅을 한다. 아래의 그림을 보자.

그리고 나서 위의 점화관계식을 이용해서 Table의 내용을 채워나가자.

아래는 Table의 내용을 채워나가는 함수이다.

프로그램 실행결과

 

소스 파일

main.c

0.01MB

 

아래의 방법으로도 구현할 수 있다.

구현

프로그램 실행결과

소스 파일

main.c

0.00MB