LCS

소개 두 문자열이 있을 때, 가장 긴 공통 부분 문자열을 찾아내는 알고리즘, 부분 문자열이란 원소들이 원래 순서를 유지하면서 일부 원소를 생략할 수 있는 형태를 말함 예시: 문자열 A: A**B**CB**DAB** 문자열 B: **BD**C**AB**B A와 B의 LCS는 BDAB라고 할 수 있다. 아이디어 2차원 배열을 통해 중간 결과를 메모이제이션 한다. 이 배열은 두 문자열의 길이에 따라 결정된다. 알고리즘 편의상 첫 번째 열과 행은 0으로 초기화 한다. 빈 문자열과 비교했을 때의 경우를 처리할 수 있다. - A B C B D A B - 0 0 0 0 0 0 0 0 두 번째 문자열의 문자를 차례대로 가져와 비교한다. - A B C B D A B - 0 0 0 0 0 0 0 0 B 0 0 1 테이블의 각 원소는 그 시점의 substring간의 LCS를 의미한다. 즉 위 표에서 1인 원소는 substring “AB”와 “B”의 LCS의 길이가 1임을 의미한다. 앞선 결과를 기반으로 LCS의 크기를 계산한다. - A B C B D A B - 0 0 0 0 0 0 0 0 B 0 0 1 1 B와 C는 같지 않더라도, “ABC”와 “B”를 비교하는 것과 같으므로, 이전에 “AB”와 “B”를 비교한 값인 1이 유지된다. 만약 두 문자가 다른 경우 - A B C B D A B - 0 0 0 0 0 0 0 0 B 0 0 1 1 1 1 1 1 D 0 0 1 B와 D는 다르지만, “AB”와 “BD”의 LCS의 길이는 1이다. 3번의 경우와 합쳐서 두 원소가 다르지 않을 때, DP 테이블을 채우는 점화식을 세울 수 있다. dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) 두 문자가 같은 경우 - A B C B D A B - 0 0 0 0 0 0 0 0 B 0 0 1 1 1 1 1 1 D 0 0 1 1 1 2 두 문자가 같은 경우, 즉 위 표의 상황에서는 “ABCBD”와 “BD”의 LCS의 크기를 구하는 경우가 된다. 이 경우는 “ABCB”와 “B”의 LCS의 크기에서 원소 “D”가 더해진 것과 같으므로, 대각선 위에 있는 값에서 1을 더한 값이 된다. dp[i][j] = dp[i - 1][j - 1] + 1 동작 원리 DP 테이블을 채우면서 두 문자가 다른 경우 이전에 계산한 결과를 그대로 유지한다. 두 문자가 같은 경우 그 문자가 없는 경우의 LCS의 크기에서 1을 더한다. 점화식 if (A[i - 1] == B[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1 } else { dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1]; } 기타 길이와 실제 문자열 DP 테이블의 마지막 값인 dp[m][n]은 LCS의 길이만 나타낸다. ...