최장 공통 부분 수열 (2) 썸네일형 리스트형 [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인 경우, 현재 수열의 누적.. [JAVA] 백준 9251번 문제, LCS (최장 공통 부분 수열) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 최장 공통 부분 수열은 두 문자열에서 가장 긴 공통 부분을 구하는 것이다. 예로 들자면 두 문자열 "ACAYKP"와 "CAPCAK"의 최장 공통 부분 수열은 "ACAK"이다. 이론은 굉장히 간단하다. "ACAYKP"를 기준으로 잡고 한 글자씩 "CAPCAK"와 비교해주면 된다. 최장 공통 부분의 길이를 알아내기 위해서는 [첫번째문자열][두번째문자열]의 .. 이전 1 다음
