[Baekjoon] 1958번 : LCS 3 (Python, 문자열, DP)

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

Contribute to stellaluminary/Baekjoon development by creating an account on GitHub.

github.com

Python

방법 1 - 메모리 37964KB / 시간 880ms / 코드 길이 472B

3단 dp에 대하여 memorization을 적용한 케이스

LCS에 대한 알고리즘 설명 웹 사이트

https://www.programiz.com/dsa/longest-common-subsequence

Longest Common Subsequence

Longest Common Subsequence In this tutorial, you will learn how the longest common subsequence is found. Also, you will find working examples of the longest common subsequence in C, C++, Java and Python. The longest common subsequence (LCS) is defined as t

www.programiz.com

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

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

LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다.

velog.io

l = [input() for _ in range(3)]
l.sort(key=len)
w1,w2,w3 = l
l1,l2,l3 = len(w1), len(w2), len(w3)

dp = [[[0]*(l1+1) for _ in range(l2+1)] for _ in range(l3+1)]

for k in range(1, l3 + 1):
    for j in range(1, l2 + 1):
        for i in range(1, l1 + 1):
            if w1[i-1] == w2[j-1] == w3[k-1]:
                dp[k][j][i] = dp[k-1][j-1][i-1] + 1
            else:
                dp[k][j][i] = max(dp[k-1][j][i], dp[k][j-1][i], dp[k][j][i-1])

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