LCS 알고리즘

1. LCS 알고리즘이란❓

• 최장 공통 부분수열(Longest Common Subsequence)
  • 연속되지 않은 부분 문자열을 찾는 것
• 최장 공통 문자열(Longest Common Substring)
  • 연속되는 부분 문자열을 찾는 것

참고 : 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

 

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

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

 

• 최장 공통 부분 문자열(Longest Common Subsequence)을 알아보기 전에 공통 문자열이 어떻게 동작하는지 부터 살펴보자
• 편의상 맨 처음 인덱스는 0 으로 고정하여 문제에 접근한다.
• 2차원 배열을 통해서 공통된 부분을 찾아나가는 과정을 반복해서 진행한다.

 

 예시로 'ABCDEF' / 'GBCDFE' 를 통해서 살펴보자

초기 상황

1. G 부터 시작해서 같은 문자 값이 있는지 체크를 진행한다.
   
   • 같은 문자 값이 없으므로 0 으로 채워나간다.
     

     

     G와 일치하는 문자열 체크

2.  G를 살핀 후 B를 통해서 넘어가서 일치하는 문자열을 체크한다.
   • B의 경우 일치하는 문자가 존재하므로 B인덱스 위치에서 -1 씩 해준 i-1, j-1 에서 +1 한 값을 넣어준다.
     

     

     B부분 결과

3. 이후 차례로 C, D, F, E 를 비교해 가면서 진행을 한다.
4. 이 과정에서 우리가 구하는 부분은 최장 공통 문자열 이기 때문에 얼마나 많은 부분이 중복되는지 체크를 해줘야 한다.
5. 이 말은 일치하는 문자열을 찾았을 경우 그 인덱스에서 -1 해준 값에 +1 을 해주는 식으로 얼마나 길이가 긴지를 구해줘야 한다.

결과

 위 과정을 다 진행하고 난 후 체크를 해보면 최장 공통 문자열의 길이는 3이 제일 긴 부분으로 나오게 되며 'BCD' 가 나오게 된다.

 

코드 구현

from pprint import pprint as print

word = input()
word_second = input()

word_length = len(word)
second_word_length = len(word_second)

matrix = [[0] * (word_length+1) for _ in range(second_word_length+1) ]

for i in range(second_word_length+1):
    for j in range(word_length+1):
        if i != 0 and j != 0:
            if word[j-1] == word_second[i-1]:
                matrix[i][j] = matrix[i-1][j-1] + 1
print(matrix)

실행 결과

 

 

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

 

• 앞서 최장 공통 문자열에 대해서 살펴봤고, 최장 공통 부분수열의 경우 앞에서 말했던 내용을 살짝 응용해서 적용한다.
• 기존 문자열 구하는 방법과 동일하지만 공통 부분수열의 경우는 연속할 필요가 없기 때문에 두 문자가 다를 경우 값을 갱신해주는 방향으로 문제를 접근해야 한다.
• 예시 및 설명을 통해서 접근하는 방식을 살펴보자

  똑같이 'ABCDEF' / 'GBCDFE' 를 통해서 살펴보자

1. 문자를 한 글자씩 비교를 진행한다.
2. 두 문자가 다를 경우 현재 문자의 인덱스를 기준으로 list[i-1][j], list[i][j-1] 중 큰 값을 표시해준다.
3. 두 문자가 같은 경우 list[i-1][j-1] 의 값에 +1 을 진행해준다.
4. 위 과정을 반복한다.

초기 상황

1. B 부터 문자가 같은지 다른지 비교를 진행한다.
   

   

   B문자열 체크

2. 비교를 진행하면서 문자가 같은경우 list[i-1][j-1] 값에 +1 을 진행해준다.
3. 문자가 같은 경우가 나온 이후로 다른 문자의 경우 그 위치에서 i-1 과 j-1 한 값중 큰 값을 갱신해준다.
   • 이 과정을 진행하는 이유는 예를 들어 C와 B가 같은지 확인하는 부분이라고 가정하면 앞선 AB와 GB의 최장 길이 수열의 길이와 A와 GBC의 최장길이 수열의 값을 비교해 현재까지 제일 긴 수열의 길이를 찾아줘야 이후에 같은 문자열이 나온 경우 그 값에 +1을 할 수 있다.
     

     

     위 설명대로 C의 위치에서 진행한 결과값

4. C 까지 비교했으므로 D로 넘어가보면
   

   

   D의 결과 이렇게 됐다

5. 마찬가지로 이후 계속해서 진행해볼 경우

최종 결과

 

최장 공통 부분수열의 경우 위와 같은 방법에 의해서 값이 갱신되고 우리가 구할 수 있는 부분수열의 최장 길이는 4가 나오게 된다.

더보기

word_one = input()
word_two = input()

one_length = len(word_one)

two_length = len(word_two)

LCS_matrix = [ [0]*(one_length+1) for _ in range(two_length+1)]

max_value = 0

for i in range(one_length+1):
    for j in range(two_length+1):
        if i == 0 or j == 0:
            LCS_matrix[j][i] = 0
        else:
            if word_one[i-1] == word_two[j-1]:
                LCS_matrix[j][i] = LCS_matrix[j-1][i-1] + 1
            else:
                LCS_matrix[j][i] = max(LCS_matrix[j-1][i], LCS_matrix[j][i-1])
    if LCS_matrix[j][i] > max_value:
        max_value = LCS_matrix[j][i]

print(max_value)

 

최종 결과