Azza's Blog

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 번째 인덱스에 채워 계산을 편하게 했다.

그리고 이제 이 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);
    }
}

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

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

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

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;
                    }
                }
            }
        }
    }
}

이 문제는 다음과 같은 아이디어로 풀 수 있다.

기존의 식에 O[k-1] Operation과 B[k] Boolean 값이 추가 된 경우,

1. B[k-1] 까지 Evaluation 결과가 T인 경우와 F인 경우

2. B[k-2] 까지 Evaluation 결과가 T인 경우와 F인 경우

위의 경우에 따라, 나눠서 생각하면 된다.

점화식은 정리해 둔게 없어서 패스.

굳이 점화식 없어도 이런 문제들은 힌트 하나로 풀리는 거니깐.

실제 소스코드 부분은 다음과 같다.

void do_cbp() {
    int i, j;

    for(j = 0; j < MAX_OPER_COUNT+1; j++) {
        for(i = 0; i <= j; i++) {
            if(i == j) {
                DP[i][j] = (B[i] == T)? 1 : 0;
            } else if(i+1 == j) {
                DP[i][j] = Eval(B[j-1], O[j-1], B[j]);
            }
            else {  // if (j > i)
                Symbols eval = Eval(B[j-1], O[j-1], B[j])? T : F;

                DP[i][j] = DP[i][j-1] * Eval(T, O[j-1], B[j])
                        + (2^(j-i-2)-DP[i][j-1]) * Eval(F, O[j-1], B[j])
                        + DP[i][j-2] * Eval(T, O[j-2], eval)
                        + (2^(j-i-3)-DP[i][j-2]) * Eval(F, O[j-2], eval);
            }
        }

    }
}

이 문제는 종이에 점화식을 잘 적어둬서 간만에 점화식을 적을 수 있겠다.

점화식은 다음과 같다.

DP[[i][j] : i 번째 ~ j 번째 동전이 있을 때, Max Value.

N[k] : k 번째 동전의 금액.

( j == i+1 인 경우 )

DP[i][j] = Max(N[i], N[j])

( j > i+1 인 경우 )

Case_I = Max(DP[i+2][j], DP[i+1][j-1]) + N[i]        ; 내가 i 번째 동전을 택한 경우, 상대방의 선택 경우 중 Max 값 

Case_J = Max(DP[i+1][j-1], DP[i][j-2]) + N[j]        ; 내가 j 번째 동전을 택한 경우, 상대방의 선택 경우 중 Max 값

DP[i][j] = Max(Case_I, Case_J)

값을 구하는 순서는 [i][j] 에서

for(j = 0; j < k+1; k++)

for(i = j-1; i >= 0; i -= 2)

위의 순서로 구해야 한다. 물론 j 의 순서에 따라 i 의 순서가 바뀔 수도 있다.

소스코드는 아래와 같다.

void do_coingame() {
    int i, j;
    int case_i, case_j;

    for(j = 1; j < MAX_COINS; j++) {
        for(i = j-1; i >= 0; i -= 2) {
            if(j == i+1) {
                DP[i][j] = max(N[i], N[j]);
            } else {    // j > i+1, j will be j >= 2
                case_i = N[i] + max(DP[i+2][j], DP[i+1][j-1]);
                case_j = N[j] + max(DP[i+1][j-1], DP[i][j-2]);
                DP[i][j] = max(case_i, case_j);
            }
        }
    }
}

이 문제는 다음과 같은 아이디어로 풀었다.

DP[i] : i 번째 도시의 다리를 연결했을 때, 최대 다리 갯수.

DP[i] = DP[0]...DP[i-1] 에서 i 번째 다리를 연결 했을 때, Cross 되지 않는 경우 중 MAX 값 + 1

딱히 점화식을 쓰기도 복잡할 꺼 같아서 패스. 핵심 소스코드로 대신 함.

class Bridge {
public:
    int nc;
    int sc;

    bool isCross(const Bridge b) const {
        return ((b.nc-nc) * (b.sc-sc) > 0) ? false : true;
    }
};

bool check_cross(int bridge, int bridge_set) {
    int prev = bridge_set;

    while(prev > -1) {
        if(B[bridge].isCross(B[prev]))
            return true;
        prev = PREV[prev];
    }

    return false;
}

void do_bb() {
    int i, j, max_bridge;

    DP[0] = 1;
    PREV[0] = -1;
    max_bridge_idx = 0;
    for(i = 1; i < NUM_OF_CITIES; i++) {
        DP[i] = 0;
        PREV[i] = -1;    // i 번째 다리를 연결했을 때의 Bridge Set 을 구하기 위한 배열
        max_bridge = 0;
        for(j = 0; j < i; j++) {
            if(DP[j] > DP[i] && check_cross(i, j) == false) {
                DP[i] = DP[j];
                PREV[i] = j;
            }
        }
        DP[i]++;

        if(DP[i] > DP[max_bridge_idx])
            max_bridge_idx = i;
    }

}

해답을 얼핏 봤을 때, Knapsack 이라는 단어를 보고 아하! 했다.

정말 그 한 단어에 실마리가 풀릴줄이야. 그래서 내가 못 풀었다는 것이다.

문제를 푼 아이디어는 다음과 같다.

SUM[i] : i 번째 원소까지의 합이라고 했을 때,

SUM[i]/2  의 Capacity 를 가지는 Knapsack 에 들어가는 값을 구하면 되는 것이다.

점화식 쓰기도 고역이라 역시 패스하고 소스코드로 대신...

void do_bp() {

    int n, c;

    for(n = 0; n < NUMBERS; n++) {

        DP[n][0] = 0;

        for(c = 1; c <= HALF_SUM; c++) {

            if(c >= N[n]) {

                if(n >= 1) {

                    DP[n][c] = max(DP[n-1][c], DP[n-1][c-N[n]]+N[n]);

                } else {

                    DP[n][c] = N[n];

                }

            } else {

                if(n >= 1) {

                    DP[n][c] = DP[n-1][c];

                } else {

                    DP[n][c] = 0;

                }

            }

        }

    }

}

최장 길이와 수열을 모두 구하는 아이디어는 다음과 같다.

A[] - 집합 A

DP[j] : 0 ~ j th 까지의 LIS 값.

DP[j] 는 A[0] ~ A[j-1] 중 A[j] 보다 작으면서,

DP[] 값이 가장 긴 원소를 찾아 연결하면 된다.

DP[0] = 1

DP[j] = MAX(DP[k] + 1)        // 단 k = 0 ... j-1, A[j] > A[k] 인 경우

P[j] : j th Element 가 속한 LIS 에서 이전 Element 를 가리키는 Index

위와 같은 아이디어로 풀면 O(n^2) 복잡도가 나온다.

위키피디아에는 O(n log n) 으로 개선이 가능하다는데, 귀찮아서 패스.

void find_lis() {
    int i, j, prev;

    // Simple way
    for(i = 0; i < NUM_OF_NUMBERS; i++) {
        prev = -1;
        DP[i] = 0;
        DP_PREV[i] = -1;
        for(j = i-1; j >= 0; j--) {
            if(A[i] > A[j] && DP[j] > DP[prev])
                prev = j;
        }
        if(prev == -1)
            DP[i] = 1;
        else
            DP[i] = DP[prev] + 1;
        DP_PREV[i] = prev;
    }

}

아이디어는 다음과 같다.

1. Box 타입을 재구성.

   Box 는 Rotation 이 가능하므로,

   Box 의 H, W, D 가 각각 H 가 되는 경우로 나눔. 단, 재구성한 타입에서는 W > D 가 되도록 함.

2. 재구성한 Box 타입을 Sort. (큰 박스가 먼저 오도록.)

3. 위의 LIS 아이디어를 적용하여 문제 해결.

void box_stacking() {

    int i, j, total_max, max_height;

    DP[0] = B2[0].h;

    PREV[0] = -1;

    total_max = 0;

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

        DP[i] = B2[i].h;

        PREV[i] = -1;

        max_height = 0;

        for(j = 0; j < i; j++) {

            if(B2[j].canStack(B2[i]) && DP[j] > max_height) {

                DP[i] = DP[j] + B2[i].h;

                PREV[i] = j;

                max_height = DP[j];

            }

        }

        if(DP[i] > total_max)

            total_max = DP[i];

    }

}

아이디어는

C-1 을 만드는 데 필요한 동전 갯수에 1원짜리 동전 하나를 더한 경우와

(C - 임의의 동전 가치) 를 만드는 데 필요한 동전 갯수 + 임의의 동전 1개인 경우를 비교해서

적은 쪽을 택하는 것.

점화식은 다음과 같다

M[C] = Change C 를 만들 때 사용하는 가장 적은 동전의 수 라고 했을 때,

M[C] = MIN( M[C-1]+1, M[C - V[j]]+1)        // 단, j = 1 ... N 이고 C >= V[j]

void minimum_coins() {
    int i, j;

    M[0] = 0;
    for(i = 1; i <= CHANGE; i++) {
        for(j = 0; j < NUM_OF_TYPES; j++) {
            if(i >= V[j])
                M[i] = MIN(M[i-1]+1, M[i-V[j]]+1);
        }
    }

}

아이디어는

D[i][j] = i 번째까지의 동전을 가지고 j 금액을 만드는 경우의 수

i-1 번째까지의 동전을 가지고 j 금액을 만드는 경우의 수에, i 번째 동전이 추가된 경우는 ==> ?

( j - i 번째 동전의 가치 * k) 의 경우의 수를 모두 더하는 것.

즉, 새로운 동전의 가치가 5 라면, { 5 }, { 55 }, { 555 } ... 가 추가되는 경우의 수를 모두 더하는 것.

점화식을 보자면, (여기서 동전의 타입의 넘버링은 0th ~ (N-1)th 까지로 생각한다)

( i == 0 인 경우 )

D[i][j] = 1    

( 아니라면 )

D[i][j] = D[i-1][j] + SUM(D[i-1][j-V[i]*k)        // k 는 자연수이고. j >= V[i]*k 인 경우.

void ways_to_make_change() {
    int i, j, k;

    for(i = 0; i < NUM_OF_TYPES; i++) {
        for(j = 0; j <= CHANGE; j++) {
            if(i == 0) {
                D[i][j] = 1;
            } else {
                D[i][j] = D[i-1][j];
                for(k = 1; j >= V[i]*k; k++) {
                    D[i][j] += D[i-1][j-V[i]*k];
                }
            }
        }
    }
}

내가 생각한 아이디어는 다음과 같다.

S[i][j] = A(i) ... A(j) 까지의 합이라고 할 때,

( j = i 인 경우) S[i][j] = A[j];

( j > i 인 경우 ) S[i][j] = S[i][j-1] + A[j];

요렇게 하면 따로이 Sum 루틴이 필요 없이,

착착 계산되어 진다는 거...

이 계산하면서 Max Sum 값을 체크하여 기억해 두면 OK.

간단하게 핵심 루틴만 적어본다면...

void find_max_sum() {
    int c, i, j;
    int max_s = 0, max_e = 0, max_sum = INT_MIN;


    for(c = 1; c <= NUM_OF_NUMBERS; c++) {   // subsequence count
        for(i = 0; i < NUM_OF_NUMBERS-c+1; i++) {   // start position
            j = i+c-1;
            if(c == 1) {
                S[i][j] = A[j];
            } else {
                S[i][j] = S[i][j-1] + A[j];
            }
            if(S[i][j] > max_sum) {
                max_sum = S[i][j];
                max_s = i;
                max_e = j;
            }
        }
    }
}

(2012.8.30 수정)

이 문제를 해결하는 좋은 알고리즘이 있었다.

Kadane's Algorithm 이다. (지나가던 과객님께 감사드립니다 (__) )

아이디어는 다음과 같은 것이다.

MaxSum(N) : N번째 원소가 포함된 Max Contiguous Subsequent Sum

MaxSum(N) : Max( MaxSum(N-1), A(N) )

( MaxSum은 굳이 배열이 아니라 그냥 변수 하나로 써도 된다 )

MaxSoFar : 계속 계산해 가던 MaxSum 들 중 최대값.

위키피디아의 파이썬 소스를 적어보면, 아래와 같다.

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

(C++ 코드)

int i = 0, j = 0, k = 0;
int MaxEnd, MaxSoFar;

MaxSoFar = MaxEnd = A[0];
for(int n = 1; n < NUM_OF_NUMBERS; n++) {
    MaxEnd = MAX(MaxEnd + A[n], A[n]);
    if(MaxEnd == A[n])
        k = n;
    if(MaxEnd > MaxSoFar) {
        MaxSoFar = MaxEnd;
        i = k;
        j = n;
    }
}

/*
 * knapsack.cpp
 *
 *  Created on: 2012. 7. 31.
 *      Author: jiwoong.yoo
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

#define NUM_OF_ITEMS    5
#define MAX_VALUE       20
#define MAX_WEIGHT      10
#define MAX_BOUND       3

#define KNAPSACK_CAPACITY   15

#define MAX(a,b)    (((a)>(b))?(a):(b))

int V[NUM_OF_ITEMS];
int W[NUM_OF_ITEMS];
int B[NUM_OF_ITEMS];

int D[NUM_OF_ITEMS+1][KNAPSACK_CAPACITY+1];

void gen_data();
void knapsack(int type);

int main() {

    gen_data();
    knapsack(0);
    knapsack(1);
    knapsack(2);

    return 0;
}


// type: 0: 0-1, 1: Bounded, others: Unbounded
void knapsack(int type) {
    int n, c, b, max_b;

    for(c = 0; c <= KNAPSACK_CAPACITY; c++)
        D[0][c] = 0;

    for(n = 0; n < NUM_OF_ITEMS; n++) {
        for(c = 1; c <= KNAPSACK_CAPACITY;  c++) {

            // Set bound
            if(type == 0)
                max_b = 1;
            else if(type == 1)
                max_b = B[n];
            else
                max_b = INT_MAX;

            for(b = 1; b <= max_b && W[n]*b <= KNAPSACK_CAPACITY; b++) {
                if(n == 0) {
                    if(c >= W[n]*b) {
                        D[n][c] = V[n]*b;
                    } else {
                        D[n][c] = 0;
                    }
                } else {
                    if(c >= W[n]*b) {
                        D[n][c] = MAX(D[n-1][c], D[n-1][c-W[n]*b]+V[n]*b);
                    } else {
                        D[n][c] = D[n-1][c];
                    }
                }
            }
        }
    }
    printf("[Type:%d][Capacity %d] Max Value = %d\n",
            type, KNAPSACK_CAPACITY, D[NUM_OF_ITEMS-1][KNAPSACK_CAPACITY]);


}

void gen_data() {
    srand(time(0));
    for(int i = 0; i < NUM_OF_ITEMS; i++) {
        V[i] = rand() % MAX_VALUE + 1;
        W[i] = rand() % MAX_WEIGHT + 1;
        B[i] = rand() % MAX_BOUND + 1;

        printf("[%2d]th item: V = %2d, W = %2d, B = %2d\n",
                i, V[i], W[i], B[i]);
    }
    printf("========================================\n");
}

Dynamic Programming도 문제를 더 작은 문제로 나눠서 해결하는 방법이다.

Knapsack Problem은 다음과 같이 문제를 나눠서 해결한다.

D[n][c] : c 크기의 배낭에 n 번째까지의 아이템을 넣는다고 했을 때, Max Value 값.

D[n][c] : (c >= W[n]*b 인 경우) 

              MAX(D[n-1][c], D[n-1][c-W[n]*b]+V[n]*b)

               (아닌경우)

              D[n-1][c];

              (단, x < 0 이면, D[x] = 0)

머, 이 정도로 정리가 가능하겠다. 어쨌거나 이해하기 어렵긴 마찬가지.

머리가 정말 좋은 사람이 아니라면, 한참을 고민을 해야 어렴풋이 감이 잡히리라 생각한다.

어쨌거나 나의 생각도 정리할 겸 설명을 해보면,

일단 N 개의 아이템에서 N 번째 아이템을 제외하고, 

가방에 넣었을 때의 Optimal Solution을 D[n-1][c] 라고 생각한다.

(물론 이건 밑에서 부터 구해와야 하는 값이다. 생각 자체는 저런식으로 한다는 거다.)

D[n-1][c] 상황에서  N 번째 아이템이 '짠'하고 등장했을 때,

N 번째 아이템을 넣지 않았을 때의 Value 값과,

N 번째 아이템의 Weight 만큼 제외한 Value 값에 N 번째 아이템의 Value를 더한 값을 비교해서

둘 중 큰 값을 D[n][c] 의 Max Value 로 선택하는 것이다.

(즉, 다른걸 빼고 N 번째 아이템을 넣느냐 마느냐 선택하는 것)

추가로 좀 더 이야기 하면,

Unbounded Knapsack Problem 이라면,

D는 1차원 배열로 충분하다.

나머지 2가지의 경우도 D[n]번째 계산과정까지 오면, D[n-2]이하는 필요 없으므로,

잘 작성한다면 1차원 배열 2개로도 구현이 가능하다.