가장 긴 공통 부분 수열: Python, C++ 예시

가장 긴 공통 부분 수열은 무엇입니까?

최장 공통 부분 수열(LCS)이란 두 개의 문자열, 패턴 또는 객체 시퀀스가 ​​주어졌을 때, 두 시퀀스 또는 문자열 모두에 동일한 순서로 존재하는 요소들로 이루어진 가장 긴 부분 수열을 찾는 것을 의미합니다.

예시

예를 들어, 두 개의 문자열이 주어졌습니다. 다음과 같다고 가정해 보겠습니다.

Pattern_1 = "RGBGARGA"
Pattern_2 = "BGRARG"

• pattern_1로부터 "RGB", "RGGA", "RGAR"와 같은 시퀀스를 생성할 수 있습니다. 시퀀스를 생성하려면 문자열 내 각 문자의 상대적 위치를 유지해야 합니다.
• pattern_2로부터 "BGR", "BRAG", "RARG"와 같은 시퀀스를 생성할 수 있습니다. 시퀀스는 원래 문자열의 상대적 위치를 유지하는 한 생성 가능합니다.

상대 위치라는 용어는 순서를 의미합니다.

예를 들어, "BRG"는 유효한 시퀀스입니다. 왜냐하면 원래 문자열 패턴_2에서 "B"가 먼저 나오고, 그 다음 "R", 마지막으로 "G"가 나오기 때문입니다. 하지만 "RBRG"는 유효하지 않은 시퀀스입니다. 왜냐하면 원래 문자열(패턴_2)에서 "B"가 먼저 나오기 때문입니다.

주어진 두 시퀀스 또는 배열에서 가장 긴 공통 부분 시퀀스를 찾는 두 가지 옵션이 있습니다.

• 순진한 방법
• 동적 프로그래밍 솔루션: 가장 긴 공통 부분 시퀀스는 LCS라고도 합니다.

단순한 해법은 시간 복잡도가 높고 최적의 해법이 아닙니다. 동적 프로그래밍(DP) 해법을 사용하면 이러한 복잡도 문제를 해결할 수 있습니다.

순진한 방법

단순 접근법은 시간 복잡도 및 기타 최적화 요소를 고려하지 않고 문제를 해결하는 가장 간단한 방법입니다. 대부분의 경우 무차별 대입 방식, 여러 개의 반복문, 재귀 호출로 구성됩니다. 무차별 대입이란 주어진 문제에 대해 가능한 모든 패턴을 시도하는 것을 의미합니다.

예시

위의 패턴1과 패턴2의 예에서 패턴1의 길이가 m이고 패턴2의 길이가 n이라고 가정해 보겠습니다. 가능한 모든 사례를 확인하려면 패턴1과 패턴2의 가능한 모든 하위 시퀀스를 평가해야 합니다.

다음은 간단한 4글자 문자열 "ABCD"입니다. 예를 들어, "ABCD"에서 순열을 만들어야 합니다. 각 문자를 사용할 수도 있고 사용하지 않을 수도 있습니다. 즉, 각 문자에 대해 두 가지 선택지가 있습니다.

• 캐릭터가 하위 시퀀스에 추가됩니다.
• 해당 문자는 하위 시퀀스에 추가되지 않습니다.

여기서 이미지는 "ABCD"라는 문자열로 만들 수 있는 모든 시퀀스를 보여줍니다.

문자가 1개인 시퀀스:

2개의 문자로 구성된 시퀀스:

3개의 문자로 구성된 시퀀스:

위 그림에서 14개의 순열이 있습니다. 만약 문자를 전혀 사용하지 않고 빈 문자열을 만들면 총 순열은 15개가 됩니다. 또한, "ABCD"라는 문자열 자체도 하나의 순열이므로 총 순열은 16개입니다.

따라서 "ABCD"에서 2^4 또는 16개의 부분 수열을 생성할 수 있습니다. 그러면 길이가 다음과 같은 문자열이 생성됩니다. m 총 부분 수열은 2^m이 될 것입니다.

각 부분 시퀀스에 대해 전체 패턴2에 대해 확인해야 합니다. 이는 O(n) 시간이 걸립니다. O(n)은 실행에 걸리는 시간을 계산하는 복잡도 함수를 의미합니다.

따라서 총 시간 복잡도는 다음과 같습니다. O(n*2^m). 위에서 살펴본 예시의 경우, m=8이고 n=5입니다.

Naive Method의 단계는 다음과 같습니다.

단계 1) 패턴1에서 시퀀스를 가져옵니다.
단계 2) 1단계의 순서와 2번 패턴을 일치시키세요.
단계 3) 일치하면 하위 시퀀스를 저장합니다.
단계 4) 패턴1에 더 많은 시퀀스가 ​​남아 있으면 1단계로 다시 돌아갑니다.
단계 5) 가장 긴 하위 시퀀스를 인쇄합니다.

최적의 하부 구조

최적 부분 구조라는 용어는 부분 문제를 해결함으로써 최적해를 찾을 수 있음을 의미합니다. 예를 들어, 위 예시에는 패턴1과 패턴2가 있습니다.

단계 1) 각 패턴에서 처음 두 문자를 가져오세요.

단계 2) 각 패턴에서 세 번째부터 다섯 번째 문자를 가져옵니다.

단계 3) 나머지 문자들에 대해서도 비슷하게 계속하십시오.

LCS 문제의 재귀적 구조

우리는 부분 문자열(원본 문자열에서 생성된 문자열)의 최장 공통 부분 문자열(LCS)을 찾습니다. 그런 다음 부분 문자열의 LCS 길이를 기록해 둡니다.

이제 또 다른 흥미로운 속성이 있습니다. 중첩하다ping 하위 문제어떤 문제는 중복된다고 합니다.ping 문제 설명을 작은 하위 문제로 나누어 프로그램에서 여러 번 사용할 수 있는 경우 하위 문제라고 합니다.

아래 다이어그램은 재귀 알고리즘이 동일한 매개변수를 사용하여 함수를 여러 번 호출한 것을 보여줍니다.

예를 들어 재귀 트리를 살펴보세요. 어두운 색 상자 안에서 겹치는 부분을 확인할 수 있습니다.ping 하위 문제들. ("RG", "RA"), ("RG", "R") 등이 여러 번 호출됩니다.

이를 최적화하기 위해 다음과 같은 접근 방식을 사용합니다. 동적 프로그래밍 (DP).

최장공배수열의 재귀적 방법

위 그림은 재귀 메서드를 나타냅니다. 각 재귀 함수에는 재귀를 중단하거나 스택에서 반환을 시작하는 기준 사례(base case)가 있습니다.

이번 구현에서는 기본 사례를 사용하겠습니다. 따라서, 연산 다음과 같습니다:

• 마지막 요소 이전의 모든 요소에 일치하는 항목이 있으면 길이를 1만큼 늘리고 반환합니다.
• 함수에 두 개의 패턴을 전달하고, 반환 값 중 최댓값을 취합니다.
• 한 패턴의 길이가 0이면 비교할 하위 시퀀스가 ​​없습니다. 이 경우 XNUMX을 반환합니다. 이것이 재귀의 기본 사례입니다.

별명 Code:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
    if len_1 or len_2 is zero:
        return 0
    if pattern_1[len_1 - 1] equals 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))

에서 구현 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

에서 구현 Python

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("Length of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

출력:

Length of LCS is:  5

최장공약수열(LCS)의 동적 프로그래밍 방법

동적 프로그래밍은 일반적인 재귀 메서드를 최적화하는 것을 의미합니다. 예를 들어, 재귀 또는 단순 접근 방식의 그래프를 살펴보면 동일한 함수 호출이 여러 번 발생하는 것을 볼 수 있습니다. 동적 프로그래밍 방식은 모든 계산 결과를 배열에 저장하고 필요할 때 재사용합니다.

패턴1과 패턴2의 길이를 각각 m과 n이라고 할 때, mxn 크기의 2차원 배열을 사용하겠습니다. 2D 배열리스트 데이터 구조를 사용할 수 있습니다. Python 또는 벡터/배열 데이터 구조 C++.

별명 Code 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]

다음은 동적 프로그래밍 방식에서 2차원 배열 데이터 구조로 사용되는 LCS 테이블입니다.

여기서 사용한 논리에 대해 논의해 보겠습니다. 단계는 다음과 같습니다.

단계 1) 만약 i 또는 j가 0이면, 주어진 두 문자열에서 빈 문자열을 추출하여 공통 부분 문자열을 찾으려고 시도합니다. 하지만 추출하는 부분 문자열이 빈 문자열이므로, 부분 문자열의 길이는 0이 됩니다.

단계 2) 두 문자가 일치하면 이전에 계산된 LCS 값을 증가시켜 (i,j) 인덱스에 값을 할당합니다. 이 LCS 값은 이전 행의 (i-1,j-1) 인덱스에 있습니다.

단계 3) 일치하지 않으면 인접한 두 인덱스 중 최댓값(LCS)을 취합니다. 이런 식으로 2차원 배열의 모든 값을 채워야 합니다.

단계 4) 마지막으로 2D 배열의 마지막 셀 값을 반환합니다.

기본적으로 2차원 배열의 모든 값은 공통 부분 수열의 길이를 나타냅니다. 그중 마지막 셀에는 가장 긴 공통 부분 수열의 길이가 저장됩니다.

에서 구현 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 < n + 1; i++) {
    for (int j = 0; j < 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) 방식에서는 각 작업을 한 번씩만 계산합니다. 반면 재귀 방식에서는 작업이 중복될 수 있습니다.ping 하위 문제들.

이 동적 프로그래밍 알고리즘에서는 2D 행렬을 사용합니다. 두 개의 문자열이 제공됩니다(둘 다 길이가 n이라고 가정). 그러면 배열에 필요한 공간은 nx n입니다. 문자열이 충분히 크면 DP 솔루션의 메모리 최적화 버전이 필요합니다.

코드에서 사용된 단순화된 논리는 다음과 같습니다.

• 2D 배열 DP[m][n]을 선언합니다.
• DP 배열의 첫 번째 행과 첫 번째 열을 0으로 채웁니다.
• 반복을 위해 i와 j를 사용합니다.
• pattern1[i]가 pattern2[j]와 같으면 DP[i][j]를 DP[i-1][j-1] + 1로 업데이트합니다.
• pattern1[i]가 pattern2[j]와 같지 않으면 DP[i][j]는 DP[i-1][j]와 DP[i][j-1] 사이의 최댓값이 됩니다.
• i와 j가 m과 n에 도달할 때까지 계속합니다.
• 마지막 요소인 DP[m-1][n-1]에는 길이가 포함됩니다.

여기서는 배열 인덱스가 0부터 시작하기 때문에 DP[m-1][n-1]로 표시됩니다.

자주 묻는 질문