문제 해결/개념정리1 최장 공통 부분 수열(LCS) 최장 공통 부분 수열이란? 먼저, 부분 수열이란 순서대로 뽑아서 나올 수 있는 수열들을 의미합니다. 예를 들어 abcdefb의 부분 수열에는 abc, bdf등이 있습니다. 따라서 공통 부분 수열은 두 문자열에서 순서대로 뽑아서 나올 수 있는 공통 부분 수열을 의미합니다. 예를 들의 abcde와 cde의 공통 부분 수열에는 ce, de cde 등이 있습니다. 마지막으로 최장 공통 부분 수열은 두 문자열에서 순서대로 뽑아서 나올 수 있는 가장 길이가 긴 공통 부분 수열이 됩니다. abcde와 cde의 최장 공통 부분 수열은 cde가 됩니다. DP를 활용하여 LCS 구하기 LCS는 DP를 활용하여 해결할 수 있습니다. 두 문자열 A, B의 LCS를 구한다고 가정하면 DP[i][j]는 A의 i번째까지의 문자와 .. 2022. 12. 13. 이전 1 다음