[Baekjoon 9251 / python / 골드5] LCS

a = [[]]  # dp테이블과 인덱스를 동기화하기 위해 빈 리스트를 추가한다.

b = [[]]

for i in list(input()):

    a.append(i)

for i in list(input()):

    b.append(i)

# 0행과 0열 값을 모두 0으로 맞춰준다.

# 첫번째 비교부터 공식을 적용하려면 이전 값이 존재해야 하기 때문에 맞춰주는 것.

dp = [[0 for _ in range(len(a))] for _ in range(len(b))]

for x in range(1, len(b)):

    for y in range(1, len(a)):

        if b[x] == a[y] :  # 문자열이 일치할 경우

            dp[x][y] = dp[x-1][y-1] + 1  # 좌측위 방향 값에서 +1 더한 값

        else:  # 문자열이 일치하지 않으면

            dp[x][y] = max(dp[x][y-1], dp[x-1][y])  # 왼쪽, 위쪽 중 큰 값

print(dp[-1][-1])

 

유명한 다이나믹 프로그래밍 문제이다.

 

LCS는 Longest Common Substring/Subsequence 로써, 두 문자열의 공통 부분 문자열 중 길이가 가장 긴 문자열을 말한다. SubString과 Subsequence 모두 LCS라고 칭하지만, 이 문제에서는 Subsequence를 구해야 한다.

 

Subsequence : 전체 문자열에서 "꼭 연속된 문자열인 것은 아닌" 부분 문자열

ex) ABCDEFGHI 에서 Subsequence 는 ABD, AEFGH, AFI, … 등이 있다.

(단, 앞에서부터가 아니라 순서가 뒤바뀐 IHE, BIDEHF 와 같은 문자열은 부분 문자열이 될 수 없다)

 

공통 부분 문자열 중, “가장 길이가 긴” 부분 문자열을 찾는다.

ex) ABCDEF 와 ACDGHI 와의 공통 Subsequence 중 가장 길이가 긴 것은

ABCDEF / AZGCDGHI 에서 ACD 이다.

 

LCS를 찾으려면 아주 골치가 아프지만, 점화식만 알면 쉽게 풀 수 있다.

 

LCS 구하기

 

위 표는 문제에 제시된 예제의 LCS를 구하는 DP 테이블이다.

ACAYKP

CAPCAK

이 두 문자열의 LCS를 구하는 것이다.

 

행을 x, 열을 y라고 하자. ( C, A, P ,C, A, K가 각각 1, 2, 3, 4, 5, 6 행 )

여기서 dp[x][y]를 구하는 기준은 이렇다.

1. 두 문자열이 일치하지 않는다면, [x-1][y], [x][y-1] (위쪽, 왼쪽) 중 더 큰 값을 입력한다.

2. 두 문자열이 일치한다면, [x-1][y-1] (좌측 위 대각선) 값에서 +1한 값을 입력한다.

# 첫번째 줄부터 점화식을 적용하기 위해, dp테이블 0행 0열은 모두 0으로 채워 놓는다.

 

생각보다 규칙은 어렵지 않다. 다만 이 규칙을 어떻게 찾아내느냐가 문제이겠지만...

쉽게 말하면 문자열이 일치하면 왼쪽 위칸 값에서 +1 하면 되고, 일치하지 않으면 왼쪽이나 위쪽 값 중 큰 값을 쓰면 된다.

 

표를 보면 이 규칙이 아주 적절히 적용되어 있는 것을 알 수 있다.