문자열 3개의 가장 긴 공통 부분문자열(Longest Common Subsequence)구하기

1. 문제 1958번: LCS 3 (acmicpc.net) 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 2. 풀이 문자열 X[1,2,...,i]와 Y[1,2,..,j]와 Z[1,2,..,k]의 가장 긴 공통부분문자열을 dp[i][j][k]라고 하자. 그러면 2개의 문자열 LCS를 구할때와 동일한 방법으로 DP배열을 채울 수 있다 https://deepdata.tistory.com/1022 = 1 and dp[i][j] == dp[i][j-1]: j -= 1 elif dp[i][j] == dp[i-1][j]: i -= 1..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 10. 28.
• textsms

LCS(Longest Common Subsequence) 문제 다이나믹 프로그래밍 기본 해법 배우기

1. 문제 두 문자열 $X = x_{1}x_{2}x_{3}...x_{n}$와 $Y = y_{1}y_{2}y_{3}...y_{m}$이 주어진다. 여기서 $x_{i}$와 $y_{j}$는 하나의 문자를 나타낸다. 여기서 문자열의 부분문자열(Subsequence)은? "원래 문자열에서 순서를 유지한채로 문자 몇개를 제거한 문자열"로 정의한다. 예를 들어 'ABCBDAB'라고 한다면... ABC도 부분문자열이지만, ABBAB도 부분문자열이 된다. 가장 긴 공통 부분문자열(Longest Common Subsequence) 문제는 K개의 문자열이 주어질때, 모든 문자열의 공통 부분문자열 중에서 가장 긴 공통 부분문자열을 구하는 문제이다. K가 변수이면 다항시간내에 풀 수 없는 NP-hard문제임이 증명되어있다. 가장..

• format_list_bulleted 다이나믹 프로그래밍
• · 2023. 10. 28.
• textsms