[백준/Python] 9251 LCS

[백준/Python] 9251 LCS

정답 코드 및 설명

정답 전체 코드

A_string = input().rstrip()
B_string = input().rstrip()

LCS = [[0] * (len(B_string) + 1) for _ in range(len(A_string) + 1)]

for i in range(1, len(A_string) + 1):
    for j in range(1, len(B_string) + 1):
        if A_string[i-1] == B_string[j-1]:
            LCS[i][j] = LCS[i-1][j-1] + 1
        else:
            LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])

print(LCS[-1][-1])

문제 설명

위 문제는 LCS, Longest Common Subsequence 최장 공통 부분 수열을 찾는 문제이다.

두 문자열, 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예시로써

ACAYKP 와 CAPCAK 의 LCS 는 ACAK 가 된다.

코드 설명

1. 먼저, 문자열 두 개를 A, B 로써 입력 받는다.

LCS 배열을 하나 만들어 초기화한다. 이 배열의 크기는 A와 B 문자열 길이에 각각 한 칸 더 늘어난 크기로 설정한다.

그 이유는 LCS 를 찾기 위해서 현재 A문자열에서 선택된 문자와 B문자열에서 선택된 문자를 비교할 텐데 부분 수열은 연속된 값이 아니고 이전 값이 유지되기 때문에 이전 값과 비교하기 위해서 한 칸을 늘려준다.

LCS 에 대한 자세한 설명은 아래 링크를 참고했다. 그림으로 자세히 설명이 되어있어 도움이 되었다.

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

2. 이후 A문자열 과 B문자열의 각 문자 하나하나 씩 비교하는 이중 for 문을 통해 검사한다.

두 문자가 다르면 LCS[i-1][j] 와 LCS[i][j-1] 둘 중 큰 값을 선택한다.

두 문자가 같다면 LCS[i][j] = LCS[i-1][j-1] + 1 이 된다.

3. 최장 공통 부분 수열의 크기를 출력한다.

최장 공통 부분 수열의 크기는 LCS 배열에서 가장 큰 값이 된다.