LCS1 [백준 9252] LCS 2 (Python 풀이, Gold IV) https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net DP 테이블을 만든 뒤, 테이블 역추적으로 LCS 문자열을 복원하는 문제다. 일단 LCS 문제를 푸는 점화식은 잘 알려져 있다. memo[i][j] = memo[i - 1][j - 1] + 1 (if a[i] == b[j]) memo[i][j] = max(memo[i - 1][j], memo[i][j - 1]) (otherwise) DP 역추적은 이.. 2023. 1. 18. 이전 1 다음
