[BOJ] 9252 – LCS 2

아이디어

동적 프로그래밍은 두 문자열의 가장 긴 공통 하위 문자열을 찾습니다.

설명

두 문자열은 각각 S1과 S2에 저장되고 길이는 각각 N1과 N2에 저장됩니다.

편리한 인덱스 액세스를 위해 여백이 1인 빈 문자열로 채워진 길이 N2+1의 목록 dp를 만듭니다.

메모리를 절약하기 위해 dp는 2차원 리스트로 변환하지 않고 현재 행을 lcs에서 처리하고 dp를 대체합니다.

S1의 i번째 문자와 S2의 j번째 문자의 가장 긴 공통 부분 시퀀스는 lcs(i+1)(j+1)에 저장됩니다.

S1과 S2의 문자가 같으면 이전 문자까지 공통 부분이 가장 긴 열에 해당 문자를 더한 문자열이 저장된다.

그렇지 않으면 더 긴 하위 체인의 체인이 이전에 저장된 하위 체인에 저장됩니다.

def solution():
    S1, S2 = input(), input()
    N1, N2 = map(len, (S1, S2))
    dp = ('')*(N2+1)
    for i in range(N1):
        lcs = ('')*(N2+1)
        for j in range(N2):
            if S1(i) == S2(j):
                lcs(j+1) = dp(j)+S1(i)
            else:
                if len(dp(j+1)) > len(lcs(j)):
                    lcs(j+1) = dp(j+1)
                else:
                    lcs(j+1) = lcs(j)
        dp = lcs
    print(len(dp(-1)))
    if dp(-1):
        print(dp(-1))

solution()

DP 2차원 목록으로 내가 사용한 코드에서 메모리 사용량은 약 13.1배, 시간은 약 2.4배 증가했습니다.

dp = (('')*(N2+1) for _ in range(N1+1))
for i in range(N1):
    for j in range(N2):
        if S1(i) == S2(j):
            dp(i+1)(j+1) = dp(i)(j)+S1(i)
        else:
            if len(dp(i)(j+1)) > len(dp(i+1)(j)):
                dp(i+1)(j+1) = dp(i)(j+1)
            else:
                dp(i+1)(j+1) = dp(i+1)(j)