LCS 알고리즘에 대해 설명해보세요.

---

LCS 알고리즘이란

• LCS에는 두 가지 의미가 있다. 최장 공통 문자열(Longest Common String)과 최장 공통 부분수열(Longest Common Subsequence)이다. 최장 공통 문자열은 연속된 부분 문자열이고, 최장 공통 부분수열은 연속적이지 않은 부분 문자열이다. 예를들어 abcdefg와 aabcefg에서 최장 공통 문자열은 efg이고, 최장 공통 부분수열은 abcefg이다. LCS 알고리즘은 이 문자열들을 찾는 것을 말한다.

---

최장 공통 문자열

• LCS 2차원 배열을 이용하여 비교하고자 하는 두 문자열을 저장한다. 처음 i와 j가 0일 때는 모두 0으로 초기화시키고, 한 글자씩 비교하며 다르다면 0을, 같다면 LCS[i-1][j-1] +1을 저장한다.

---

최장 공통 부분수열

• 마찬가지로 LCS 2차원 배열을 이용하여 문자열을 저장한다. 한 글자씩 비교하면서 다르다면 LCS[i-1][j]와 LCS[i][j-1] 중 큰 값을 가져오고, 같다면 LCS[i-1][j-1] + 1 을 저장한다. 비교하는 문자가 다를 때 최장 공통 문자열과 차이점을 보이는데, 이는 최장 공통 부분수열은 연속일 필요가 없기 때문에 이전의 최대 공통 부분 수열이 유지되어야 하기 때문이다.

• LCS 배열의 마지막 값에서부터 탐색하여 왼쪽과 위쪽의 값이 현재 값보다 작을 때 결과에 저장하며 0을 만날 때 까지 반복하여 결과를 역순으로 뒤집으면 LCS 탐색이 끝나게 된다.

---

결론

LCS가 의미하는 것에는 최장 공통 문자열과 최장 공통 부분수열이 있습니다. 최장 공통 문자열은 연속된 부분 문자열이고, 최장 공통 부분수열은 연속되지 않은 부분 문자열입니다. LCS 알고리즘은 이 문자열을 찾는 알고리즘인데, 찾는 과정에서 이전까지 찾은 최장 공통 부분을 사용하는 점에서 DP라고 할 수 있습니다. 각 문자열의 길이가 M, N이라고 할 때, LCS의 시간 복잡도는 O(MN)이 됩니다.