BOJ 백준 15483 : 최소 편집

시작하면서

　이번 문제는 최소 편집 알고리즘(Edit distance algorithm) 문제이다.

BOJ 15483 - 최소 편집

​

문제 이해

​ 최소 편집 알고리즘(Edit distance algorithm)은 다이나믹 프로그래밍의 일종으로 두 문자열의 유사도를 판단하는 알고리즘이다. LCS와 비슷하게 두 문자열을 비교하면서 진행해나간다. 개념이 잘 설명된 블로그 링크를 첨부한다.

LINK

​

해결

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

int GetEditDistance(vector<vector<int>>& editDistance, string a, string b)
{
    for (int i = 0; i < editDistance.size(); i++)
    {
        editDistance[i][0] = i;
    }

    for (int i = 0; i < editDistance[0].size(); i++)
    {
        editDistance[0][i] = i;
    }

    for (int i = 1; i < editDistance.size(); i++)
    {
        for (int j = 1; j < editDistance[i].size(); j++)
        {
            if (a[i - 1] == b[j - 1])
            {
                editDistance[i][j] = editDistance[i - 1][j - 1];
            }
            else
            {
                editDistance[i][j] = min(editDistance[i - 1][j], editDistance[i][j - 1]);
                editDistance[i][j] = min(editDistance[i][j], editDistance[i - 1][j - 1]);
                editDistance[i][j] += 1;
            }
        }
    }

    /*for (int i = 0; i < editDistance.size(); i++)
    {
        for (int j = 0; j < editDistance[i].size(); j++)
        {
            cout << editDistance[i][j] << " ";
        }
        cout << "\n";
    }*/

	return editDistance[editDistance.size() - 1][editDistance[0].size() - 1];
}

int main()
{
    // sync off
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // sync off

    vector<vector<int>> editDistnance;
    string a, b;

    cin >> a >> b;

    editDistnance.resize(a.length() + 1);
    for (int i = 0; i < editDistnance.size(); i++)
    {
        editDistnance[i].resize(b.length() + 1);
    }

    cout << GetEditDistance(editDistnance, a, b);

    return 0;
}