[코테, 알고리즘] 백준 class 4 - LCS(최장 공통 부분 수열)

김재연·2023년 8월 11일
0
post-thumbnail

[9251] LCS


LCS하면 보통 최장 공통 부분수열을 말하지만, 최장 공통 문자열을 말하기도 한다.

  1. Longest Common Substring (최장 공통 문자열)
    : 한번에 이어져 있어야 함
    ex) ABCDEF 와 GBCDFE 의 최장 공통 문자열 = BCD

  2. Longest Common Subsequence (최장 공통 부분수열)
    : 문자 사이를 건너뛸 수 있음
    ex) ABCDEF 와 GBCDFE 의 최장 공통 문자열 = BCDF / BCDE

LCS 구현은 DP로 이루어진다. (또 DPㅡㅡ)

기본틀은 이렇게 문자열의 문자를 하나씩 비교해서 두 문자가 같은지, 다른지에 따라 값을 갱신한다. (이후 설명에서 아래 2차원배열을 LCS라 부른다.)


1. 최장 공통 문자열

(1) LCS에는 무슨 값이 들어가는가?

LCS가 정확히 뭘 담는건지 모르겠어서 고민을 많이 했는데, 내 생각으론 다음과 같다.

LCS[i][j] = str1은 str1[i], str2는 str2[j]로 끝나는 최장공통문자열

말이 복잡한데, 비교하는 두 문자가 같은지 다른지에 따라 경우의 수를 나누어서 정리하면 이렇다.

if str1[i] == str2[j] == 'X':
	LCS[i][j] = str1과 str2를 비교했을 때 'X'로 끝나는 최장공통문자열
    ('X'가 앞에서부터 만들어진 최장공통문자열의 뒤에 붙을지,
     새로운 최장공통문자열의 시작이 될지는 이전값을 통해 알 수 있다. => DP)
else:
	LCS[i][j] = 애초에 끝자리가 다르므로 최장공통문자열일 수가 없음 (, 0)

(2) 예시

str1 = GBCDFE
str2 = ABCDEF

  1. str1[3] == str2[3] == 'C'이므로, LCS[3][3]에는 GBC와 ABC를 비교해서 C로 끝나는 최장공통문자열인 BC의 길이 2가 들어가게 된다.
    cf) GB(C)와 AB(C)의 최장공통문자열 'B' + 'C' = 'BC'

str1 = GBCDFE
str2 = ABCDEF

  1. 반면 str1[4] != str2[5]이므로, LCS[4][5]에는 GBCD와 ABCDE를 비교했을때 각각 DE로 끝나는 최장공통문자열이란 존재할 수 없으므로 0이 들어가게 된다.

(3) 그림으로 보는 동작과정

쉽게 말하자면 현재 비교하고 있는 문자가 똑같을때, 각 문자열의 현재 문자의 바로 앞에 있는 문자가 이미 만들어져있는 최장공통문자열의 일부인지 보고, 일부이면 그 뒤에 붙이고, 아니라면 이 문자를 새로운 최장공통문자열의 시작으로 보는 것이다. 어쨌든 후자의 경우에도 0(없음)에서 1(현재문자)을 더하는 점에서 똑같기 때문에, LCS[i][j] = LCS[i-1][j-1]+1이라는 식이 성립하는 것이다.


(4) 코드

코드로 나타내면 다음과 같다.

LCS = [[0 for _ in range(len(str2)+1)] for _ in range(len(str1)+1)]

for i in range(1, len(str1)+1):
  for j in range(1, len(str2)+1):
    if str1[i-1] == str2[j-1]:
      LCS[i][j] = LCS[i-1][j-1] + 1
    else:
      LCS[i][j] = 0

# LCS의 최대값이 최장공통문자열의 길이

2. 최장 공통 부분수열

최장 공통 문자열과 알고리즘은 같은데, 두 문자가 다를 때 처리하는 방식이 다르다. 최장 공통 부분수열은 두 문자가 다를 때도 이를 건너뛰고 LCS를 이어갈 수 있기 때문에, 0으로 퉁치는게 아니라 추가적인 식이 필요하다.

(1) LCS에는 무슨 값이 들어가는가?

이번에는 LCS에 담는 내용이 (비교적?) 직관적이다.

LCS[i][j] = str1[0:i]과 str2[0:j]의 최장공통부분수열
			(다만, 최장공통문자열과는 달리
            최장공통부분수열의 끝이 str1[i]나 str2[j] 이전에 위치한 문자일 수 있다.)

마찬가지로 비교하는 두 문자가 같은지 다른지에 따라 경우의 수를 나누어서 정리하면 다음과 같다.

if str1[i] == str2[j] == 'X':
	LCS[i][j] = str1[0:i]와 str2[0:j]의 최장공통부분수열 + 'X'
else:
	LCS[i][j] = max(str1[0:i]와 str2의 최장공통부분수열, str1와 str2[0:j]의 최장공통부분수열)
  1. 만약 str1[i] == str2[j]라면, 현재 문자를 제외한 이전 문자열들끼리 비교해서 구한 최장공통부분수열에 현재 문자를 더하면 된다.

  2. 그런데 str1[i] != str2[j]라면? 현재 문자는 최장공통부분수열에 넣을 수 없지만, 현재 문자를 그냥 건너뛰고 다음에 더 이어갈 수 있으므로, 이전에 구한 최장공통부분수열 중 가장 큰 값을 복사해놓으면 된다.

    여기서 '이전에 구한 최장공통부분수열'이란, str1[0:i]str2의 최장공통부분수열, 또는 str1str2[0:j]의 최장공통부분수열이다.


(2) 예시

str1 = GBCDFE
str2 = ABCDEF

  1. str1[3] == str2[3] == 'C'이므로, LCS[3][3]에는 GBC와 ABC의 최장공통부분수열인 BC의 길이 2가 들어가게 된다.
    cf) GB(C)와 AB(C)의 최장공통부분수열 'B' + 'C' = 'BC'

str1 = GBCDFE
str2 = ABCDEF

  1. 반면 str1[3] != str2[2]이므로, LCS[3][2]에는 GBC와 AB의 최장공통부분수열이 들어가되 각각 CB는 포함하지 않은 값이 들어갈 것이다. 이때 이전에 구한 GB와 AB의 최장공통부분수열, GBC와 A의 최장공통부분수열 중 큰 값이 들어간다.

(3) 그림으로 보는 동작과정

ㅋㅋㅋㅋ 내가 그려놓고도 세상 정신없다

아무튼 가장 마지막값([-1][-1])이 최장공통부분수열의 길이다.


(4) 코드

LCS = [[0 for _ in range(len(str2)+1)] for _ in range(len(str1)+1)]

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

print(LCS[-1][-1])

(5) LCS 실제 값 찾기

  1. LCS의 가장 마지막값(LCS[-1][-1])부터 시작한다.
  2. LCS[i-1][j]LCS[i][j-1] 중 같은 값이 있으면 해당 위치로 이동한다.
  3. 같은 값이 없으면 해당 위치의 문자를 결과에 저장하고, LCS[i-1][j-1]로 이동한다.
  4. LCS[i][j]가 0이 될 때까지 2~3번 과정을 반복한다.
  5. 탐색을 종료하고 결과를 뒤집으면 실제 LCS의 값이다.
result = []
i = len(str1)
j = len(str2)
while dp[i][j] > 0:
	if dp[i-1][j] == dp[i][j]:
		i -= 1
    elif dp[i][j-1] == dp[i][j]:
		j -= 1
    else:
		result += str1[i-1]
		i -= 1
		j -= 1
  result.reverse()
  print("".join(result))

Reference

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

profile
일기장같은 공부기록📝

0개의 댓글