목록9251 (1)

JINWOOJUNG

[ DP - 9251 ] LCS(C++)

접근법 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 여기서 부분 열은 상대적인 순서를 유지해야 하는데, 예를들어 ACAYKP의 부분 수열은 ACA, ACP, CYK, CAP 등 순서를 유지한 부분 수열이다. DP의 대표적인 문제 중 하나로, 스트링 편집 거리와 유사하게 접근해 볼 수 있다. 위에서 주어진 예시를 이용하면 "ACAYKP", "CAPCAK"의 LCS를 찾아야 한다. 스트링 편집 거리와 같이 한 문자열은 고정시켜 두고, 나머지 하나의 문자열 중 하나씩 증가시키면서 비교 해 보자.  ACAYKPC0  "C"와 "A"의 LCS는 없다. 따라서 0이다. ACAYKPC01..
백준 2024. 6. 15. 15:39
이전 Prev 1 Next 다음