SY DevLog

1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 동적 계획법을 통한 최장 공통 수열을 구하는 문제이다. 보통은 두 문자열의 LCS를 구하는데, 이 문제는 세 개의 문자열의 LCS를 구해야 한다. 아래는 LCS(Lowest Common Subsequence)를 구하는 방법에 대한 글이다. lotuslee.tistory.com/39?category=964787 LCS(Longest Common Subsequence) LCS(Longest Common Subsequence) : 최장 공통 부분문자열 두 문자열에서 "공통되는 가장..

LCS(Longest Common Subsequence) : 최장 공통 부분문자열 두 문자열에서 "공통되는 가장 긴 부분문자열"을 찾는 알고리즘 여기서 subsequence는 꼭 연속하지 않아도 되는 부분문자열이다. * 문자열에서 substring 과 subsequence의 차이 * 문자열 A가 있을 때, - substring : 문자열 A의 연속하는 부분 문자열 - subsequence : 문자열 A에서 연속하지 않은 부분 문자열(연속해도 되고, 연속하지 않아도 됨) 즉, 다시 한번 짚고 넘어가면 LCS 알고리즘은 두 개의 문자열에서 subsequence를 찾는 알고리즘이다. LCS 알고리즘은 DP(Dynamic Programming : 다이나믹 프로그래밍)을 이용한다. LCS 알고리즘은 예제를 보면서..