백준 15483 편집거리 알고리즘 풀이

목표: 백준 15483 풀기

환경: mac OS Mojave 10.14, CLion

로직

문제이해

굉장히 유명한 편집 거리 알고리즘을 다이나믹 프로그래밍 문제로 풀이 DP를 모르는데 이 문제를 싸악 풀었으면 알고리즘 안해도 됌.
DP에 대해 모른다면 이해 자체가 안되는 문제

문제접근

이게 왜 단계별로 풀어보기 jh05013 Edition pt.1 에 들어가는지 전혀모르겠음.

이 문제를 풀이하면서 고민했음. 풀이가 뭘까, 전혀 모르겠음. 모르겠음. 전혀 모르겠음. 검색했음.
블로그마다 편집거리 알고리즘이라 써있음. 편집거리 알고리즘 검색했음.

그래서 인터넷에서 본 풀이를 정리함. the mighty geeksforgeeks

이 문제에서 작은 문제란 무엇인가?

정리가 이해가 안된다면 geeksforgeeks 가서 그림을 보면 되죠. 또한 DP를 모른다면 코드플러스의 백준 강의를 들으면 되죠.

이 아이디어는 두 문자열의 왼쪽 또는 오른쪽에서 쳐다보는 모든 문자를 하나씩 처리함. 오른쪽부터 보죠. 모든 문자 쌍을 순회할때 두가지의 경우의 수가 있죠.

그전에 정의할 것
m : str1의 길이
n : str2의 길이

  1. 두 문자열의 마지막 문자가 같다? m-1, n-1 이 작은 문제가 되죠.
  2. 두 문장열의 마지막 문자가 다르다? 문제에서 주어진 대로
    삽입
    삭제
    교체 로 나눌 수 있죠.

    삽입의 경우는 m 과 n-1의 작은 문제로 볼 수 있고
    삭제의 경우는 m-1 과 n의 작은 문제로 볼 수 있고
    교체의 경우는 m-1 과 n-1의 작은 문제로 볼 수 있죠.

작은 문제로 나누어도 겹치는 경우의수가 매우 발생함.
시간복잡도가 O(3^m) 인 아주 뭣 같은 복잡도죠.

고래서
DP를 무조건 사용하면 시간복잡도로 이득, bottom-up이든 top-down이든 똑같죠. 메모이제이션을 써야해요.

시간복잡도O(n*m)에 해결해버림.

나에겐 매우 어려운 문제였음…

#include<iostream>
#include<string>
using namespace std;

// Utility function to find the minimum of three numbers 
int min(int x, int y, int z)
{
    return min(min(x, y), z);
}

int editDistDP(string str1, string str2, int m, int n)
{
    // Create a table to store results of subproblems 
    int dp[m+1][n+1];

    // Fill d[][] in bottom up manner 
    for (int i=0; i<=m; i++)
    {
        for (int j=0; j<=n; j++)
        {
            // If first string is empty, only option is to 
            // insert all characters of second string 
            if (i==0)
                dp[i][j] = j;  // Min. operations = j 

                // If second string is empty, only option is to
                // remove all characters of second string
            else if (j==0)
                dp[i][j] = i; // Min. operations = i 

                // If last characters are same, ignore last char
                // and recur for remaining string
            else if (str1[i-1] == str2[j-1])
                dp[i][j] = dp[i-1][j-1];

                // If the last character is different, consider all
                // possibilities and find the minimum
            else
                dp[i][j] = 1 + min(dp[i][j-1],  // Insert 
                                   dp[i-1][j],  // Remove 
                                   dp[i-1][j-1]); // Replace 
        }
    }

    return dp[m][n];
}

int main(){
    string a,b;
    cin>> a >> b;

    cout<<editDistDP(a,b, a.length(),b.length());
    return 0;
}