Python에서 가장 긴 공통 하위 시퀀스
Rohan Timalsina
2023년10월10일
하위 시퀀스는 나머지 문자의 순서를 변경하지 않고 일부 또는 전혀 문자를 제거한 후 주어진 시퀀스에서 얻은 시퀀스입니다. 최장 공통 부분 수열이란 주어진 모든 수열에 공통인 가장 긴 부분 수열을 의미한다.
이 튜토리얼은 Python에서 두 시퀀스 사이의 가장 긴 공통 하위 시퀀스의 길이를 찾는 방법을 알려줍니다.
순진한 방법을 사용하여 Python에서 가장 긴 공통 하위 시퀀스 찾기
S1과 S2의 두 시퀀스가 있다고 가정합니다.
S1 = QEREW
S2 = QWRE
여기서 일반적인 하위 시퀀스는 QE, QW, QR, QRE 및 RE입니다. 이 중 가장 긴 공통 부분 수열은 QRE이며 길이는 3입니다.
이제 가장 긴 공통 하위 시퀀스의 길이를 인쇄하는 Python 솔루션을 살펴보겠습니다.
암호:
def LCS(S1, S2, x, y):
if x == 0 or y == 0:
return 0
if S1[x - 1] == S2[y - 1]:
return LCS(S1, S2, x - 1, y - 1) + 1
return max(LCS(S1, S2, x, y - 1), LCS(S1, S2, x - 1, y))
S1 = "QEREW"
S2 = "QWRE"
x = len(S1)
y = len(S2)
print("Length of LCS is", LCS(S1, S2, x, y))
출력:
Length of LCS is 3
이 방법은 Python에서 LCS 문제를 해결하기 위한 재귀적 접근 방식입니다. 주어진 시퀀스의 가능한 모든 하위 시퀀스를 확인하고 가장 긴 공통 하위 시퀀스를 찾습니다.
동적 프로그래밍을 사용하여 Python에서 가장 긴 공통 하위 시퀀스 찾기
동적 프로그래밍은 일반 재귀 방법의 최적화입니다. 보시다시피 반복되는 함수 호출이 많은 재귀 접근 방식에는 하위 문제가 중첩됩니다.
동적 접근 방식은 필요할 때 사용할 수 있도록 각 함수 호출의 결과를 배열에 저장합니다. 결과적으로 함수 호출 횟수가 줄어듭니다.
암호:
def LCS(S1, S2, m, n):
R = [[None] * (n + 1) for i in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0 or j == 0:
R[i][j] = 0
elif S1[i - 1] == S2[j - 1]:
R[i][j] = R[i - 1][j - 1] + 1
else:
R[i][j] = max(R[i - 1][j], R[i][j - 1])
return R[m][n]
S1 = "QEREW"
S2 = "QWRE"
m = len(S1)
n = len(S2)
print("Length of LCS is", LCS(S1, S2, m, n))
출력:
Length of LCS is 3
이 방법은 O(mn)의 시간 복잡도를 가지므로 더 빠르고 효율적입니다.
작가: Rohan Timalsina
