[백준] 9252 LCS 2 Python 3

두 문자열 간의 최장 공통 부분 수열(Longest Common Subsequence, LCS)을 찾는 파이썬 코드를 작성해 보겠습니다. 이 문제는 DP(동적 프로그래밍)를 이용하여 해결할 수 있습니다

문제 설명

LCS(Longest Common Subsequence)는 두 문자열이 주어졌을 때, 두 문자열 모두에 부분 수열이 되는 문자열 중 가장 긴 문자열을 찾는 문제입니다. 예를 들어, 문자열 "ACAYKP"와 "CAPCAK"의 LCS는 "ACAK"입니다.

접근 방식

LCS 문제를 해결하기 위해 다음과 같은 동적 프로그래밍 접근 방식을 사용할 수 있습니다:

1. 두 문자열 A와 B의 길이를 측정합니다.
2. 각 부분 문자열의 LCS 길이를 저장할 DP 테이블을 만듭니다.
3. 두 문자열을 순회하며 DP 테이블을 채웁니다.
4. DP 테이블을 사용하여 최장 공통 부분 수열을 추출합니다.

코드 구현

def print_lcs(dp, A, B, x, y):
    # 주어진 DP 테이블을 기반으로 LCS를 추출하는 함수
    lcs = []
    while x > 0 and y > 0:
        if A[x - 1] == B[y - 1]:
            # 현재 위치의 문자가 같다면 LCS에 추가
            lcs.append(A[x - 1])
            x -= 1
            y -= 1
        elif dp[x - 1][y] > dp[x][y - 1]:
            # 위쪽이 더 크다면 위쪽으로 이동
            x -= 1
        else:
            # 왼쪽이 더 크다면 왼쪽으로 이동
            y -= 1
    # LCS는 역순으로 추출되었으므로 뒤집어서 반환
    return ''.join(reversed(lcs))

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    A = data[0]
    B = data[1]

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

    ans = 0  # LCS의 길이
    a = b = 0  # LCS의 끝나는 위치

    # DP 테이블 채우기
    for i in range(len(A)):
        for j in range(len(B)):
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])  # 위쪽, 왼쪽 값 중 큰 값 선택
            if A[i] == B[j]:
                # 현재 문자가 같다면 대각선 위에서 +1
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)

            if ans < dp[i + 1][j + 1]:
                # 현재까지 찾은 LCS의 길이 갱신
                ans = dp[i + 1][j + 1]
                a = i + 1
                b = j + 1

    if ans == 0:
        # LCS가 없을 경우
        print("0")
    else:
        # LCS의 길이와 LCS 문자열 출력
        print(ans)
        print(print_lcs(dp, A, B, a, b))

if __name__ == "__main__":
    main()

코드 설명

1. print_lcs 함수: 이 함수는 DP 테이블을 기반으로 최장 공통 부분 수열을 생성합니다.
   • 문자열 A와 B의 마지막 문자부터 시작하여, 두 문자가 같으면 해당 문자를 결과 리스트에 추가하고, 그렇지 않으면 DP 테이블 값을 비교하여 더 큰 방향으로 이동합니다.
   • 최종적으로 LCS 문자열을 반환합니다.
2. main 함수: 이 함수는 입력을 처리하고 DP 테이블을 채우는 메인 함수입니다.
   • 문자열 A와 B를 입력받습니다.
   • DP 테이블을 초기화합니다.
   • 두 문자열을 순회하며 DP 테이블을 채웁니다.
   • LCS의 길이와 실제 문자열을 출력합니다.