작심 24/7

9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS(Longest Common Subsequence) 문제이다. LCS(Longest Common Substring)과 같이 문자열 A, B에서 A[i]와 B[j]가 같을 때는 DP[i][j] = DP[i-1][j-1] + 1 이 되지만 A[i]와 B[j]가 다를 때는 DP[i][j] = max(DP[i-1][j], DP[i][j-1]) + 1 이 된다. 그러면 최종적으로 DP[문자열A 끝][문자열B 끝]이 L..

5582번: 공통 부분 문자열 문제 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예 www.acmicpc.net LCS(Longest Common Substring) 문제이다. 문자열 A, B에서 A[i]와 B[j]가 같을 때, DP[i][j] = DP[i-1][j-1] + 1 이 된다. 무슨 말이냐 하면 문자열 A는 ABCDE이고 B는 CDEGG라 할 때 예를 들어 A[4]과 B[2]가 E로 같으면 그 전까지의 문자열 ABCD와 CD에서 가장 길었던 문자열의 길이(DP[3][1])에 E 길이 1을 더한 값이 DP[4][2]에 들어가게 된다. DP 배열의 값 중..