LCS(Longest Common Subsequence, 최장 공통 부분 문자열)-알고리즘10

1. LCS? 우선 아래 개념부터 확인하고 출발하자. Subsequence vs Substring Substring: 문자열에서 연속된 부분 문자열 ex) abcde-> ace 는 substring 아님. abcde->abc 는 substring Subsequence: 문자열에서 연속된 문자열이 꼭 아니어도 되는 부분 문자열 ex) abcde-> ace 도 subsequence Common Subsequence: 두 문자열중 공통된 subsequence ex) abcde, bzxchje -> 'bce' 따라서 LCS란, 두 문자열 사이에서, 가장 긴 공통 부분 문자열(Longest Common Subsequence)을 뜻한다. 두 문자열이 주어졌을 때, LCS를 어떻게 찾을까? 2.DynamicProgr..

2023.08.24