알고리즘을 풀 때 단계별로 접근하는 방법을 좋아합니다.
우선 LCS (가장 긴 공통 부분 수열)을 구할 때 가장 먼저 생각할 수 있는 방법은 수열 X, Y에 대해 모든 부분 수열을 구하고 비교하는 것입니다.
시간복잡도는 O(2^(x) 2^(y) l) 입니다.
- x,y = X,Y의 원소의 개수, l = 문자열 비교
그 다음으로 생각해볼 수 있는 건 재귀를 이용한 방법입니다.
만약 수열 X,Y의 끝 원소가 같다면 당연히 가장 긴 공통 부분 수열은 마지막 원소를 포함할 것입니다. 그래서 LCS(X,Y) = LCS(X[:-1], Y[:-1]) + 1가 됩니다.
한편, X,Y의 끝 원소가 다르다면 굳이 끝 원소를 사용할 필요가 없습니다. 따라서
LCS(X,Y) = max(LCS(X[:-1],Y), LCS(X, Y[:-1])) 가 됩니다.
(X = abcf, Y= fabc인 경우를 생각해보면 이해가 쉽습니다.)
이 경우 원소가 모두 다를 경우에 시간복잡도는 O(2^min(x,y) + a)가 됩니다.
*x,y = X,Y의 원소의 개수
(수열 X, Y 중 원소의 크기가 더 적은 애가 하나씩 빠져서 원소의 개수가 0이 될 때까지 2개씩 분해되고, 원소의 길이가 더 긴 수열에 의해 생기는 경우의 수 a 입니다.)
이렇게 되면 수열의 길이가 50만 되더라도 시간이 어마어마하게 걸리게 됩니다.
한번 예시를 들어보겠습니다. X = {A,B,C,D,E} , Y = {Z,X,C,V,L} 라고 해보면 재귀를 풀기 위해 다음과 같은 과정을 겪게 됩니다. (pdf 파일에는 그림이 있습니다!)
- LCS(X,Y) = max( LCS(X[:-1],Y), LCS(X, Y[:-1))
- 1의 왼쪽 LCS에서 LCS(X[:-1],Y) = max( LCS(X[:-2], Y), LCS(X[:-1],Y[:-1))
- 1의 오른쪽 LCS에서 LCS(X,Y[:-1]) = max( LCS(X[:-1],Y[:-1]), LCS(X, Y[:-2))
위에서 볼 수 있듯 LCS( X[:-1], Y[:-1])의 계산이 중복됩니다.
계산의 중복을 지울 순 없을까? -> 동적 계획법의 핵심!
우리가 피보나치를 구할 때도 같은 계산이 중복되는 걸 메모라이제이션 기법을 이용하여 테이블에 값을 저장 후 계산의 중복을 피했습니다.
LCS 문제도 이와 같이 테이블을 만들게 되면 LCS(X,Y)를 X와 Y의 원소의 개수의 곱, 위의 예시에서 5 * 5의 계산만으로 해결할 수 있게 됩니다.
따라서 테이블을 이용하게 되면 LCS의 시간 복잡도는 O(x * y) 가 됩니다.
x,y = X,Y의 원소의 개수
아래에 정리한 PDF를 넣어두었습니다.
https://acoustic-basin-638.notion.site/LCS-9de234b35d314230bcf502de7cfbe829
