Python LCS (1) 썸네일형 리스트형 [Python] 백준 9251번 문제, 최장 공통 부분 수열(LCS) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제는 최장 공통 부분 수열을 그대로 적용시키면 해결할 수 있는 문제이다. 반복문의 i는 compared_str의 길이만큼 작동하며, j는 standard_str의 길이만큼 작동해 i와 j를 비교한다. dp[i][j]를 채우는 수식은 다음과 같다. i == j인 경우, 전 단계의 최고 누적합에다가 +1를 한다. i != j인 경우, 현재 수열의 누적.. 이전 1 다음
