[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

emplam27·2021년 1월 2일
161
post-thumbnail

Longest Common Subsequence? Substring?

LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다.

문자열 ABCDEFGBCDFE를 이용하여 차이점을 예시로 들어보면

Longest Common Subsequence와 Longest Common Substring의 차이

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



최장 공통 문자열(Longest Common Substring)

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

점화식

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. 위 과정을 반복합니다.

위 과정이 성립하는 이유는 공통 문자열은 연속되야 하기 때문입니다. 현재 두 문자가 같을때 두 문자의 앞 글자까지가 공통 문자열이라면 계속 공통 문자열이 이어질 것이고, 아니라면 본인부터 다시 공통 문자열을 만들어 가게 될 것입니다. 아래 예시를 통해 직관적으로 확인할 수 있습니다.

구현과정

logest common substring 1

logest common substring 2

logest common substring 3



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

그렇다면 이번에는 다른 LCS인 최장 공통 부분수열(Longest Common Subsequence)를 만들어 보겠습니다.

점화식

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])

최장 공통 부분수열의 점화식을 코드로 작성해보았습니다. 위와 마찬가지로 LCS라는 2차원 배열에 매칭하고 마진값을 설정한 후 검사합니다.

  1. 문자열A, 문자열B의 한글자씩 비교해봅니다.
  2. 두 문자가 다르다면 LCS[i - 1][j]LCS[i][j - 1] 중에 큰값을 표시합니다.
  3. 두 문자가 같다면 LCS[i - 1][j - 1] 값을 찾아 +1 합니다.
  4. 위 과정을 반복합니다.

최장 공통 문자열을 구하는 과정과 다른부분은 비교하는 두 문자가 다를 때 입니다. 비교하는 두 문자가 같을 때는 같은 과정을 보여줍니다. 왜 어떤 부분은 다른 로직을, 어떤부분은 같은 로직을 사용하는지 상세히 살펴보겠습니다.

1. LCS[i - 1][j]LCS[i][j - 1]는 어떤 의미인가?

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

LCS 구현과정 1-1

문자열 ABGBC를 비교(위 그림의 초록색 부분)하는 과정을 예로 들어보겠습니다. AB와 GBC의 최대 공통 부분수열이 B라는 것을 알기 위해서는 문자열 A와 GBC를 비교하는 과정, 문자열 AB와 GB를 비교하는 과정이 필요합니다. 문자열 ABGB의 비교 과정에서 최대 공통 부분수열이 B임을 확인했기 때문에 문자열 ABGBC의 최대 공통 부분수열 역시 B가 되는 것입니다.

LCS 구현과정 1-2

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

최대 공통 문자열을 구할 때 비교하는 문자가 같으면 LCS[i][j] = LCS[i - 1][j - 1] + 1의 과정을 거쳤습니다. 이 과정이 어떻게 최대 공통 부분수열에도 똑같이 적용될까요? 부분수열이 연속될 필요가 없음을 위 과정에서 여러번 보았습니다. 그렇다면 답은 간단합니다. 두 문자가 같은 상황이 오면 지금까지의 최대 공통 부분수열에 1을 더해주는 것 입니다.

LCS 구현과정 2-1

문자열 ABCGBC를 비교(위 그림의 초록색 부분)하는 과정을 예로 들어보겠습니다. LCS 배열은 LCS[i - 1][j]LCS[i][j - 1]의 비교를 통해 언제나 본인까지의 최대 공통 부분수열 값을 가지고 있습니다. 문자열 ABGB를 비교할때와 문자열 ABCGBC를 비교할 때 달라진 점은 두 문자열 모두에 C가 추가된 점입니다. 때문에 기존의 최대 공통 부분수열인 BC를 더한 BC가 최대 공통 부분수열이 되는 것입니다.

LCS 구현과정 2-2

구현과정

logest common subsequence 1

logest common subsequence 2

logest common subsequence 3



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

위에서 LCS 구현과정을 통해 LCS 배열을 만들며 LCS의 길이를 알았습니다. 이제 만든 LCS 배열을 이용해 최장 공통 부분수열의 값을 찾아보겠습니다. 경우에 따라 여러가지 답이 나올 수 있기 때문에 아래 예시는 한가지 경우만을 보겠습니다.

과정은 다음과 같습니다.

  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 입니다.

구현과정

logest common subsequence 찾기 1

logest common subsequence 찾기 2

logest common subsequence 찾기 3



마치며

최장 공통 부분수열(Longest Common Subsequence)과 최장 공통 문자열(Longest Common Substring)에 대해 포스팅 해보았습니다. 이후 포스팅 역시 DP에 자주 활용되는 알고리즘을 포스팅 하겠습니다.

profile
내가 다시 보고 싶은 글이어야 남들도 보고 싶은 글이라 생각하며 작성합니다. 공부한 내용들을 건강하게 공유하며 함께 성장하고자 합니다😊😊

15개의 댓글

comment-user-thumbnail
2021년 6월 28일

good!!

답글 달기
comment-user-thumbnail
2021년 11월 24일

엄청난 정성이 담긴 글 잘 보았습니다. 인터넷에 존재하는 LCS 설명 글 중 최고입니다.

1개의 답글
comment-user-thumbnail
2022년 3월 31일

감사합니다

답글 달기
comment-user-thumbnail
2022년 4월 23일

감사합니다!

답글 달기
comment-user-thumbnail
2022년 4월 25일

정말 감사합니다 바로 이해됐습니다!

답글 달기
comment-user-thumbnail
2022년 10월 14일

감사합니다! 잘읽었습니다.😊

답글 달기
comment-user-thumbnail
2022년 11월 5일

감사합니다 ~! 다음에 또 보고 싶어서 블로그에 참조로 출처를 남겼습니다 ~!

답글 달기
comment-user-thumbnail
2022년 11월 14일

정말 큰 도움 받았습니다!

답글 달기
comment-user-thumbnail
2022년 12월 10일

좋은 글 감사합니다!

답글 달기
comment-user-thumbnail
2022년 12월 16일

좋은 글 잘 읽었습니다! 블로그에 참고로 출처 남겼습니다.

답글 달기
comment-user-thumbnail
2023년 9월 21일

이게 바로 선생님이지....

답글 달기
comment-user-thumbnail
2023년 9월 25일

너무 좋은 설명 감사합니다!!! 😎

답글 달기
comment-user-thumbnail
2024년 1월 19일

정말 좋은 포스팅 감사합니다.
A, B, C, D, E, F 와 G,B,C,D,F,E,Z,K 를 이용하여 비교해봤을때
result 배열을 생성을 하기 위해 탐색 우선순위를 왼쪽부터 하는 것과 위쪽부터 하는 것이 그 결과가 사뭇다르던데요.
이거는 그냥 무시하는 현상일까요?
아니면 왼쪽이나 위쪽에 대해 우선순위를 두는 조건이 따로 있는 걸가요?

답글 달기
comment-user-thumbnail
2024년 1월 29일

감사합니다 ! 덕분에 LCS 한 번에 이해했습니다.

답글 달기