[백준 파이썬 9252번 LCS2] DP에 문자열을 넣어서 드셔보세요

9252번: LCS 2

 

 

문자열 전체를 DP에 저장해서 사용하는 아이디어가 참신했다

---

공간 복잡도 O(n)로 짠 코드

def lcs(seq, tar):
    dp = [''] * len(tar)  # 배열의 크기는 두 번째로 도는 iter의 크기로 해야한다 ->5번라인으로
    for i in range(len(seq)):
        max_dp = ''
        for j in range(len(tar)):  # 배열의 크기만큼 돈다
            if len(max_dp) < len(dp[j]):
                max_dp = dp[j]
            elif seq[i] == tar[j]:
                dp[j] = max_dp + tar[j]

    # 가장 큰 값 찾기
    ans = ''
    for s in dp:
        if len(ans) < len(s):
            ans = s
    print(len(ans))
    if len(ans):
        print(ans)


A, B = input(), input()
lcs(A, B)

# DP
> ['C', 'CA', 'CAP', 'AC', 'ACA', 'ACAK']

 

이 경우 DP의 마지막에 최대 크기가 들어간다는 보장이 없기 때문에 탐색을 한 번 해주어야 하는 것 같다.

---

공간 복잡도 O(n**2)로 짠 코드

seq = [""] + list(input().rstrip())
tar = [""] + list(input().rstrip())
LCS = [[""] * len(tar) for _ in range(len(seq))]

for i in range(1, len(seq)):
    for j in range(1, len(tar)):
        if seq[i] == tar[j]:
            LCS[i][j] = LCS[i-1][j-1] + seq[i]
        else:
            if len(LCS[i-1][j]) >= len(LCS[i][j-1]):
                LCS[i][j] = LCS[i-1][j]
            else:
                LCS[i][j] = LCS[i][j-1]

result = LCS[-1][-1]
print(len(result), result, sep="\n")

# DP
> ['', 'C', 'CA', 'CAP', 'CAP', 'ACA', 'ACAK']

 

??? : 똑똑한 청년.

 

[백준 9252 파이썬] LCS 2 (골드 4, DP)