LCS 알고리즘

LCS (Longest Common Subsequence) 알고리즘

• 최장 공통 부분수열
• 최장 공통 문자열

점화식

\[LSC(x_i, y_i) = \begin{cases} 0\\ LCS(x_{i-1}, y_{j-1} + 1)\\ max(LCS(x_i, y), LCS(x, y_i)) \end{cases}\]

Top-Down 방식

• 재귀적

시간복잡도 O(2^ (m + n))**

구현방식

X = ‘ABCBDAB’ Y = ‘BDCAB’

1. 마지막 문자 부분이 같을 경우
   1. 재귀 + 1
2. 마지막 문자 부분이 다를 경우
   1. Y의 마지막 문자를 줄이고 X와 재귀
   2. X의 마지막 문자를 줄이고 Y와 재귀
   3. 2-1, 2-2 중 최대값

X = 'ABCBDAB'
Y = 'BDCAB'

def LCS(X, Y):
	m, n = len(X), len(Y)
	if m <= 0 or n <= 0:
		return 0

	if X[-1] == Y[-1]:
		return LCS(X[-1], Y[-1]) + 1
	else:
		return max(LCS(X, Y[:n - 1]), LCS(X[:m - 1], Y))

count = LCS(X, Y)
print(count)

Bottom-Up 방식

• DP

시간복잡도 O(m + n)

1. 이차원 배열 선언
2. 마지막 문자가 같을 경우
   1. 대각선값 + 1
3. 마지막 문자가 다를 경우
   1. 왼쪽, 위의 값 중 가장 큰 값으로 갱신

X = 'ABCBDAB'
Y = 'BDCAB'
m, n = len(X), len(Y)
memo = [[0] * (n + 1) for _ in range(m + 1)]

def LCS(X, Y):
	for i in range(m):
		for j in range(n):
			if X[i] == Y[j]:
				memo[i + 1][j + 1] = memo[i][j] + 1
			else:
				memo[i + 1][j + 1] = max(memo[i][j + 1], memo[i + 1][j])
	return memo[m][n] 

count = LCS(X, Y)
print(count)

사용처

1. 버전관리 시스템 (git)
2. DNA, RNA 서열 분석
3. 오타 교정