LCS 알고리즘

September 26, 2023

LCS1

(더 좋은 예시를 들고 싶었는데, 푸바오랑 맞출만한 단어가 안떠올라서…
더 좋은 단어 있음 말씀해주세요…)

Longest Common Substring과 Longest Common Subsequence의 차이를,
그림으로 설명해봤습니다. 차이가 보이시나요?
Longest Common Substring은 한 번에 이어진 문자열만 찾아내고,
Longest Common Subsequence는 공백을 건너뛰면서 공통되는 문자열을 찾는다는 점입니다.
비슷해보이면서도 헷갈리기 때문에, 구하는 점화식과 구하는 과정등을 보면서 같이 알아봐야합니다.
한 번 알아보도록 하겠습니다.

1. 최장 공통 부분문자열(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

최장 공통 부분문자열과 최장 공통 부분수열 모두 2차원 array형태를 이용합니다.
i, j가 1 이상일 때부터 검사를 시작하는데, 검사 순서는 아래와 같습니다.

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

최장 공통 부분문자열은 연속되어야하므로
현재 두 문자가 같을 때 두 문자의 앞 글자까지가 공통 문자열이라면 계속 공통 문자열이 이어지고,
아니라면 그 부분부터 다시 공통 부분문자열을 만들어가게 됩니다.
그림으로 보면 아래와 같습니다.

⓵ 앞 마진이 0인 2차원 배열을 생성하여,
Fubao 문자열과 Fusion 문자열을 한 글자씩 비교를 시작합니다.

Substring1

⓶ LCS[1][1] 부분에 같은 문자열 F가 존재하며,
LCS[0][0] 부분은 0이므로 0과 1을 더한 1을 표시합니다.

Substring2

⓷ 마찬가지로 LCS[2][2] 부분에 같은 문자열 u가 존재하며,
LCS[1][1] 부분은 1이므로 1과 1을 더한 2를 표시합니다.

Substring3

⓸ 그 후에는 같은 문자열이 안나오다가, LCS[5][5] 부분에 같은 문자열 o가 나옵니다.
하지만 LCS[4][4] 부분이 0이므로 0과 1을 더한 1을 표시합니다.

Substring4

⓹ 최종적으로 숫자의 최댓값인 2까지의 문자열 Fu가 최장 공통 부분문자열이 됩니다.

Substring5

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

최장 공통 부분문자열이 연속되어있는 공통 문자열을 찾는 문제였다면,
최장 공통 부분수열은 공백이나 다른 문자열까지 고려하여 공통되는 문자열 중
가장 긴 것을 찾는 문제입니다.

좀 더 어렵게 표현하면, 주어진 여러 개의 수열 모두의 부분수열이 되는 수열 중에
가장 긴 것을 찾는 문제입니다.
diff 유틸리티의 근간이 되며, bioinformatics에도 많이 응용되고 있습니다.
그러면 점화식을 한 번 살펴보도록 하겠습니다.
위에서 살펴봤던 최장 공통 부분문자열의 점화식이 일부분 쓰이는 것을 볼 수 있습니다.

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

해당 점화식의 진행 순서는 아래와 같습니다.

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

최장 공통 부분문자열을 구하는 과정과 다른 부분은 비교하는 두 문자가 다를 때입니다.
부분수열은 연속된 값이 아니기 때문에,
현재의 문자를 비교하는 과정 이전의 최대 공통 부분수열은 계속되어야 합니다.
그 과정이 바로 LCS[i - 1][j], LCS[i][j - 1]입니다.
그림으로 보면 아래와 같습니다.

⓵ 똑같이 앞 마진이 0인 2차원 배열을 생성하여,
Fubao 문자열과 Fusion 문자열을 한 글자씩 비교를 시작합니다.

Subsequence1

⓶ LCS[1][1] 부분에 같은 문자열 F가 존재하며,
LCS[0][0] 부분은 0이므로 0과 1을 더한 1을 표시합니다.

Subsequence2

⓷ else 부분에서 max(LCS[i - 1][j], LCS[i][j - 1]) 부분 때문에,
현재 문자를 비교하는 과정 이전의 최대 공통 부분수열은 유지됩니다.
즉, Fusion의 F와 Fubao를 비교하는 과정의 최대 공통 부분수열은 1이 됩니다.
또한 else조건으로 인해, Fusion의 F이후 값들도 1이 됩니다.

Subsequence3

⓸ 마찬가지로 Fusion의 u와 Fubao를 비교하는 과정에서,
LCS[2][2]는 LCS[1][1]에 1을 더한 2가 되며, 그것이 계속 유지됩니다.
즉, Fusion의 u와 Fubao를 비교하는 과정의 최대 공통 부분수열은 2가 됩니다.
또한 else조건으로 인해, Fusion의 u이후 값들도 2가 됩니다.

Subsequence4

⓹ 해당 과정을 반복하면 최종적으로 아래와 같은 결과가 나옵니다.

Subsequence5

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

이렇게 만든 LCS 배열을 이용하여 값을 찾을 수 있습니다.
과정은 아래와 같습니다.

결과값을 저장할 result 배열을 준비한 뒤, LCS 배열의 가장 마지막 값에서 시작합니다.
LCS[i - 1][j]와 LCS[i][j - 1] 중 현재 값과 같은 값을 찾습니다.
만약 같은 값이 있다면 해당값으로 이동하며,
같은 값이 없다면 result 배열에 해당 문자를 넣고 LCS[i - 1][j - 1]로 이동합니다.
2번 과정을 반복하다 0으로 이동하게 되면 종료합니다. result 배열의 역순이 LCS입니다.

그림으로 보면 아래와 같습니다.

⓵ LCS의 마지막 부분에서 시작, LCS[5][5]에 같은 값이 있으므로 이동합니다.

Subsequence6

⓶ LCS[5][5]와 더 이상 같은 값이 없으므로, 배열에 값을 채웁니다.
그 후 LCS[4][4]로 이동합니다.

Subsequence7

⓷ LCS[3][4], LCS[4][3]에 같은 값이 있는지 보고, 그 값으로 이동합니다.
(여기서는 왼쪽, 위로 움직이도록 하겠습니다.)
같은 값으로 계속 이동하다가,
더 이상 LCS[i - 1][j], LCS[i][j - 1]에 같은 값이 없는 LCS[2][2]에서 배열에 값을 채웁니다.
그리고 LCS[1][1]로 이동합니다.

Subsequence8

⓸ LCS[1][1]도 주변에 같은 값이 없으므로, 배열에 값을 채웁니다.
그리고 LCS[0][0]으로 이동합니다.

Subsequence9

⓹ LCS[0][0]이 0이므로 종료하고, 배열을 뒤집으면 최장 공통 부분수열이 됩니다.

Subsequence10

4. 최장 공통 부분수열(Longest Common Subsequence)의 시간 복잡도

위에서는 result라는 정답 배열에 메모이제이션으로 겹치는 부분을 저장하고,
상위 단계로 이동했을 때 이 정보를 이용할 수 있도록 하는 과정을 이용했습니다.
즉 우리는 위 문제를 DP(Dynamic Programming)로 해결했다고 할 수 있습니다.

길이가 n과 m인 문자열에서, DP에 의한 실행 시간은 $O(n \times m)$ 입니다.
각 문자열의 모든 캐릭터 쌍에 대해 검사를 수행하기 때문에,
두 문자열의 길이에 선형적으로 비례하는 시간이 소요되기 때문입니다.
코드 최적화나 해쉬를 이용해서 복잡도를 더 줄일 수 있는 방법도 있는데,
그 부분은 시간 날 때 추가하여 포스팅해보겠습니다.

5. LCS 알고리즘 코드(Python)

LCS 알고리즘 full 코드는 아래와 같습니다.
이 코드는 백준 ‘비밀번호 만들기’[ 링크 ]의 해답이기도 합니다.
반복문 및 함수 부분에 위에 그림으로 살펴봤던 핵심 부분이 있습니다.
다른 문제나 프로그램에 이용할 때는 필요한 부분을 수정해주세요!

# LCS 알고리즘
def print_lcs(i, j):
    if i == 0 or j == 0:
        return
    if str1[i] == str2[j]:
        print_lcs(i - 1, j - 1)
        print(str1[i], end="")
    else:
        if arr[i][j - 1] == arr[i][j]:
            print_lcs(i, j - 1)
        else:
            print_lcs(i - 1, j)

a = input()
b = input()
str1 = "0" + a
str2 = "0" + b

arr = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]

for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        if str1[i] == str2[j]:
            arr[i][j] = arr[i - 1][j - 1] + 1
        else:
            arr[i][j] = max(arr[i - 1][j], arr[i][j - 1])

print_lcs(len(a), len(b))

6. 정리

오늘은 최장 공통 부분문자열 및 최장 공통 부분수열에 대해 알아봤습니다.
다음 포스팅으로는 이 알고리즘을 이용한 diff 유틸리티에 대해 알아보겠습니다.

Reference

① https://velog.io/@emplam27/LCS
② https://ko.wikipedia.org/wiki/최장_공통_부분수열

LCS 알고리즘

1. 최장 공통 부분문자열(Longest Common Substring)

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

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

4. 최장 공통 부분수열(Longest Common Subsequence)의 시간 복잡도

5. LCS 알고리즘 코드(Python)

6. 정리

Reference

Leave a comment

You may also enjoy

‘다잇다’ 시리즈 ② : ‘다잇다’ 홈쇼핑의 고객 관점에서 구매활동성 증대 방안 분석하기

‘다잇다’ 시리즈 ① : 파레토 차트를 통해 ‘다잇다’ 홈쇼핑의 매출 성장 방안 인사이트 도출하기

태블로 따라쟁이 ① : 제주오름도 식후경(공공데이터포털 데이터 시각화)

조용한 사직(Quiet Quitting)을 어떻게 정의할 수 있을까?