동적계획법

동적계획법

1. 일반적으로 최적화문제(optimision problem) 혹은 카운팅(counting) 문제에 적용됨

2. 주어진 문제에 대한 순환식(recurrence equation)을 정의한다.

3. 순환식을 memoization 혹은 bottom-up 방식으로 푼다.

알고리즘의 동작 방식

1. 문제를 부분 문제로 나눈다.

2. 가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장한다.

3. 테이블에 저장되어 있는 부분 문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다.

 

subproblem들을 풀어서 원래 문제를 푸는 방식. 그런 의미에서 분할정복법과 공통성이 있다.

 

이 문제에 어떤 옵티멀 서브스트럭쳐(최적 부분해)가 존재하는가?

원래 문제의 부분 문제들의 해를 조합해서 원래 문제의 해를 어떻게 구할것인가?

이 문제에 대한 최적해의 한 부분이 그 부분에 대한 최적해인가?

 

int lcs(int m, int n)

{

for(int i=0; i<=m; I++)

    c[i][0] = 0;

for(int j=0; j<=n; j++)

    c[0][j] = 0;

for(int I=0; i<=m; I++){

for(int j=0; j<=n; j++)

{

if(x[i] == y[j])

c[i][j] = c[i-1][j-1]+1;

else

c[i][j] = Math.max(c[i-1][j], c[i][j-1]);

}

}

return c[m][n];

}

LCS 문제가 최적 부분 구조로 이루어져 있는지 확인 위한 점화식

1. 두 문자열중 하나라도 문자열 길이가 0이라면 0

2. 두 문자열의 마지막 부분이 같다면, TABLE[i, j] = TABLE[i-1, j-1]이 성립한다.

3. 두 문자열의 마지막 부분이 다르다면, TABLE[i, j] = MAX(TABLE[i-1, j],TABLE[i, j-1])

위 식을 바탕으로 알고리즘을 만든다면

아래는 풀 소스

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

typedef struct structLCSTable

{

int** Data;

}LCSTable;

int LCS(char* X, char* Y, int i, int j, LCSTable* Table)

{

int m = 0; int n = 0;

/* 아무것도 없는 행을 표현하기 위하여 0으로 초기화 */

for (m = 0; m <= i; m++)

Table->Data[m][0] = 0;

for (n = 0; n <= j; n++)

Table->Data[0][n] = 0;

for (m = 1; m <= i; m++)

{

for (n = 1; n <= j; n++)

{

if (X[m - 1] == Y[n - 1])

{

Table->Data[m][n] = Table->Data[m - 1][n - 1] +1;

}

else

{

if (Table->Data[m][n - 1] >= Table->Data[m - 1][n])

Table->Data[m][n] = Table->Data[m][n - 1];

else

Table->Data[m][n] = Table->Data[m - 1][n];

}

}

}

return Table->Data[i][j];

}

void LCS_TraceBack(char* X, char* Y, int m, int n, LCSTable* Table, char* LCS)

{

if (m == 0 || n == 0)

return;

if (Table->Data[m][n] > Table->Data[m][n - 1] && Table->Data[m][n] > Table->Data[m - 1][n] && Table->Data[m][n] > Table->Data[m - 1][n - 1])

{

char TempLCS[100];

strcpy(TempLCS, LCS);

sprintf(LCS, "%c%s", X[m - 1], TempLCS);

LCS_TraceBack(X, Y, m - 1, n - 1, Table, LCS);

}

else if (Table->Data[m][n] > Table->Data[m - 1][n] && Table->Data[m][n] == Table->Data[m][n - 1])

{

LCS_TraceBack(X, Y, m, n - 1, Table, LCS);

}

else

{

LCS_TraceBack(X, Y, m - 1, n, Table, LCS);

}

}

void LCS_PrintTable(LCSTable* Table, char* X, char* Y, int LEN_X, int LEN_Y)

{

int i = 0; int j = 0;

printf("%4s", "");

for (i = 0; i < LEN_Y + 1; i++)

printf("%c ", Y[i]);

printf("\n");

for (i = 0; i < LEN_X + 1; i++)

{

if (i == 0)

printf("%2s", "");

else

printf("%-2c", X[i - 1]);

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

{

printf("%d ", Table->Data[i][j]);

}

printf("\n");

}

}

int main(void)

{

char* X = "GOOD MORNING.";

char* Y = "GUTEN MORGEN.";

char* Result;

int LEN_X = strlen(X);

int LEN_Y = strlen(Y);

int i = 0;

int j = 0;

int Length = 0;

LCSTable Table;

Table.Data = (int**)malloc(sizeof(int*)* (LEN_X + 1));

for (i = 0; i < LEN_X + 1; i++)

{

Table.Data[i] = (int*)malloc(sizeof(int)* (LEN_Y + 1));

memset(Table.Data[i], 0, sizeof(int)* (LEN_Y + 1));

}

Length = LCS(X, Y, LEN_X, LEN_Y, &Table);

LCS_PrintTable(&Table, X, Y, LEN_X, LEN_Y);

Result = (char*)malloc(sizeof(Table.Data[LEN_X][LEN_Y] + 1));

sprintf(Result, "");

LCS_TraceBack(X, Y, LEN_X, LEN_Y, &Table, Result);

printf("\n");

printf("LCS:\"%s\" (Lenght : %d) \n", Result, Length);

return 0;

}