동적 계획법에서 필요로 되는
reference transparency 및 최적 부분 조건이 성립해야한다.
최적 부분 조건이 성립하도록 점화식을 만들어야한다.
Quantization (Need Improv.) 버전은 이부분을 고려하지 않은 알고리즘으로 보임.
동적 계획법에서 필요로 되는
reference transparency 및 최적 부분 조건이 성립해야한다.
최적 부분 조건이 성립하도록 점화식을 만들어야한다.
Quantization (Need Improv.) 버전은 이부분을 고려하지 않은 알고리즘으로 보임.
/**
* Quantization => k-mean?
*/
//#define N 10
//int input[N]={3,3,3,1,2,3,2,2,2,1};
#define S 34
#define N 36
int input[N]={1,744,755,4,897,902,890,6,777,1,744,755,4,897,902,890,6,777,1,744,755,4,897,902,890,6,777,1,744,755,4,897,902,890,6,777};
int pow2(int n){
return n*n;
}
int minError(int s, int e){
if(s==e){
return 0;
}
bool oneNumber = true;
for(int i=s;i<e;i++){
if(input[i]!=input[i+1]){
oneNumber =false;
break;
}
}
if(oneNumber){
return 0;
}
float mean = 0;
for(int i=s;i<=e;i++){
mean +=input[i];
}
mean = (mean/(float)((e-s)+1.0f));
mean +=0.5f;
int error=0;
for(int i=s;i<=e;i++){
error += pow2((int)mean-input[i]);
}
return error;
}
void sort(){
for(int i=0;i<N;i++){
for(int j=0;j<=i;j++){
if(input[j] > input[i]){
int t = input[j];
input[j] = input[i];
input[i]=t;
}
}
}
}
int parent[S];
//minError(s,e) 의 s,e 가 무엇이 되어야 최소가 될까? s,e 는 0~N-1까지임
//0~9 S \0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0개로 나누는데 가장 작은 minError 를 주는 것.
//모든 부분 조합 완전 탐색
int n=0;
int min=-1;
int minSum(int depth){
n++;
if(depth == S-1){
int sum=0;
for(int i=0;i<S-1;i++){
sum += minError(parent[i],parent[i+1]-1);
}
sum+=minError(parent[depth],N-1);
return sum;
}
for(int i=parent[depth]+1;i<N;i++){
parent[depth+1]=i;
int t=minSum(depth+1);
if(min==-1||t<min){
min = t;
}
}
return min;
}
int main(){
sort();
parent[0]=0;
printf("%d
",minSum(0));
printf("Function %d times
",n);
return 1;
}
#define N 5
int triangle[N][N]={
{ 6,-1,-1,-1,-1},
{ 1, 2,-1,-1,-1},
{ 3, 7, 4,-1,-1},
{ 9, 4, 1, 7,-1},
{ 2, 7, 5, 9, 4}
};
int cache[N][N];
int n=0;
int path1(int x, int y){
n++;
//basis
if(x==N || y>x){return 0;}
if(cache[x][y]!=-1){return cache[x][y];}
int n1 = path1(x+1,y);
int n2 = path1(x+1,y+1);
if(n1>n2){
return cache[x][y]=triangle[x][y]+n1;
}else{
return cache[x][y]=triangle[x][y]+n2;
}
}
int main(){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
cache[i][j]=-1;
}
}
printf("%d
",path1(0,0));
printf("Function called %d times
",n);
}
/**
* JumpGame
*/
#define N 7
int gameBoard[N][N]={
{2,5,1,6,1,4,1},
{6,1,1,2,2,9,3},
{7,2,3,2,1,3,1},
{1,1,3,1,7,1,2},
{4,1,2,3,4,1,2},
{3,3,1,2,3,4,1},
{1,5,2,9,4,7,-1}
};
//int gameBoard[N][N]={
// {1,1,1,1,1,1,1},
// {1,1,1,1,1,1,1},
// {1,1,1,1,1,1,1},
// {1,1,1,1,1,1,1},
// {1,1,1,1,1,1,1},
// {1,1,1,1,1,1,2},
// {1,1,1,1,1,2,-1},
//};
int n=0;
int footStep[N][N];
bool jumpGame(int x,int y){
n++;
//basis
if(x>=N || y>=N){ return false;}
if(x== N -1 && y==N-1){return true;}
if(footStep[x][y]!=-1){ return footStep[x][y];}
footStep[x][y] = jumpGame(x+gameBoard[x][y],y) || jumpGame(x,y+gameBoard[x][y]);
return footStep[x][y];
}
int main(){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
footStep[i][j]=-1;
}
}
if(jumpGame(0,0)){
printf("Reached a goal.
");
}else{
printf("Not reached a goal.
");
}
printf("Function called %d times
",n);
}