백준 5582번 공통 부분 문자열 - C++ 풀이
1. dp(p, q) = S[p...]와 T[q...]가 앞에서부터 일치하는 최대 글자 수 2. S[p] = T[q]인 경우 dp(p, q) = 1 + dp(p+1, q+1)이고, 아닌 경우 0이다. 3. dp(p, q)의 최댓값이 최장 공통부분 문자열의 길이이다. 1. dp(p, q) = S[p...]와 T[q...]가 앞에서부터 일치하는 최대 글자 수 dp(p, q)를 위와 같이 정의하자. 2. S[p] = T[q]인 경우 dp(p, q) = 1 + dp(p+1, q+1)이고, 아닌 경우 0이다. S[p] = T[q]인 경우, 그다음 글자를 비교해야 하므로 dp(p, q) = 1 + dp(p+1, q+1)이 된다. dp(p, q)는 "앞에서부터" 일치하는 최대 글자 수이므로, S[p] != T[q]인..
2022. 8. 4.
백준 1958번 LCS 3 - C++ 풀이
1. dp(a, b, c): A[a...], B[b...], C[c...]의 LCS 길이 2. 만약 A[a] = B[b] = C[c]이면, dp(a, b, c) = 1 + dp(a+1, b+1, c+1) 3. 아니라면, dp(a, b, c) = max(dp(a+1, b, c), dp(a, b+1, c), dp(a, b, c+1)) 1. dp(a, b, c): A[a...], B[b...], C[c...]의 LCS 길이 세 문자열을 각각 A, B, C라고 하고 dp(a, b, c)를 위와 같이 정의하자. 2. 만약 A[a] = B[b] = C[c]이면, dp(a, b, c) = 1 + dp(a+1, b+1, c+1) 문자열 2개일 때 LCS와 똑같은 방식으로 점화식을 세우면 된다. 세 문자열의 첫 글자가 ..
2022. 7. 26.
