최장 공통 부분수열(Longest Common Subsequence) 최장 공통 문자열Longest common substring 점화식 if i == 0 or j == 0: LCS[i][j] = 0 elif string_A[i] == string_B[j] LCS[i][j] = LCS[i-1][j-1] + 1 else: LCS[i][j] = 0 동작 문자열 A, 문자열 B의 한 글자씩 비교한다. 두 문자가 다르다면 LCS[i][j]에 0을 표시 두 문자가 같다면 LCS[i-1][j-1] 값을 찾아 + 1 위 과정을 반복한다. 이 과정이 성립하는 이유는 공통 문자열은 연속 되어야 하기 때문에 현재 두 문자가 같을 때 두 문자의 앞 글자 까지가 공통 문자열이라면 계속 공통 문자열이 이어질 것이고, 아니라면 ..