Dynamic Programming - Edit Distance, Two-Person Traversal...

http://people.csail.mit.edu/bdean/6.046/dp/

위 링크의 Dynamic Programming 문제들 중,

남은 두 문제인 Edit Distance 와 Two-Person Traversal of a Sequence of Cities 에 대하여 정리해 본다.

( 12번 Bin Packing 은 굳이 할 필요가 없어 패스 )

이 두 문제는 도대체 해결방법이 떠오르지 않아, 인터넷의 풀이를 보고 말았다.

두 문제의 풀이를 보면서 일단 DP 문제라도,

문제를 Recursive 하는 푸는 방법을 떠 올리고,

거기서 DP 풀이를 찾는 것이 좋겠다는 생각이 들었다.

- Edit Distance

문제) String A, String B 가 있을 때, A -> B 로 바꾸는 최소한의 Operation 수를 구하는 문제이다.

        Operation 은 다음과 같은 3 가지가 있다.

        1. Insert a character, 2. Remove a character, 3. Change a character to another character.

이 문제는 아래 링크의 풀이를 참고하였다.

https://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/styles/pages/editdistance.html

거기서 사용된  예를 가지고 문제를 쪼개는 방법을 설명해 본다.

String A: "Zeil"

String B: "trials"

라고 했을 때, "Zeil" -> "trials" 을 만드는 경우는 다음과 같이 쪼갤 수 있다.

(1. Add Case)

"Zeil" -> "trial" 의 Edit Distance + 1 ( 여기서 +1 은 "s" Add Operation)

(2. Remove Case)

"Zei" -> "trials" 의 Edit Distance + 1 (여기서 +1 은 "l' Remove Operation)

(3. Change Case)

"Zei" -> "trial" 의 Edit Distance + 1 (여기서 +1 은 "l" -> "s" Change Operation)

이 세가지 Case 에서 Recursive 하게 Min 값을 찾아가면 되는 것이다.

물론.. Recursive 하게 풀면 O(3^N) 정도의 복잡도에 깔려 죽겠지..

그래서 DP Table 을 구성하는 데...

DP[n][m] : String A 의 Substring (0,n) 에서 String B 의 Substring (0,m) 로 변환하는 Edit Distance

로 둔다. 그리고 위의 Case 를 참고로 찾아가는 것이다.

위의 풀이에서는 DP Table 에 빈 문자열을 0 번째 인덱스에 채워 계산을 편하게 했다.

	""	t	r	i	a	l	s
""	0	1	2	3	4	5	6
Z	1
e	2
i	3
l	4

그리고 이제 이 Table 을 채워가는 것이다.

How? 윈쪽, 윈쪽 위, 위 쪽의 값을 참고로 채워 나간다.

(1. 윈쪽 참고)

Z -> "" 만드는 Edit Distance + 1 ( +1 은 Add 't' 가 되겠다 )

(2. 위쪽 참고)

"" -> "t" 만드는 Edit Distance + 1 ( +1 은 Remove 'Z' 가 되겠다 )

(3. 왼쪽 위 참고)

"" -> "" 만드는 Edit Distance +1 or 0 (+1 은 Chagne 'Z' -> 't' 가 되겠다. 두 문자가 같으면 0 )

이런식으로 차례대로 채워가면 OK.

소스코드는 아래와 같다.

위 링크에 있는 소스를 사용했지만, 그대로 사용하면 제대로 동작하지 않는다.

마지막 changeDistance 계산식의 마지막 +1 or 0 결정 부분에 괄호를 넣어야 한다.

(Dynamic Programming Solution - 2012/9/11 잘못된 소스 수정)

int editDistance(string x, string y) {
    for(int i = 0; i <= (int)x.length(); i++)
        DP[i][0] = i;
    for(int j = 0; j <= (int)y.length(); j++)
        DP[0][j] = j;

    for(int i = 1; i <= (int)x.length(); i++) {
        for(int j = 1; j <= (int)y.length(); j++) {
            DP[i][j] = min(min(DP[i][j-1]+1, DP[i-1][j]+1), DP[i-1][j-1] + ((x[i-1] == y[j-1]) ? 0 : 1));
        }
    }
    return DP[x.length()][y.length()];
}

(Recusive Solution)

int editDistance (string x, string y) {
    if (x == "")
        return y.length(); // base case
    else if (y == "")
        return x.length(); // base case
    else
    {
        int addDistance = editDistance(x, y.substr(0,y.length()-1)) + 1;
        int removeDistance = editDistance(x.substr(0,x.length()-1), y) + 1;
        int changeDistance = editDistance(x.substr(0,x.length()-1), y.substr(0,y.length()-1))
                            + ((x[x.length()-1] == y[y.length()-1]) ? 0 : 1);

        return min(min(addDistance, removeDistance), changeDistance);
    }
}

- Two-Person Traversal of a Sequence of Cities

문제) 순서가 있는 N 개의 도시가 있다. (지리적으로 순서가 있다는 의미가 아니다. 방문할 수 있는 순서를 말한다. )

        그리고 각각의 도시는 모두 연결되어 있다.

        이 도시들을 두 집합으로 나누고 (연속된 도시일 필요는 없다.),

        두 사람 A, B 가 각각의 도시 집합을 방문한다고 할 때,

        A, B 의 이동거리의 합이 가장 짧은 경우는 얼마가 되는가?

        단, A, B 방문 시작점은 각 도시 집합의 첫 번째 도시이다.

처음엔 문제 자체를 이해를 못해서 한참 해멨다.

그 다음에는 문제를 어떻게 풀어야 하는지도 몰라서 한참 생각하다가,

결국 인터넷을 뒤졌는데, 이걸 깔끔하게 설명한 곳도 찾기가 힘들었다.

그리다가 아래 링크의 Grimbal 이란 사람의 리플을 보고 풀었다.

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1311271494

이 문제는 여러모로 헷갈렸다.

이제 머리가 잘 안 돌아가나 보다. ㅠㅠ

이 문제의 아이디어의 핵심은 다음이라고 본다.

DP[i][j] : ( 0 <= i < j ), 두 사람이 각각 i, j 번째에서 방문이 끝났을 때, 이동거리 합의 최소값.

이것이 이 문제를 푸는 핵심이다.

이것을 가지고 문제를 쪼개 보면 다음과 같은 경우가 나온다.

DP[i][j] 만들기 전의 상태를 DP[a][b] 라고 했을 때,

1. a -> i 가 되고, b -> j 가 되는 경우. (멀리 간 넘이 다음 도시로 이동한 경우)

2. a -> j 가 되고 b -> i 가 되는 경우. (적게 간 넘이 멀리 간 넘을 넘어 다음 도시로 이동한 경우)

이렇게 두 가지로 나뉜다.

d(i, j) 를 i 번째 도시에서 j 번째 도시까지의 거리라고 할 때,

1번의 경우, DP[i][j] = DP[i][j-1] + d(j-1, j) 로 구할 수 있겠다. (단, i < j-1 )

2번의 경우, DP[i][j] = Min( DP[k][j-1] + d(k, j) ). ( 0 <= k < j-1 )

2번은 i+1 = j 인 경우이다. 이 경우는 멀리있는 넘을 넘어가는 경우의 수를

모두 조사하여 Min 값을 찾는 것이다.

소스는 다음과 같다.

void do_tpt() {
    UINT    min_value, new_value;

    DP[0][1] = 0;
    for(int j = 2; j < NUM_OF_CITIES; j++) {
        for(int i = 0; i <= j-1; i ++) {
            min_value = UINT_MAX;
            if(i < j-1) {   // case 'i' fixed, move 'j-1' to 'j'
                DP[i][j] = DP[i][j-1] + Distance[j-1][j];
            }
            else {    // i == j-1, case 'j-1' fixed..
                min_value = UINT_MAX;
                for(int k = 0; k <= j-2; k++) {
                    new_value = DP[k][j-1] + Distance[k][j];
                    if(new_value < min_value) {
                        min_value = new_value;
                        DP[i][j] = new_value;
                    }
                }
            }
        }
    }
}