최장 공통 부분 수열 (Longest Common Subsequence, LCS)

최장 공통 부분 수열 (LCS) 문제는 두 개의 문자열이 주어졌을 때, 두 문자열에서 순서를 유지하며 공통으로 나타나는 가장 긴 부분 수열을 찾는 문제이다. 부분 수열(subsequence)은 원래 문자열에서 순서를 유지하면서 일부 문자를 선택하여 만든 새로운 문자열이며, 문자가 반드시 연속할 필요는 없다.

예시

두 문자열 A = "ABCBDAB"와 B = "BDCAB"가 주어졌을 때:

• A에서 "BCAB"가 B에서의 "BCAB"와 일치한다.
• 이때 최장 공통 부분 수열은 "BCAB"이며, 그 길이는 4이다.

LCS 문제의 이론적 배경

LCS 문제는 다음과 같은 특성을 가지고 있다:

1. 최적 부분 구조 (Optimal Substructure):
   • 문제의 최적 해가 그 하위 문제의 최적 해로 구성될 수 있는 성질이다. 즉, 두 문자열에서 공통 부분 수열을 찾을 때, 그 수열은 하위 문자열에서의 공통 부분 수열로 구성된다.
2. 중복되는 하위 문제 (Overlapping Subproblems):
   • LCS 문제를 해결할 때 동일한 부분 문제를 여러 번 해결하는 일이 자주 발생한다. 예를 들어, 첫 번째 문자를 비교할 때 남은 부분에 대해 동일한 문제를 반복하게 된다. 이러한 중복 계산을 동적 프로그래밍(Dynamic Programming) 기법을 통해 효율적으로 처리할 수 있다.

LCS 문제를 동적 프로그래밍으로 해결하는 방법

동적 프로그래밍(DP)을 사용하여 최장 공통 부분 수열 문제를 효율적으로 해결할 수 있다. 이때 중요한 점은 하위 문제의 결과를 메모이제이션(Memoization)하거나, 테이블에 저장(Tabulation)하는 방식으로 중복된 계산을 피하는 것이다.

문제를 작은 하위 문제로 분할하기

두 문자열 A와 B가 있을 때, 두 문자열에서 최장 공통 부분 수열의 길이를 구하는 방법은 각 문자를 비교하여 다음과 같이 나눌 수 있다:

• 두 문자가 같은 경우: A[i] == B[j]
  • 두 문자열의 마지막 문자가 같다면, 그 문자는 최장 공통 부분 수열의 일부가 된다. 이때 두 문자를 제외한 하위 문자열들에서 최장 공통 부분 수열을 찾으면 된다.
  • 즉, LCS(i, j) = LCS(i-1, j-1) + 1입니다.
• 두 문자가 다른 경우: A[i] != B[j]
  • 두 문자열의 마지막 문자가 다르다면, 두 가지 선택이 있다:
    1. 문자열 A의 마지막 문자를 제외하고 LCS(i-1, j)를 계산한다.
    2. 문자열 B의 마지막 문자를 제외하고 LCS(i, j-1)을 계산한다.
  • 두 값 중 더 큰 값이 최장 공통 부분 수열이 된다.
  • 즉, LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1))이다.

동적 프로그래밍 테이블 (DP 테이블) 정의

• dp[i][j]: 문자열 A[0..i-1]과 B[0..j-1]의 최장 공통 부분 수열(LCS)의 길이를 저장한다.
  • dp[0][j] = 0: 문자열 A가 빈 문자열이면 LCS는 항상 0이다.
  • dp[i][0] = 0: 문자열 B가 빈 문자열이면 LCS는 항상 0이다.

점화식:

• A[i-1] == B[j-1]:
  • dp[i][j] = dp[i-1][j-1] + 1
• A[i-1] != B[j-1]:
  • dp[i][j] = max(dp[i-1][j], dp[i][j-1])

LCS 문제를 푸는 동적 프로그래밍 알고리즘

다음은 동적 프로그래밍을 사용해 LCS 문제를 해결하는 알고리즘이다.

동적 프로그래밍을 이용한 LCS 구현

def lcs(A, B):
    n, m = len(A), len(B)
    # DP 테이블 초기화 (0으로 채움)
    dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

    # DP 테이블 채우기
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if A[i - 1] == B[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1  # 두 문자가 같으면 1 증가
            else:  # 그렇지 않으면 이전 최댓값 유지
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[n][m]  # 최종적으로 dp[n][m]이 LCS의 길이를 저장

# 테스트
A = "ABCBDAB"
B = "BDCAB"
print(lcs(A, B))  # Output: 4 ("BDAB")

알고리즘 설명:

1. DP 테이블 초기화: dp[i][j]는 문자열 A[0..i-1]과 B[0..j-1]의 LCS 길이를 저장한다.
   • 테이블의 크기는 (n+1) x (m+1)로, 모든 값을 0으로 초기화한다.
2. 문자 비교 및 테이블 채우기:
   • 두 문자를 비교하면서 테이블을 채워나간다.
   • A[i-1] == B[j-1]이면, 현재 위치의 값은 대각선 값에서 1을 더한 값이다.
   • 그렇지 않으면, 상단 또는 왼쪽 값 중 더 큰 값을 현재 위치에 넣는다.
3. 결과 반환: 최종적으로 dp[n][m]에 LCS의 길이가 저장된다.

LCS 문제의 시간 복잡도

• 시간 복잡도: O(n * m)
• → 두 문자열의 길이가 각각 n과 m일 때, 각각의 하위 문자열 쌍에 대해 값을 계산해야 하므로 이중 루프가 필요하다.
• 공간 복잡도: O(n * m)
• → DP 테이블을 저장하는 데 n x m의 공간이 필요하다. 이 공간 복잡도는 문제에 따라 최적화할 수 있다. (1차원 배열을 사용하는 방식으로 공간 복잡도를 O(min(n, m))으로 줄일 수 있다.)

LCS 문제의 추가 사항

LCS 값 추적

위의 알고리즘에서는 최장 공통 부분 수열의 길이만을 구한다. 실제로 LCS 자체를 구하려면, 계산된 DP 테이블을 역추적해야 한다. 두 문자열이 같은 부분이 나왔을 때 그 문자를 기록하고, 테이블을 따라가면서 공통 부분 수열을 완성할 수 있다.

def lcs(A, B):
    n, m = len(A), len(B)
    dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

    # DP 테이블 채우기
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if A[i - 1] == B[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # 최장 공통 부분 수열 추적
    lcs_string = []
    i, j = n, m
    while i > 0 and j > 0:
        if A[i - 1] == B[j - 1]:
            lcs_string.append(A[i - 1])  # 공통 문자 찾음
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return "".join(reversed(lcs_string))  # 역추적 결과를 뒤집어서 반환

# 테스트
A = "ABCBDAB"
B = "BDCAB"
print(lcs(A, B))  # Output: "BDAB"

1. LCS(최장 공통 부분 수열) 문제는 두 문자열 사이에서 순서를 유지하면서 공통으로 나타나는 가장 긴 부분 수열을 찾는 문제이다.
2. 동적 프로그래밍(DP)을 사용해 LCS 문제를 해결하며, 2차원 테이블(dp 테이블)을 이용하여 부분 문제를 해결하고, 그 결과를 재사용한다.
3. 점화식을 기반으로 테이블을 채운 후, 그 값을 통해 최장 공통 부분 수열의 길이 또는 수열 자체를 역추적하여 구할 수 있다.
4. LCS의 시간 복잡도는 O(n * m)이며, 공간 복잡도도 동일하지만, 최적화를 통해 공간 복잡도를 줄일 수 있다.

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms