최장 공통 부분 수열(LCS) cf. 최장 공통 문자열

🟩 LCS, 최장 공통 부분 수열 Longest Common Subsequence (cf. Longest  Common Substring 최장 공통 문자열)

 

최장 공통 부분 수열의 경우, 부분수열이기 때문에 문자 사이를 건너뛰어 공통되면서 가장 긴 부분 문자열을 찾으면 된다.

최장 공통 문자열의 경우, 부분 문자열이 아니기 때문에, 한 번에 이어져 있는 문자열만 가능하다.

 

🟩 최장 공통 문자열

if i == 0 or j == 0:  # 마진 설정
	LCS[i][j] = 0
elif string_A[i] == string_B[j]:
	LCS[i][j] = LCS[i - 1][j - 1] + 1
else:
	LCS[i][j] = 0

 

LCS라는 2차원 배열을 이용하여 두 문자열을 행, 열에 매칭한다. 편의상 i, j가 0일 때는 모두 0을 넣어줘 마진값을 설정한다. 이후 i, j가 1이상일 때부터 검사를 시작한다.

 

1. 문자열 A, B의 한글자씩 비교한다.

2. 두 문자가 다르다면 LCS[i][j]에 0을 표시한다.

3. 두 문자가 같다면 LCS[i-1][j-1] 값을 찾아 +1 한다.

4. 위 과정을 반복한다.

 

공통 문자열은 연속되어야 하기 때문에 위 과정이 성립된다. 현재 두 문자가 같을 때 두 문자의 앞 글자까지가 공통 문자열이라면 계속 공통 문자열이 이어질 것이고, 아니라면 본인부터 다시 공통 문자열을 만들어 가게 될 것이다. 

 

🟩 구현과정

 

🟩 최장 공통 부분 수열

if i == 0 or j == 0:  # 마진 설정
	LCS[i][j] = 0
elif string_A[i] == string_B[j]:
	LCS[i][j] = LCS[i - 1][j - 1] + 1
else:
	LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])

 

1. 문자열 A, B의 한글자씩 비교한다.

2. 두 문자가 다르다면 LCS[i - 1][j]와 LCS[i][j - 1] 중에 큰 값을 표시한다.

3. 두 문자가 같다면 LCS[i - 1][j -1] 값을 찾아 +1 한다.

4. 위 과정 반복한다.

 

최장 공통 문자열과 다른 부분은 비교하는 두 문자가 다를 때이다. 비교하는 두 문자가  같을 때는 같은 과정을 보여준다.

부분 수열은 연속된 값이 아니다. 때문에 현재의 문자를 비교하는 과정 이전의 최대 공통 부분수열은 계속해서 유지한다. '현재의 문자를 비교하는 과정' 이전의 과정이 바로 LCS[i-1][j]와 LCS[i][j-1]이 된다.

 

🌟 LCS[i-1][j]와 LCS[i][j-1] 의 의미

 

문자열 AB와 GBC를 비교하는 과정을 예로 든다면, AB와 GBC의 최대 공통 부분수열이 B라는 것을 알기 위해서는 문자열 A와 GBC를 비교하는 과정, 문자열 AB와 GB를 비교하는 과정이 필요하다. 문자열 AB와 GB의 비교 과정에서 최대 공통 부분수열이 B임을 확인했기 때문에 문자열 AB와 GBC의 최대 공통 부분수열 역시 B가 된다.

 

🌟 왜 문자가 같으면 LCS[i][j] = LCS[i-1][j-1] +1인가?

부분 수열은 연속될 필요가 없다. 두 문자가 같은 상황이 오면 지금까지의 최대 공통 부분수열에 1을 더해주는 것

문자열 ABC와 GBC를 비교하는 과정을 예로 들자면, LCS 배열은 LCS[i-1][j]와 LCS[i][j-1]의 비교를 통해 언제나 본인까지의 최대 공통 부분수열 값을 가지고 있다. 문자열 AB와 GB를 비교할 때와 문자열 ABC와 GBC를 비교할 때 달라진 점은 두 문자열 모두에 C가 추가된 점이다. 때문에  기존의 최대 공통 부분수열인 B에 C를 더한 BC가 최대 공통 부분수열이 된다.

 

🟩 구현과정

 

🟩 시간복잡도

길이 n과 m인 두 스트링의 LCS 길이 👉 O(nm)

각각 길이 n과 m을 사용하는 중첩된 이중 루프

 

테이블 LCS[][]로부터 LCS를 구하는 알고리즘 👉 O(n+m)

idx가 LCS 길이만큼 줄어들 때까지 반복하는 형태의 루프로 구성

실제로는 i=n, j=m부터 최대 i=0, j=0까지 도달 가능

 

🌟 최장 공통 부분 수열 찾기

여러가지 방법 중 하나

1. LCS 배열의 가장 마지막 값에서 시작한다. 결과값을 저장할 result 배열을 준비한다.

2. LCS[i-1][j]와 LCS[i][j-1] 중 현재 값과 같은 값을 찾는다.

👉 2-1. 만약 같은 값이 있다면, 해당 값으로 이동

👉 2-2. 만약 같은 값이 없다면, result 배열에 해당 문자를 넣고, LCS[i-1][j-1]로 이동한다.

3. 2번 과정을 반복하다가 0으로 이동하게 되면 종료한다. result 배열의 역순이 LCS이다.

 

---

자료 출처

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence