백준 9251 (1) 썸네일형 리스트형 [LCS] Longest Common Subsequence (최장 공통 부분 문자열) LCS 알고리즘이란..? 한국말로 번역해보면 "최장 공통 부분 문자열"이다. 여기서 Subsequence와 Substring의 차이에 대해 이해해야만 한다. 둘의 차이는 연속성이다. 연속된 부분 문자열을 만족하는 것은 Substring이고 연속되지 않은 부분 문자열이라면 Subsequence이다. "ACAYKP" "CAPCAK" 가장 긴 Substring은 CA이고 가장 긴 Subsequence는 ACAK이다. LCS 를 구하는 방법 (다이나믹 프로그래밍) 먼저 dp배열을 만들어준다. 0열 0행을 추가적으로 만들어준다. (편의를 위해) 배열1과 배열2를 비교하는데 배열2의 문자하나를 잡아서 배열1의 모든 문자와 비교해나간다. 문자를 비교해서 값이 같으면 왼쪽 위(현재 문자를 포함하지 않은 최댓값)에 +1.. 이전 1 다음