취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15483번 문제인 최소 편집이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/15483

이 문제는 편집 거리(edit distance; Levenshtein distance)를 구하는 문제이다. 기본적인 DP를 이해하고 있다면 편집 거리를 구하는 것은 크게 어렵지 않다.

s1의 마지막 글자를 뺀 문자열을 s1', s2의 마지막 글자를 뺀 문자열을 s2'라 하자.

그렇다면, 길이가 1 이상인 문자열 s1과 s2의 편집 거리는 다음 1, 2, 3 중 최솟값과 같다.

1) (s1'과 s2의 편집 거리) + 1

[s1'에 삽입 연산을 하는 경우]

2) (s1과 s2'의 편집 거리) + 1

[s1에 삭제 연산을 하는 경우]

3) (s1'과 s2'의 편집 거리) + ( s1과 s2의 마지막 글자가 같다면 0, 아니면 1)

[s1의 마지막 글자에 교체연산을 하는 경우 / 교체가 필요없는 경우에는 0을 더한다]

이제 이를 메모이제이션(memoization)을 이용하여 구현하면 된다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <cmath>
using std::cin;
using std::cout;
using std::string;
using std::min;

int arr[1001][2]; // memoization을 위한 배열

int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    int s1len = s1.length();
    for (int i = 1;i <= s1len;i++) {
        arr[i][0] = i;
    }
    for (int j = 1; j <= s2.length();j++) {
        arr[0][1] = j;
        for (int i = 1;i <= s1len;i++) {
            arr[i][1] = min(arr[i - 1][0] + ((s1[i - 1] == s2[j - 1]) ? 0 : 1), min(arr[i - 1][1], arr[i][0]) + 1);
        }
        for (int i = 0;i <= s1len;i++) {
            arr[i][0] = arr[i][1];
        }
    }
    cout << arr[s1len][1];

    return 0;
}