가장 긴 공통 부분 수열: Python, C++ 예시
사라 첸
가장 긴 공통 부분 수열은 무엇입니까?
LCS(Longest Common Subsequence)는 두 개의 문자열/패턴/객체 시퀀스가 제공된다는 의미입니다. 이 두 시퀀스/문자열 중에서 문자열이나 패턴 모두에 존재하는 동일한 순서로 요소의 가장 긴 하위 시퀀스를 찾아야 합니다.
예시
예를 들어, 두 개의 문자열이 제공됩니다.
가정해보자.
Pattern_1 = "RGBGARGA"
Pattern_2 = "BGRARG"
- Pattern_1에서 “RGB”, “RGGA”, “RGAR”와 같은 시퀀스를 생성할 수 있습니다. 시퀀스를 생성하려면 문자열에서 각 문자의 상대적 위치를 유지해야 합니다.
- Pattern_2에서 "BGR", "BRAG", "RARG"와 같은 시퀀스를 생성할 수 있습니다. 원래 문자열의 상대 위치를 유지하는 한 시퀀스를 생성할 수 있습니다.
상대 위치라는 용어는 순서를 의미합니다.
예를 들어, "BRG"는 원래 문자열 패턴_2에서 "B"가 먼저 나타나고 그 다음 "R", "G"가 나타나므로 유효한 시퀀스입니다. 그러나 시퀀스가 "RBRG"인 경우 유효하지 않습니다. 원래 문자열(pattern_2)에서는 “B”가 먼저 오기 때문입니다.
주어진 두 시퀀스 또는 배열에서 가장 긴 공통 부분 시퀀스를 찾는 두 가지 옵션이 있습니다.
- 순진한 방법
- 동적 프로그래밍 솔루션: 가장 긴 공통 부분 시퀀스는 LCS라고도 합니다.
순진한 솔루션은 시간 복잡도가 더 크고 최적의 솔루션이 아닙니다. 동적 프로그래밍 솔루션(DP)을 사용하여 복잡도 문제를 극복합니다.
순진한 방법
단순 방법은 시간 복잡도 및 기타 최적화 요소에 관계없이 문제에 대한 간단한 접근 방식입니다.
Naive 방법은 대부분의 경우 "Brute Force", 다중 루프, 재귀 방법으로 구성됩니다.
무차별 대입이라는 용어는 주어진 문제에 대해 가능한 모든 패턴을 검토하는 것을 의미합니다.
예시
위의 패턴1과 패턴2의 예에서 패턴1의 길이가 m이고 패턴2의 길이가 n이라고 가정해 보겠습니다. 가능한 모든 사례를 확인하려면 패턴1과 패턴2의 가능한 모든 하위 시퀀스를 평가해야 합니다.
다음은 간단한 4글자 문자열 "ABCD"입니다. 예를 들어 "ABCD"에서 시퀀스를 만들어야 합니다. 우리는 캐릭터를 취할 수도 있고 그렇지 않을 수도 있습니다. 이는 각 캐릭터에 대해 두 가지 선택이 있다는 것을 의미합니다.
그들은 :
- 캐릭터가 하위 시퀀스에 추가됩니다.
- 해당 문자는 하위 시퀀스에 추가되지 않습니다.
여기서 이미지는 "ABCD"라는 문자열로 만들 수 있는 모든 시퀀스를 보여줍니다.
문자가 1개인 시퀀스:
2개의 문자로 구성된 시퀀스:
3개의 문자로 구성된 시퀀스:
위 다이어그램에는 14개의 시퀀스가 있습니다. 기본적으로 빈 문자열인 문자를 사용하지 않으면 전체 시퀀스는 15개가 됩니다. 게다가 문자열 “ABCD” 자체도 시퀀스입니다. 따라서 전체 시퀀스는 16개입니다.
따라서 2개 생성이 가능합니다.4 또는 "ABCD"의 16개 하위 시퀀스. 그런 다음 길이가 다음과 같은 문자열입니다. m 총 2개의 하위 시퀀스가 필요합니다.m.
각 하위 시퀀스에 대해 전체 패턴을 확인해야 합니다. 2(n) 시간이 걸립니다. 0(n)은 실행에 걸리는 시간을 계산하는 복잡도 함수를 의미합니다.
따라서 총 시간 복잡도는 다음과 같습니다. O(n*2m). 예를 들어, 위에서 m=8과 n=5의 값을 보았습니다.
Naive Method의 단계는 다음과 같습니다.
단계 1) 패턴1에서 시퀀스를 가져옵니다.
단계 2) 1단계의 순서를 패턴2와 일치시킵니다.
단계 3) 일치하면 하위 시퀀스를 저장합니다.
단계 4) 패턴1에 더 많은 시퀀스가 남아 있으면 1단계로 다시 이동합니다.
단계 5) 가장 긴 하위 시퀀스를 인쇄합니다.
최적의 하부 구조
최적의 하위 구조라는 용어는 하위 문제를 해결하여 최적의 솔루션(단순)을 찾을 수 있음을 의미합니다. 예를 들어 위의 예에는 패턴1과 패턴2가 있습니다.
단계 1) 각 패턴에서 처음 두 문자를 가져옵니다.
단계 2) 각 패턴에서 세 번째부터 다섯 번째 문자를 가져옵니다.
단계 3) 나머지 문자들에 대해서도 비슷하게 계속하십시오.
하위 문자열(원래 문자열에서 생성된 문자열)에서 LCS를 찾습니다. 그런 다음 하위 문자열의 LCS 길이를 기록합니다.
이제 또 다른 흥미로운 속성이 있습니다. 중복되는 하위 문제. 문제 설명을 작은 하위 문제로 나누어 프로그램에서 여러 번 사용할 수 있는 경우 문제에 중첩된 하위 문제가 있다고 합니다.
아래 다이어그램은 재귀 알고리즘이 동일한 매개변수를 사용하여 함수를 여러 번 호출한 것을 보여줍니다.
예를 들어 재귀 트리를 살펴보겠습니다.
어두운 색 상자에서 겹치는 하위 문제를 볼 수 있습니다. ("RG", "RA"), ("RG", "R") 및 기타 문제가 여러 번 호출됩니다.
이를 최적화하기 위해 다음과 같은 접근 방식이 있습니다. 동적 프로그래밍 (DP).
가장 긴 통신 시퀀스의 재귀적 방법
위에 표시된 그래프는 재귀적 방법입니다. 각 재귀 함수에는 재귀를 중단하거나 스택에서 반환을 시작하는 기본 사례가 있습니다.
이 구현에서는 기본 사례를 사용합니다. 그래서 연산 다음과 같습니다:
- 마지막 요소 이전의 모든 요소가 일치하는 경우 길이를 XNUMX만큼 늘리고 반환합니다.
- 함수에 두 개의 패턴을 전달하고 반환값의 최대값을 가져옵니다.
- 한 패턴의 길이가 0이면 비교할 하위 시퀀스가 없습니다. 이 경우 XNUMX을 반환합니다. 이것이 재귀의 기본 사례입니다.
의사 코드 :
def lcs:
input: pattern_1, pattern_2, len_1, len_2
if len_1 or len_2 is zero:
then
return 0
if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]
then
return 1 + lcs(pattern_1, pattern_2,
len_1 - 1, len_2 - 1)
else
max of lcs(pattern_1, pattern_2, len_1 - 1, len_2),
lcs(pattern_1, pattern_2, len_1, len_2 - 1)
에서 구현 C++
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int lcs(string pattern_1, string pattern_2, int len_1, int len_2) {
if (len_1 == 0 || len_2 == 0)
return 0;
if (pattern_1[len_1 - 1] == pattern_2[len_2 - 1]) {
return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1);
} else {
return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1));
}
}
int main() {
string pattern_1, pattern_2;
pattern_1 = "RGBGARGA";
pattern_2 = "BGRARG";
cout<<"Length of LCS is: "<<lcs(pattern_1, pattern_2, pattern_1.size(), pattern_2.size())<<endl;
}
출력:
Length of LCS is: 5
파이썬으로 구현
def lcs(pattern_1, pattern_2, len_1, len_2):
if len_1 == 0 or len_2 == 0:
return 0
if pattern_1[len_1 - 1] == pattern_2[len_2 - 1]:
return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
else :
return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1))
pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Lenght of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))
출력:
Lenght of LCS is: 5
LCS(Longest Common Subsequence)의 동적 프로그래밍 방법
동적 프로그래밍은 일반 재귀 방법을 최적화하는 것을 의미합니다. 예를 들어 재귀적 또는 순진한 접근 방식 그래프를 보면 동일한 함수 호출이 여러 개 있음을 알 수 있습니다. 동적 프로그래밍 방법은 모든 계산을 배열에 기록하고 필요할 때 사용합니다.
mxn 차원의 2D 배열을 사용하겠습니다. 여기서 m과 n은 패턴1과 패턴2의 길이입니다.
럭셔리 2D 배열, 파이썬에서 List 데이터 구조를 사용하거나 벡터/배열 데이터 구조를 사용할 수 있습니다. C++.
DP를 사용하는 LCS용 의사 코드:
LCS(pattern_1, pattern_2):
m = length of pattern_1 + 1
n = length of pattern_2 + 1
dp[n][m]
for i in range 0 to n + 1:
for j in range 0 to m + 1:
if i or j equals to 0:
dp[i][j] = 0
else if pattern_1[i] == pattern_2[j]:
dp[i]][j] = dp[i - 1][j - 1] + 1
else :
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[n][m]
다음은 동적 프로그래밍 접근 방식을 위한 2D 배열 데이터 구조로 사용되는 테이블 LCS입니다.
여기서 사용한 논리를 논의해 보겠습니다. 단계는 다음과 같습니다:
단계 1) i 또는 j가 0이면 주어진 두 문자열에서 빈 문자열을 가져와 공통 부분 수열을 찾으려고 합니다. 그러나 우리가 취하는 하위 문자열은 비어 있으므로 하위 시퀀스 길이는 XNUMX입니다.
단계 2) 두 문자가 일치하면 이전 행의 (i-1,j-1) 인덱스에 있는 이전에 계산된 LCS를 증가시켜 (i,j) 인덱스에 값을 할당합니다.
단계 3) 일치하지 않으면 인접한 두 인덱스의 최대 LCS를 사용합니다. 이런 방식으로 2D 배열의 모든 값을 채워야 합니다.
단계 4) 마지막으로 2D 배열의 마지막 셀 값을 반환합니다.
기본적으로 2D 배열의 모든 값에는 공통 부분 수열의 길이가 포함됩니다. 이 중 마지막 셀에는 가장 긴 공통 부분 수열의 길이가 포함됩니다.
에서 구현 C++
#include<iostream>
using namespace std;
int lcs(string pattern_1, string pattern_2) {
int m = pattern_1.size();
int n = pattern_2.size();
// dp will store solutions as the iteration goes on
int dp[n + 1][m + 1];
for (int i = 0; i & lt; n + 1; i++) {
for (int j = 0; j & lt; m + 1; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (pattern_2[i - 1] == pattern_1[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n][m];
}
int main() {
string pattern_1 = "RGBGARGA";
string pattern_2 = "BGRARG";
cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;
}
출력:
Length of LCS: 5
에서 구현 Python
def lcs(pattern_1, pattern_2):
m = len(pattern_1)
n = len(pattern_2)
# dp will store solutions as the iteration goes on
dp = [
[None] * (n + 1) for item in range(m + 1)
]
for i in range(m + 1):
for j in range(n + 1):
if i == 0 or j == 0:
dp[i][j] = 0
elif pattern_1[i - 1] == pattern_2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else :
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS: ", lcs(pattern_1, pattern_2))
출력:
Length of LCS: 5
따라서 두 문자열 모두 길이가 5인 가장 긴 공통 부분 수열을 갖습니다.
간단히 말해서 DP 방식에서 DP 방식으로 각 작업을 한 번만 계산하면 됩니다. 재귀적 방법에서는 하위 문제가 중복될 수 있습니다.
이 동적 프로그래밍 알고리즘에서는 2D 행렬을 사용합니다. 두 개의 문자열이 제공됩니다(둘 다 길이가 n이라고 가정). 그러면 배열에 필요한 공간은 nx n입니다. 문자열이 충분히 크면 DP 솔루션의 메모리 최적화 버전이 필요합니다.
코드에서 사용된 단순화된 논리는 다음과 같습니다.
- 2D 배열 DP[m][n]을 선언합니다.
- DP 배열의 첫 번째 행과 첫 번째 열을 0으로 채웁니다.
- 반복을 위해 i와 j를 사용합니다.
- 패턴1[i]가 패턴2[j]와 같으면 DP[i][j] = DP[i-1][j-1] + 1을 업데이트합니다.
- 패턴1[i]가 패턴2[j]와 같지 않으면 DP[i][j]는 DP[i-1][j]와 DP[i][j-1] 사이의 최대값이 됩니다.
- i와 j가 m과 n에 도달할 때까지 계속합니다.
- 마지막 요소 또는 DP[m-1][n-1]에는 길이가 포함됩니다.
여기서는 배열 인덱스가 1부터 시작하므로 DP[m-1][n-0]로 처리됩니다.
요약
- DP 방법은 시간 복잡도가 낮습니다. O(mn)이고, 여기서 m과 n은 입력 문자열이나 배열의 길이입니다.
- DP는 재귀적 방법보다 더 빠른 접근 방식이며 시간 복잡도는 다음과 같습니다. O(n*2m).
- 동적 프로그래밍(DP)은 메모리 최적화가 아닙니다. 우리는 길이가 m*n인 2D 배열을 사용했습니다. 따라서 공간 복잡도는 (m*n)입니다.
- 재귀적 방법은 최악의 경우에 차지하는 최대 메모리는 m+n, 즉 기본적으로 입력된 문자열의 전체 길이가 됩니다.
- 오늘날의 최신 컴퓨터는 이 정도의 메모리를 처리하기에 충분합니다.
