[알고리즘] Longest Common Subsequence - Length
안녕하세요. 오늘은 학교 수업 중 알고리즘 강의를 굉장히 재밌게 들었고 내용을 보다 확실히 이해하기 위해 기록을 통해 다시 한번 생각해보려 글을 작성하게 되었습니다.
오늘 배운 알고리즘 다이나믹 프로그래밍 (DP) 중 유명한 알고리즘 문제중 하나인 Longest Common Subsequence, 줄여서 LCS 문제를 분석해보는 시간이였습니다. 그 중에서도 문자열의 LCS에 대해 공부를 해보았습니다. LCS란 두 문자열에서 서로 공통되는 가장 긴 부분 문자열을 말합니다. LCS 문제는 이 부분 문자열을 구하는 문제가 되는 것입니다.
그럼 바로 시작해보도록 하겠습니다.
LCS
먼저 단순히 뜻만으로는 와닿지 않을 수 있으니 몇 가지 예를 들어 설명해보도록 하겠습니다.
- LCS of "ABCDGH", "AEDFHR" = "ADH"
- LCS of" AGGTAB", "GXTXAYB" = "GTAB"
- LCS of "MZJAWXU", "XMJYAUZ" = "MJAU"
이제 어느정도 감이 잡히시나요? 저는 오늘 LCS 자체를 구하는 것보다 LCS의 길이를 구하는것에 집중해보도록 하겠습니다. 왜냐하면 길이가 구해진 과정을 통해 문자열을 유추해낼 수 있기 때문입니다. 그럼 본격적으로 길이를 구하는 점화식을 구해보도록 하겠습니다.
DP를 사용하여 문제를 풀기 위해서는 먼저 두 가지가 선행되어야 합니다.
- 부분 문제 선정
- 점화식 유도
이에 따라 먼저 부분 문제부터 선정해보도록 하겠습니다.
예를 들어 길이가 각각 m과 n인 X와 Y의 문자열의 LCS의 길이를 구한다고 가정하였을 때 X, Y 문자열은 각각 다음과 같이 표현될 수 있습니다.
- X = X[0] X[1] X[2] … X[i - 2] X[i - 1] (0 <= i <= m)
- Y = Y[0] Y[1] Y[2] … Y[j - 2] Y[j - 2] (0 <= j <= n)
그리고 L(i, j)는 위와 같은 배열에서 i와 j의 값에 따른 LCS의 길이를 나타냅니다.
예를 들어 X 문자열이 "ABCDGH"이고 Y 문자열이 "AEDFHR"라면 L(3,2)는 "ABC"와 "AE"의 LCS의 길이를 나타내는 값으로 "A"의 길이 즉 1이 됩니다.
이렇게 우리는 i와 j의 값을 각각 0부터 진행하며 현재의 i, j 값에 따른 LCS의 길이를 구해가는 것을 통해 부분 문제를 풀어갈 수 있습니다. 그리고 문자열의 마지막 문자에 집중하며 문제를 풀어나가면 됩니다.
여기서 제가 깨달은 것은 DP의 문제중 어떤 것의 길이나 나열된 값을 요구하는 문제는 항상 마지막 요소에 집중하여 문제를 생각해보면 해결 방법이 보인다였습니다. 마지막 요소를 추가하냐 마냐에 따라 점화식을 세우는 등의 방법으로 문제를 접근하면 해답에 조금 더 가까워지는 것을 많이 느꼈습니다.
위에서 언급한 것처럼 마지막 요소에 집중하여 점화식을 세워보도록 하겠습니다. 먼저 마지막 요소를 고려할 때는 두 가지의 경우가 존재합니다.
첫 번째는 바로 각각의 문자열에서 마지막 요소가 서로 같을 때 입니다. 현재 비교하고 있는 인덱스가 각각 서로의 마지막 인덱스가 되므로 현재의 인덱스의 값을 현재 비교중인 부분 문자열의 마지막 요소라 생각하면 됩니다. 그리고 이렇게 각 부분 문자열의 마지막 인덱스가 같다면 이전 인덱스에서 구한 길이에 1을 증가시켜주면 됩니다.
말로 풀어 설명하니까 이해가 잘 안되시죠? 점화식과 예시를 통해 설명해보도록 하겠습니다. 위의 예제에서와 같이 X를 "ABCDGH", Y를 "AEDFHR"이라 가정해보도록 하겠습니다. 그리고 부분 문제를 풀기 위해 나누어 비교 중인 각각의 문자열의 부분 문자열의 길이가 6과 5라면 현재 비교 중인 문자열은 "ABCDGH"와 "AEDFH"가 됩니다. 그리고 각각의 마지막 요소는 H가 되고 서로 같으므로 이전 LCS인 "AB"의 길이에 1과 "H"를 추가하여 LCS의 길이가 3인 "ADH"가 되는 것입니다.
이를 점화식으로 표현한다면 L(i, j) = L(i-1, j-1) + 1입니다.
두 번째는 현재 비교중인 각각 부분 문자열의 마지막 요소가 서로 다를 때 입니다. 이 경우도 두 가지의 경우로 나누어지게 됩니다. 그 경우로는 X 부분 문자열의 마지막 요소가 Y 부분의 문자열의 마지막 요소가 아닌 앞의 요소와 짝이 맺어지는 경우이거나 Y 부분 문자열의 마지막 요소가 X 부분 문자열의 마지막 요소가 아닌 앞의 요소와 짝이 맺어지는 경우입니다. 그리고 이 둘 중 최대 값이 현재 비교 중인 각각의 부분 문자열의 마지막 요소가 서로 다를 때의 LCS 길이가 됩니다.
이를 점화식으로 표현한다면 max(L(i, j - 1), L(i - 1, j))
그러므로 이를 종합한 최종 점화식은 다음과 같습니다.
- if i == 0 or j == 0 ~ L(i, j) = 0
- if X[i - 1] == Y[j - 1]) ~ L(i, j) = L(i - 1, j - 1) + 1
- else ~ L(i, j) = max(L(i, j - 1), L(i - 1, j))
i == 0 or j == 0은 하나의 문자열이라도 길이가 0이라면 공통된 부분의 문자열의 길이는 0이라는 것을 의미합니다. 위의 점화식을 구현한 코드는 다음과 같습니다.
