[swjungle 2기] LCS

LCS 알고리즘

Longest Common Subsequence, Substring

• LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다.
• 문자열 ABCDEF와 GBCDFE를 이용하여 차이점을 예시로 들어보면

Longest Common Subsequence

A(BCD)E(F)
G(BCDF)E
---
BCDF

Longest Common Substring

A(BCD)EF
G(BCD)FE
---
BCD

• 해당 예시에서 최장 공통 부분수열은 BCDF, BCDE가 될 수 있습니다. 부분수열이기 때문에 문자 사이를 건너뛰어 공통되면서 가장 긴 부분 문자열을 찾으면 됩니다. 최장 공통 문자열은 BCD입니다. 부분문자열이 아니기 때문에 한번에 이어져 있는 문자열만 가능합니다.

최장 공통 문자열

• 최장 공통 부분수열을 구하기 전에 최장 공통 문자열을 먼저 보도록 하겠습니다. 해당 과정이 더 쉽고, 최장 공통 부분수열을 구하는데 사용되기 때문에 먼저 알아보겠습니다.
• 점화식

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]

• 최장 공통 문자열의 점화식을 코드로 작성해 보았습니다. 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. 위 과정을 반복합니다.
• 위 과정이 성립하는 이유는 공통 문자열은 연속되야 하기 때문입니다. 현재 두 문자가 같을때 두 문자의 앞 글자까지가 공통 문자열이라면 계속 공통 문자열이 이어질 것이고, 아니라면 본인부터 다시 공통 문자열을 만들어 가게 될 것입니다.

---

최장 공통 부분수열(Longest Common Subsequence)길이 구하기

• 그렇다면 이번에는 다른 LCS인 최장 공통 부분수열을 만들어 보겠습니다.
• 점화식

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(LCSp[i - 1][j], LCS[i][j - 1])

• 최장 공통 부분수열의 점화식을 코드로 작성해 보았습니다. 위와 마찬가지로 LCS라는 2차원 배열에 매칭하고 마진값을 설정한 후 검사합니다.
  1. 문자열A, 문자열B의 한글자씩 비교해봅니다.
  2. 두 문자가 다르다면 LCS[i - 1][j]와 LCS[i][j - 1] 중에 큰 값을 표시 합니다.
  3. 두 문자가 같다면 LCS[i - 1][j - 1]값을 찾아 +1 합니다.
  4. 위 과정을 반복합니다.
• 최장 공통 문자열을 구하는 과정과 다른 부분은 비교하는 두 문자가 다를때입니다. ㅣㅂ교하는 두 문자가 같을때는 같은 과정을 보여줍니다.