[백준] 9251번: LCS [파이썬]

https://www.acmicpc.net/problem/9251

문제

입력 및 출력

문제 풀이 review

입력으로 받은 두 문자열 전체에서 가장 길이가 긴 문자열을 바로 찾아내는 방법은 너무 까다롭다.

따라서 문제를 먼저 작은 문제로 나누어 접근해야 한다.

작은 문제로 나누는 방법은 문자열의 길이를 작게 만들면 된다.

길이가 짧은 문자열의 부분 수열은 그 문자열을 포함하는 긴 문자열의 부분 수열을 포함하고 있기 때문에 앞 단계의 연산이 뒷 단계의 연산에 사용된다.

따라서 이 문제는 다이나믹 프로그래밍 알고리즘을 사용해야한다.

다이나믹 프로그래밍 알고리즘 중에서도 bottom-up 방식의 다이나믹 프로그래밍으로 문제를 해결하기 위해서는 앞 단계의 연산을 저장해 놓을 배열과 앞 단계의 연산을 뒷 단계에 적용시킬 방법인 점화식이 필요하다.

1. 마지막 문자열이 같을 때

LCS는 다음과 같이 나타낼 수 있다.
LCS(str1,str2) = LCS(str1 [ :-1 ], str2[ :-1 ]) + 1

2. 마지막 문자열이 다를 때

LCS는 다음과 같이 나타낼 수 있다.
LCS(str1, str2) = max( LCS(str1[ :-1 ], str2), LCS(str1, str2[ :-1 ]) )

점화식

파이썬 코드