9251~2번: LCS

문제는 -> 링크

MIT 6.006 강의에서 LCS 를 배웠다.

SRTBOT 으로 문제를 분해해보자.

Subproblem

A = HABIT,
B = THEIR

이라고 가정할 때, subproblem L(i,j) 는:

$L(i,j)=LCS(A[i:],B[j:])$

이다. 가령 i=2, j=3 일 때, L(2,3) = LCS(BIT, IR) 이 되겠다.

Relate

# common sequence 가 있음
if A[i]==B[j]:

	return 1 + L(i+1,j+1)
    
# common sequence 가 없음, 둘중 하나는 LCS 가 아님
else:

	return max(L(j+1,i), L(j,i+1))

Topology

Suffix 로 접근했으니 오른쪽부터 왼쪽으로 키워나가자.

Base case

L(|A|,j) == L(i,|B|) == 0

Original problem

L(0,0) 을 구하고 싶다.

Time complexity

O(subproblem) * O(relate) = $\Theta(|A||B|)\times\Theta(1)$

Solution

import sys

A = sys.stdin.readline().strip()
B = sys.stdin.readline().strip()

L = [[0 for _ in range(len(B)+1)] for _ in range(len(A)+1)]

for i in reversed(range(len(A))):

    for j in reversed(range(len(B))):

        if i == len(A) or j == len(B):

            continue

        if A[i] == B[j]:

            L[i][j] = 1 + L[i+1][j+1]

        # common sequence 가 없음, 둘중 하나는 LCS 가 아님
        else:

            L[i][j] = max(L[i+1][j], L[i][j+1])


# print(*L, sep="\n")

print(L[0][0])

9212번도 똑같이 풀 수 있다. L[i][j] 에 string 자체를 저장하면 된다.

        if A[i] == B[j]:

            L[i][j] = A[i] + L[i+1][j+1]

        else:

			# 바로 max 를 못구하니 직접 비교하자.
            if len(L[i+1][j]) > len(L[i][j+1]):
                L[i][j] = L[i+1][j]

            else:
                L[i][j] = L[i][j+1]