The Checkerboard Problem, Longest Common Subsequence

The Checkerboard Problem

cost table이 위와 같이 주어졌을 때, i=1에서 i=5까지 움직일 때, 최솟값을 찾는 문제이다.

 

q(i,j) : the minimum cost to reach squrare(i,j)라고 할 때,

로 식을 짜게 되면 q[i][j]에는 최소값이 선언되게 된다.

table P도 만들어서 어디서 왔는지 알려주면 된다.

#include <stdio.h>
#define N 5
#define INFTY 100000
int c[N+1][N+2] = {-1,-1,-1,-1,-1,-1,-1,
                   -1, 7, 3, 5, 6, 1,-1,
                   -1, 2, 6, 7, 0, 2,-1,
                   -1, 3, 5, 7, 8, 2, -1,
                   -1, 7, 6, 1, 1, 4, -1,
                   -1, 6, 7, 4, 7, 8, -1};
int p[N+1][N+2], q[N+1][N+2];

void ComputeCBCosts(int n){
    int i,j, m;
    
    for(i=1;i<=n;i++) q[1][i]=c[1][i];
    for(i=1;i<=n;i++){
        q[i][0]=INFTY;
        q[i][n+1]=INFTY;
    }
    for(i=2;i<=n;i++){
        for(j=1;j<=n;j++){
            m=q[i-1][j-1];
            if(m>q[i-1][j]) m=q[i-1][j];
            if(m>q[i-1][j+1]) m=q[i-1][j+1];
            q[i][j]=m+c[i][j];
            if(m==q[i-1][j-1]) p[i][j]=-1;
            else if(m==q[i-1][j]) p[i][j]=0;
            else p[i][j] = 1;
        }
    }
}

void PrintShortestPath(int n,int imin){
    printf(" (%d, %d) <-",n,imin);
    if(n==2) printf(" (%d, %d)\n",1,imin+p[n][imin]);
    else PrintShortestPath(n-1,imin+p[n][imin]);
}

void ComputeCBShortestPath(int n){
    int i,imin, m;
    ComputeCBCosts(n);
    
    imin=1;m=q[n][1];
    for(i=2;i<=n;i++){
        printf("%d ",q[n][i]);
        if(q[n][i]<m){
            imin=i;
            m=q[n][i];
        }
    }
    printf("*** The cost of the shortest path is %d.\n",q[n][imin]);
    PrintShortestPath(n,imin);
}

void main(void){
    int n;
    n=N;
    ComputeCBShortestPath(n);
}

---

Longest Common Subsequence

LCS는 두 문자열이 주어졌을 때, 가장 길게 겹치는 subsequence를 찾아야 하는 문제이다.

ex) X=<A,B,C,B,D,A,B>, Z=<B,C,D,B> LSC = <B,C,D,B> (2,3,5,7)

 

X = <x1,x2,...,xm> 그리고 Y=<y1,y2,...,yn>이라고 할 때, 마지막이 같을 때와 마지막이 다를 때, 두가지의 경우로 모든 경우를 표현할 수 있다.

 

따라서 Xm=Yn인 경우에 왼쪽 대각선에서 값을 가져오면 되고, Xm≠Yn인 경우에는 왼쪽 또는 위에서 더 큰 값을 가져오면 된다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* LCS(char* a, char* b);
#define NEITHER 0
#define UP 1
#define LEFT 2
#define UP_AND_LEFT 3

int main(int argc, char* argv[]) {
    printf("%s\n", LCS(argv[1],argv[2]));
}
char* LCS(char* a, char* b) {
    int n = strlen(a); int m = strlen(b); int** S; int** R; int ii; int jj;
    int pos; char* lcs;
    S = (int **)malloc( (n+1) * sizeof(int *) );
    R = (int **)malloc( (n+1) * sizeof(int *) );
    for (ii = 0; ii <= n; ++ii) {
        S[ii] = (int*) malloc( (m+1) * sizeof(int) );
        R[ii] = (int*) malloc( (m+1) * sizeof(int) );
    }
    for (ii = 0; ii <= n; ++ii) {
        S[ii][0] = 0; R[ii][0] = UP;
    }
    for (jj = 0; jj <= m; ++jj) {
        S[0][jj] = 0; R[0][jj] = LEFT;
    }
    for (ii = 1; ii <= n; ++ii) {
        for (jj = 1; jj <= m; ++jj) {
            if ( a[ii-1] == b[jj-1] ) {
                S[ii][jj] = S[ii-1][jj-1] + 1;
                R[ii][jj] = UP_AND_LEFT;
            }
            else {
                S[ii][jj] = S[ii-1][jj-1] + 0; R[ii][jj] = NEITHER;
            }
            if ( S[ii-1][jj] >= S[ii][jj] ) {
                S[ii][jj] = S[ii-1][jj];
                R[ii][jj] = UP;
            }
            if ( S[ii][jj-1] >= S[ii][jj] ) {
                S[ii][jj] = S[ii][jj-1];
                R[ii][jj] = LEFT;
            }
            
        }
    }
    ii = n;
    jj = m;
    pos = S[ii][jj];
    lcs = (char *) malloc( (pos+1) * sizeof(char) );
    lcs[pos--] = (char)NULL;
    while ( ii > 0 || jj > 0 ) {
        if( R[ii][jj] == UP_AND_LEFT ) {
            ii--; jj--;
            //거꾸로 넣는다
            lcs[pos--] = a[ii];
        }
        else if ( R[ii][jj] == UP ) {
            ii--;
        }
        else if ( R[ii][jj] == LEFT ) {
            jj--;
        }
    }
    for (ii = 0; ii <= n; ++ii ) {
        free(S[ii]);
        free(R[ii]);
    }
    free(S);
    free(R);
    return lcs;
}