-
LCS(최장 공통 부분 수열 - longest common subsequence) DPAlgorithm with C/Dynamic Programming 2020. 9. 28. 16:35
LCS가 처음이라면 아래에서 우선 재귀적 방법과 메모이제이션 방법을 익히고 오자.
designatedroom87.tistory.com/117
점화식은 아래와 같이 4가지 경우가 있다고 하였다.
1. 두 문자열의 맨 마지막 원소가 같은 원소로 끝나는 경우(LCS에 포함이 되는 경우)
2. 두 문자열의 맨 마지막 원소가 모두 LCS에 포함이 되지 않는 경우
3. 문자열 Y의 맨 마지막 원소가 LCS에 포함이 되는 경우
4. 문자열 X의 맨 마지막 원소가 LCS에 포함이 되는 경우LCS(Xi,Yj)는 각 Case1~4중에 가장 큰 값이다.
우리가 앞에서 만든 점화식이 위이다.
이 점화식을 토대로 Table의 데이터를 채워나가면 된다.
우선 앞에서 본 대로 각 0행과 0열에는 0으로 세팅을 한다. 아래의 그림을 보자.
그리고 나서 위의 점화관계식을 이용해서 Table의 내용을 채워나가자.
아래는 Table의 내용을 채워나가는 함수이다.
프로그램 실행결과
소스 파일
아래의 방법으로도 구현할 수 있다.
구현
프로그램 실행결과
소스 파일