최장 공통 부분 수열(LCS)

최장 공통 부분 수열은 Longest Common Subsequence의 약자로 줄여서 LCS라고 한다.

우선 Subsequence와 Substring의 차이에 대해 알아야 한다.

 

Substring이랑 부분 문자열로 공통 Substring을 구해야 한다면 공통된 연속하는 문자열을 구할 수 있어야한다.

Subsequence는 부분 수열로 공통 Subsequence는 문자를 건너 뛰더라도 공통뒤는 문자 수열을 말한다. 

 

최장 공통 부분 수열(Longest Common Subsequence)

---

LCS를 구하는 방법은 다이나믹 프로그래밍 방식을 사용한다. 

두 문자열이 있을 때 각 문자열의 인덱스를 하나 씩 방문하여 같은지 비교하여 값을 저장한다. 

그림으로 이해하면 이해하기 쉬움

위 그림을 예시로 "ABCAB"라는 문자열과 "AABACA"라는 두 문자열을 비교하여 LCS를 구하는 과정입니다.

해당 이차원 배열을 DP배열, 두 문자열을 s1, s2라고 할때 

아래와 같이 점화식을 세울 수 있습니다. 

DP[i][j] = s1[0]~s1[i]까지의 문자열과 s2[0] 부터 s2[j] 까지의 문자열을 비교할 때 두 문자열의 LCS
s1[i] == s2[j] 일때
 DP[i][j] =DP[i-1][j-1] + 1
else
 DP[i][j] = max(DP[i-1][j], DP[i][j-1])

즉, 이전의 문자를 하나씩 비교하면서 비교한 결과값(LCS 값)을 저장해두고 이전의 저장한 값을 사용해서 전체 두 문자열을 비교했을 때 LCS를 구할 수 있습니다.

 

위 점화식을 말로 풀어서 설명한다면

비교하는 두 문자가 같을 때
예 ) 문자열 "ABC" 와 "AABAC"는 비교하는 두 문자가 'C'로 같으므로 "AABA"와 "AB"를 비교한 LCS 값에 +1을 해줍니다.

비교하는 두 문자가 다를 때
예) 문자열 "AABA" 와 "AB"는 비교하는 두 문자가 'B'로 서로 다름. 이런 경우 "AABA"와 "AB"의 LCS 값은
"AABA" 와 "A"의 LCS 값과 "AAB"와 "AB"의 LCS값 중 더 큰 값을 갖습니다.

 

 

LCS 문제

https://hoime.tistory.com/58

[DP] 백준 9251 LCS C++