🔗 문제 링크 https://www.acmicpc.net/problem/9252 ✍️ 문제 풀이 해당 문제는 다이나믹 프로그래밍 문제로, 1 ~ n 인덱스까지의 A 문자열이 있을 때, 1 ~ n 인덱스까지의 B 문자열과의 최장 공통 수열을 2차원 dp 배열에 차례대로 갱신하는 Bottom-Up 방식으로 풀었다. 이 문제는 기존 LCS 문제와 같으나, 개수 뿐만 아니라 해당 수열을 직접 출력까지 해야한다. 따라서 LCS의 길이를 구하는 부분은 생략하고, 수열을 출력하는 부분만 알아보겠다. (9251번 : LCS 링크) 1) A 문자

LCS 알고리즘(Longest Common Subsequence) LCS == 최장 공통 부분 수열로, 두 문자열을 비교했을 때 가장 긴 공통 부분 문자열 LCS는 최장 공통 문자열(Longest Common String)을 의미하기도 하는데, 둘의 차이점은 공통 부분이 연속하는지 아닌지 여부다. 두 문자열 ABCD, ABFC 가 있다고 할 때, 최장 공통 문자열 : AB 최장 공통 부분 수열 : ABC _ ✍️ DP를 이용한 LCS 풀이 방법 : DPi에는 i 인덱스까지의 문자열 1과 j인덱스까지의 문자열 2 사이의 LCS의 길이가 저장된다. 문자열 BCFD와 ABCD를 비교한다고 할 때 각 문자열의 세번째 인덱스까지의 LCS는 아래 두 가지 중 하나로 결정된다. 세 번째 글자가 같다면 : BC와 AB 사이의 LCS + 1