편집 거리 알고리즘 및 LCS문제

/*

★편집 거리 알고리즘★

편집 거리 알고리즘은 두 문자열이 주어지고 한 문자열을 다른 문자열으로 최소한의 연산을 사용해서 바꾸는 알고리즘이다

연산은 수정, 삭제, 삽입 3가지 연산을 사용한다.

이 알고리즘으로 구한 최소 편집 거리는 두 문자열간의 유사도를 판단하는 기준이 될 수 있다.

알고리즘은 다이나믹 프로그래밍으로 접근 할 수 있고 문자열 A와 B에 대해

DP[i][j] = A문자열 (1~i)번 까지를 B문자열 (1~j)번 까지로 바꾸는 최소 편집 거리 라고 정의 할 수 있다.

A문자열의 i번째 B문자열의 j번째를 비교해서 단어가 같으면 연산을 수행 필요가 없으므로 인덱스를 증가시켜준다.

만약 단어가 다르면 삽입, 수정, 삭제 세가지 연산 준 가장 작은 값을 취해주고 +1을 해주면 된다.

*/

#include <cstdio>

#include <iostream>

#include <string>

using namespace std;

int dp[123][123];

// dp[i][j] = A(1~i) 까지를 B(1~j)로 바꾸는 최소 편집 거리

int min(int a, int b) {

return a > b ? b : a;

}

int main()

{

string A, B;

cin >> A >> B;

for (int i = 1; i <= A.size(); i++) {

for (int j = 1; j <= B.size(); j++) {

if (A[i - 1] == B[j - 1]) {

dp[i][j] = dp[i - 1][j - 1];

}

else {

dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;

// A를 기준으로 dp[i-1][j-1] 에서 수정, dp[i-1][j]는 삽입, dp[i][j-1]는 삭제

}

}

}

printf("%d\n", dp[A.size()][B.size()]);

return 0;

}