파이썬 코딩테스트 강좌, 최장 공통 부분 수열 찾기

문제 설명

주어진 두 개의 문자열이 있을 때, 이 두 문자열의 최장 공통 부분 수열(Longest Common Subsequence, LCS)을 구하는 문제입니다. 공통 부분 수열이란 두 문자열에서 순서를 유지하면서 나타나는 공통 문자들을 나타냅니다. 길이가 최대인 경우를 찾는 것이 목표입니다.

예제

입력

문자열 A: ABCBDAB
문자열 B: BDCAB

출력

최장 공통 부분 수열: BDAB

문제 접근 방법

LCS 문제를 해결하기 위해서는 동적 프로그래밍(Dynamic Programming)을 사용할 수 있습니다. 동적 프로그래밍은 이미 계산한 결과를 저장해 두고, 이를 재사용하는 방식으로 문제를 해결하는 기법입니다. LCS를 구하기 위해서는 두 문자열의 각 문자 비교 결과를 통해 부분 수열의 길이를 저장해 나갑니다.

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

1단계: DP 테이블 초기화

두 문자열의 길이를 각각 m, n이라 할 때, 크기가 (m + 1) x (n + 1)인 2차원 DP 배열을 생성하고 초기화합니다. DP 배열의 각 원소는 두 문자열에서의 공통 부분 수열의 길이를 저장합니다.

2단계: DP 테이블 작성

두 문자열의 각 문자를 비교하면서 DP 테이블을 채워나갑니다. 만약 두 문자가 같다면, 그 문자를 포함한 LCS 길이는 DP[i-1][j-1] + 1입니다. 만약 다르다면, DP[i][j] = max(DP[i-1][j], DP[i][j-1])을 사용하여 현재까지 찾은 LCS 길이를 기록합니다.

3단계: LCS 길이와 문자열 추출

DP 테이블을 모두 채운 후, DP[m][n]을 확인하여 최장 공통 부분 수열의 길이를 얻고, 이를 통해 실제 공통 부분 수열을 추출합니다. 추출 과정은 테이블을 역으로 탐색하여 공통된 문자를 확인하는 방식으로 진행됩니다.

알고리즘 코드

    
def lcs(A, B):
    # 1단계: DP 배열 초기화
    m = len(A)
    n = len(B)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 2단계: 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])

    # 3단계: LCS 길이 얻기
    lcs_length = dp[m][n]

    # LCS 문자열 추출
    lcs_str = []
    i, j = m, n
    while i > 0 and j > 0:
        if A[i - 1] == B[j - 1]:
            lcs_str.append(A[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    lcs_str.reverse()  # 꺼낸 문자열을 뒤집어서 원래 순서로 복원
    return lcs_length, ''.join(lcs_str)

# 테스트 코드
A = "ABCBDAB"
B = "BDCAB"
length, lcs_string = lcs(A, B)
print("LCS 길이:", length)
print("LCS 문자열:", lcs_string)

복잡도 분석

이 알고리즘의 시간 복잡도는 O(m * n)입니다. 각 문자를 비교해야 하므로, 두 문자열의 길이에 따라 곱해진 결과가 나옵니다. 공간 복잡도 또한 O(m * n)이며, 생성된 DP 테이블의 크기에 의해 결정됩니다. 하지만 DP 테이블의 크기를 줄일 방법도 있습니다. 예를 들어, 이전 행의 데이터만 필요하기 때문에, 2개의 1차원 배열로 구현할 수도 있습니다.

최적화된 코드 예시

    
def optimized_lcs(A, B):
    m = len(A)
    n = len(B)
    dp = [0] * (n + 1)

    for i in range(1, m + 1):
        current = 0  # 현재 위치의 값
        for j in range(1, n + 1):
            temp = dp[j]
            if A[i - 1] == B[j - 1]:
                dp[j] = current + 1
            else:
                dp[j] = max(dp[j], dp[j - 1])
            current = temp  # 이전 행의 값을 저장

    return dp[n]

# 최적화된 테스트
length = optimized_lcs(A, B)
print("LCS 길이:", length)

결론

이번 강좌에서는 최장 공통 부분 수열(Longest Common Subsequence) 문제를 다루었습니다. 이 문제는 문자열 처리와 동적 프로그래밍 개념을 쉽게 활용할 수 있는 좋은 예제입니다. LCS 문제는 다양한 분야, 특히 유전자 분석과 동일한 서열 찾기 문제에서 많이 사용되므로, 알고리즘의 이해와 구현은 코딩 테스트나 실무에서 매우 유용합니다.