개요

LCS (Longest Common Subsequence, 최장 공통 부분 수열)
즉, 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것

알고리즘

1. arr1, arr2가 주어질 때, len(arr1)+1 * len(arr2)+1 dp 배열을 사용한다.

2. 여기서 arr1의 i-1 인덱스, arr2의 j-1 인덱스까지 최장 공통 부분수열을 dp[i][j]에 기록한다.

3. arr1[i-1], arr2[j-1]가 동일하다면, dp[i-1][j-1]에서 arr[i-1]을 더하고, 아니라면 dp[i-1][j]나 dp[i][j-1] 중 긴 값을 가져온다.

   3-1. 값이 같을 때 [i-1][j-1]에서 찾는 이유는 현재 같은 arr1[i-1],arr2[j-1]이 제외된 수열 중 가장 긴 수열이기 때문이다. [i-1][j], [i][j-1]을 사용한다면, 중복된 문자, 숫자를 사용하는 셈이 된다.

4. 그럼 dp[-1][-1]에 최장 공통 부분 수열이 저장된다.

dp = [[""]*(len(arr2)+1) for _ in range(len(arr1)+1)]

for i in range(1,len(arr1)+1):
    for j in range(1,len(arr2)+1):
        if arr1[i-1] == arr2[j-1]:
            dp[i][j] = dp[i-1][j-1]+arr1[i-1]
        else:
            if len(dp[i-1][j]) > len(dp[i][j-1]):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]

만약, 길이만 구해도 되는 경우, ""를 0으로 바꾸고, 문자열 대신 값이 같을 때, +1을 해주면 된다.