5-7. DP: LCS (최장 공통 부분 수열)

1. 최장 공통 부분 수열 (LCS)의 이해

최장 공통 부분 수열 (Longest Common Subsequence, LCS) 문제는 두 개의 주어진 수열에서 공통으로 나타나는 부분 수열 중 가장 긴 것의 길이를 찾는 문제입니다. 여기서 '부분 수열'이란, 원래 수열에서 순서를 유지하면서 일부 또는 전부의 원소를 선택하여 만든 수열을 의미합니다. 즉, 부분 수열은 연속될 필요는 없지만, 원래 수열에서의 상대적인 순서는 보존되어야 합니다.

예시:

수열 A = "ABCBDAB" 와 수열 B = "BDCAB" 가 주어졌을 때, LCS는 "BCAB" 가 됩니다. 이 LCS의 길이는 4입니다.

LCS 문제는 컴퓨터 과학, 특히 생물 정보학 (DNA 시퀀스 비교), 버전 관리 시스템 (파일 변경 사항 비교), 데이터 압축 등 다양한 분야에서 활용됩니다. 두 문자열 간의 유사성을 측정하는 데 사용될 수 있으며, 이를 통해 정보 검색, 텍스트 편집, 코드 diff 등의 기능을 구현할 수 있습니다.

1) 부분 수열 vs. 부분 문자열

LCS를 이해하기 위해서는 '부분 수열'과 '부분 문자열'의 차이점을 명확히 알아야 합니다.

• 부분 문자열 (Substring): 원래 문자열에서 연속된 일련의 문자들로 구성됩니다. 예를 들어, "ABC"에서 부분 문자열은 "AB", "BC", "ABC", "A", "B", "C" 등이 있습니다.
• 부분 수열 (Subsequence): 원래 문자열에서 순서를 유지하면서, 연속되지 않은 문자들을 포함할 수 있습니다. 예를 들어, "ABC"에서 부분 수열은 "AB", "AC", "BC", "A", "B", "C", "ABC" 등이 있습니다. "BAC"는 순서가 다르므로 부분 수열이 아닙니다.

LCS는 부분 수열을 찾는 문제이므로, 부분 문자열과는 다른 점에 유의해야 합니다.

2. 동적 프로그래밍 (DP)을 이용한 LCS 해결

LCS 문제는 동적 프로그래밍 (Dynamic Programming, DP)을 사용하여 효율적으로 해결할 수 있습니다. DP는 큰 문제를 작은 하위 문제로 나누어 해결하고, 하위 문제의 해결 결과를 저장하여 중복 계산을 피하는 알고리즘 설계 기법입니다. LCS 문제에 DP를 적용하면 중복되는 하위 문제들을 효율적으로 해결하여 시간 복잡도를 줄일 수 있습니다.

1) DP 테이블 정의

LCS 문제를 해결하기 위해 2차원 배열, 즉 DP 테이블을 사용합니다. dp[i][j]는 첫 번째 수열 A의 i번째 문자까지와 두 번째 수열 B의 j번째 문자까지의 LCS 길이를 저장합니다.

2) 점화식 유도

DP 테이블을 채우기 위한 점화식은 다음과 같습니다. A를 m개의 문자, B를 n개의 문자로 이루어진 수열이라고 가정합니다.

• 기저 조건:

  • dp[i][0] = 0 (0 <= i <= m): A의 i번째 문자까지와 B의 0개 문자 (빈 문자열)까지의 LCS 길이는 0
  • dp[0][j] = 0 (0 <= j <= n): A의 0개 문자 (빈 문자열)까지와 B의 j번째 문자까지의 LCS 길이는 0
  • 일반적인 경우:
  • if A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] + 1 (두 문자가 같으면, LCS 길이는 이전 LCS 길이에 1을 더함)
  • else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (두 문자가 다르면, A[i-1]을 제외한 LCS 길이와 B[j-1]을 제외한 LCS 길이 중 큰 값을 선택)

3) DP 테이블 채우기

점화식을 사용하여 DP 테이블을 채워나가는 과정은 다음과 같습니다.

1. 기저 조건을 초기화합니다. dp[i][0]과 dp[0][j]를 모두 0으로 설정합니다.
2. i와 j를 1부터 m과 n까지 반복하면서, 점화식에 따라 dp[i][j] 값을 계산합니다.

예를 들어, A = "ABCBDAB", B = "BDCAB"의 경우, DP 테이블은 다음과 같이 채워집니다.

최종적으로 dp[m][n]에는 LCS의 길이가 저장됩니다. 이 경우, dp[7][5]는 4가 됩니다.

3. LCS 알고리즘 구현 (Python)

def longest_common_subsequence(A, B):
    m = len(A)
    n = len(B)

    # DP 테이블 초기화
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # DP 테이블 채우기
    for i in range(1, m + 1):
        for j in range(1, n + 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 길이 반환
    return dp[m][n]

# 예시 사용
A = "ABCBDAB"
B = "BDCAB"
lcs_length = longest_common_subsequence(A, B)
print(f"LCS 길이: {lcs_length}")  # 출력: LCS 길이: 4

4. 시간 복잡도 분석

LCS 알고리즘의 시간 복잡도는 $O(m \times n)$입니다. 여기서 m과 n은 각각 두 수열의 길이입니다. 이는 DP 테이블을 채우기 위해 이중 루프를 사용하기 때문입니다. 공간 복잡도 또한 $O(m \times n)$이며, 이는 DP 테이블의 크기 때문입니다.

1) 시간 복잡도 개선 가능성

공간 복잡도를 $O(\min(m, n))$으로 줄이는 방법이 존재합니다. 이는 현재 행 또는 열의 값만 사용하여 이전 행 또는 열의 값을 덮어쓰는 방식으로 구현할 수 있습니다. 하지만, LCS 자체를 복원하는 것은 어려워집니다. LCS의 길이를 구하는 데 집중한다면 공간 효율성을 높일 수 있습니다.

5. LCS 응용 및 활용 사례

1) 텍스트 비교

LCS는 두 텍스트 간의 유사성을 측정하는 데 사용될 수 있습니다. 텍스트 편집기에서 변경 사항을 하이라이트하거나, 두 문서 간의 차이점을 파악하는 데 활용될 수 있습니다.

2) DNA 시퀀스 비교

생물 정보학에서 DNA 시퀀스 간의 유사성을 분석하는 데 사용됩니다. LCS를 통해 DNA 서열의 유사성을 파악하고, 진화적 관계를 추론하거나, 유전자 변이를 감지할 수 있습니다.

3) 버전 관리 시스템

Git과 같은 버전 관리 시스템에서 파일의 변경 사항을 비교하고, 병합 (merge)을 수행하는 데 사용됩니다. LCS를 사용하여 파일의 공통 부분을 찾고, 변경된 부분을 식별하여 효율적인 버전 관리를 가능하게 합니다.

6. 주의 사항 및 트러블 슈팅

1) 메모리 제한

입력 수열의 길이가 매우 긴 경우, DP 테이블의 크기가 커져 메모리 제한에 걸릴 수 있습니다. 이러한 경우, 공간 복잡도를 줄이는 최적화 기법을 고려해야 합니다.

2) LCS 복원

LCS의 길이뿐만 아니라 LCS 자체를 구해야 하는 경우, DP 테이블을 채우는 과정에서 추가 정보를 저장해야 합니다. 일반적으로, 각 dp[i][j] 셀에서 LCS가 어떻게 구성되었는지를 나타내는 정보를 저장합니다 (예: 이전 셀의 위치). 역추적을 통해 LCS를 복원할 수 있습니다.

3) 입력 데이터 검증

입력 데이터가 유효한지 확인해야 합니다. 예를 들어, 입력 수열이 빈 문자열인지, 또는 예상되는 형식인지 확인합니다.

4) 재귀적 구현 vs. 반복적 구현

LCS는 재귀적 방식과 반복적 방식으로 모두 구현 가능합니다. 재귀적 구현은 코드가 간결하지만, 중복 계산이 발생하여 비효율적일 수 있습니다. 반복적 구현은 DP 테이블을 사용하여 효율적인 해결책을 제공합니다.

7. 결론

LCS는 두 수열 간의 유사성을 파악하는 강력한 도구입니다. 동적 프로그래밍을 사용하여 효율적으로 해결할 수 있으며, 텍스트 비교, DNA 시퀀스 분석, 버전 관리 등 다양한 분야에서 응용됩니다. LCS 알고리즘의 원리를 이해하고, DP 테이블을 활용하여 문제를 해결하는 능력을 키우는 것은 알고리즘 및 데이터 구조 학습의 중요한 부분입니다.