Algorithm
- Consistenct Hashing 2012.09.10
- temp 변수 사용하지 않고 숫자 바꾸기(swap) 2009.11.28 2
- 다익스트라 - 최단경로 2009.07.29
- 스택에의한RPN변환 2009.07.29
- 백트래킹 - 미로 2009.07.29
- 부분집합의 합 2009.07.29
- 장기판에 상놓기 - 가지수 2009.07.29
- 퀸문제 2009.07.29
- 해밀튼의 회로 2009.07.29
- 오일러 순환로 2009.07.29
Consistenct Hashing
2012. 9. 10. 15:44
temp 변수 사용하지 않고 숫자 바꾸기(swap)
2009. 11. 28. 19:13
void Swap(int* a, int* b) { int temp; temp=*a; *a=*b; *b=temp; }
이것이 내가 늘상 쓰던 swap방법이다.
임시 저장 변수가 꼭 필요하다.
void Swap(int* a, int* b) { *a = *a + *b; *b = *a - *b; *a = *a - *b; }
원래 있던 두값을 더해서 한 값을 빼주면 나머지 한값이 나오는것을 이용해서,
임시 저장 변수가 필요없는 swap이다.
단점이라면, 당연히 숫자만 된다는 점이다.
다익스트라 - 최단경로
2009. 7. 29. 21:14
#include <stdio.h> //using namespace std; int main() { int i,j,k,s,e,min,n=8; int path[8],path_cnt=0; // unconnect const int U=static_cast<unsigned int>(-1)/2; int data[8][8] = { {0,2,U,U,U,3,U,U}, {2,0,4,1,U,U,U,U}, {U,4,0,U,3,U,U,U}, {U,1,U,0,3,U,2,U}, {U,U,3,3,0,U,U,4}, {3,U,U,U,U,0,6,U}, {U,U,U,2,U,6,0,4}, {U,U,U,U,4,U,4,0}}; bool v[8]; int distance[8],via[8]; // 출발, 도착 정점 s=0,e=7; // 초기화 for(i=0;i<n;i++) { v[i]=false; distance[i]=U; } distance[s]=0; // 찾기 for(i=0;i<n;i++) { min=U; for(j=0;j<n;j++) { if(v[j]==false && distance[j]<min) { k=j; min=distance[j]; } } v[k]=true; if(min==U) break; for(j=0;j<n;j++) { if(distance[k]==U || data[k][j]==U) continue; if(distance[j]>distance[k]+data[k][j]) { distance[j]=distance[k]+data[k][j]; via[j]=k; } } } // 최단 비용 printf("%d\n",distance[e]); // 최단 경로 k=e; while(true) { path[path_cnt++]=k; if(k==s) break; k=via[k]; } for(i=path_cnt-1;i>=1;i--) printf("%d -> ",path[i]); printf("%d\n",path[i]); return 0; }
스택에의한RPN변환
2009. 7. 29. 21:12
#include<stdio.h> #include<stdlib.h> #include<string.h> #define MAX 150 FILE *fp,*fp1; main(){ int i,j,k,m,n,s_top,len,o_i; char stack[MAX]; char output[MAX]; int imp[MAX]; char sik[MAX]; fp=fopen("input.txt","r"); fp1=fopen("output.txt","w"); fscanf(fp,"%s",sic); len=strlen(sic); for(i=(int)'0';i<=(int)'9';i++) imp[i]=5; imp[(int)'(']=3; imp[(int)'<']=2; imp[(int)'>']=2; imp[(int)'%']=1; imp[(int)')']=0; for(i=0,s_top=-1,o_i=-1;i<len;i++){ if(imp[(int)sik[i]]==5) output[++o_i]=sik[i]; else{ switch(imp[(int)sik[i]]){ case 3: stack[++s_top]=sik[i]; break; case 2: if(imp[(int)stack[s_top]]>=imp[(int)sik[i]]){ while(imp[(int)stack[s_top]]>=imp[(int)sik[i]]) output[++o_i]=stack[s_top--]; } else stack[++s_top]=sik[i]; break; case 1: if(imp[(int)stack[s_top]]>=imp[(int)sik[i]]){ while(imp[(int)stack[s_top]]>=imp[(int)sik[i]]) output[++o_i]=stack[s_top--]; } else stack[++s_top]=sik[i]; break; fprintf(fp1,"Impossible\n"); fclose(fp); fclose(fp1); }
백트래킹 - 미로
2009. 7. 29. 21:10
#include<stdio.h> int miro[10][10],chk[11][11]={0},path[100][2]; int maxpath[100][2],minpath[100][2]; int max=-9999,min=9999; int row,col,st_x,st_y,maxcnt,mincnt,maxsum,minsum; FILE *fp,*fp1; void back(int x,int y,int sum,int cnt){ int i,j; path[cnt][0]=x; path[cnt][1]=y; chk[x][y]=1; if(x==row && y==col){ if(sum>max){ for(i=1;i<=cnt;i++){ maxpath[i][0]=path[i][0]; maxpath[i][1]=path[i][1]; } max=sum; maxcnt=cnt; } else if(sum<min){ for(i=1;i<=cnt;i++){ minpath[i][0]=path[i][0]; minpath[i][1]=path[i][1]; } min=sum; mincnt=cnt; } chk[x][y]=0; } else{ if(!chk[x][y+1]) back(x,y+1,miro[x][y+1]+sum,cnt+1); if(!chk[x+1][y]) back(x+1,y,miro[x+1][y]+sum,cnt+1); if(!chk[x][y-1]) back(x,y-1,miro[x][y-1]+sum,cnt+1); if(!chk[x-1][y]) back(x-1,y,miro[x-1][y]+sum,cnt+1); chk[x][y]=0; } } main(){ int i,j; fp=fopen("input.txt","r"); fp1=fopen("output.txt","w"); fscanf(fp,"%d %d",&row,&col); for(i=1;i<=row;i++){ for(j=1;j<=col;j++){ fscanf(fp,"%d",&miro[i][j]); } } fscanf(fp,"%d %d",&st_x,&st_y); for(i=0;i<=row+1;i++){ for(j=0;j<=col+1;j++){ if(i==0 || i==row+1 || j==0 || j==col+1) chk[i][j]=1; } } back(st_x,st_y,miro[st_x][st_y],1); fprintf(fp1,"최대경로:"); for(i=1;i<=maxcnt;i++) fprintf(fp1,"(%d,%d)",maxpath[i][0],maxpath[i][1]); fprintf(fp1,"\n최대합 : %d\n",max); fprintf(fp1,"최소경로:"); for(i=1;i<=mincnt;i++) fprintf(fp1,"(%d,%d)",minpath[i][0],minpath[i][1]); fprintf(fp1,"\n최소합 : %d\n",min); }
부분집합의 합
2009. 7. 29. 21:08
#include <iostream> #include <fstream> #include <string> using namespace std; ifstream fin("input.txt"); ofstream fout("output.txt"); int a[5]={5,6,10,11,16},check[100]={0}; //오름차순 정렬된 데이터. int n=5,find=21; //n원소의 수, find 목표 수 void subsum(int p,int s){ int promising; promising= (p<=n) && (s==find || s+a[p]<=find); //promising 유망 판별 변수, 가지치기 if(promising){ if(s==find){ for(int i=0;i<n;i++){ if(check[i]) cout << a[i] << " "; } cout << endl; } else{ check[p]=1; subsum(p+1,s+a[p]); //현재 a[p]를 포함시키고 호출 check[p]=0; subsum(p+1,s); // 포함시키지 않고 호출 } } } void main(){ subsum(0,0); }
장기판에 상놓기 - 가지수
2009. 7. 29. 21:07
#include <iostream> #include <fstream> #include <string> using namespace std; ifstream fin("input.txt"); ofstream fout("output.txt"); int chky[8]={2,3,3,2,-2,-3,-3,-2}; int chkx[8]={3,2,-2,-3,-3,-2,2,3}; int chkt[8][8]={0}; int cnt=0,row,col; void janggi(int p,int k){ if(p>=row){ cnt++; } else{ for(int i=0;i<col;i++){ int flag=1; if(chkt[p][i]) flag=0; if(flag){ for(int j=0;j<8;j++){ if(p+chkx[j]>=0 && p+chkx[j]< row && i+chky[j]>=0 && i+chky[j]< col) if(chkt[p+chkx[j]][i+chky[j]]==0) chkt[p+chkx[j]][i+chky[j]]=p+1; } janggi(p+1,i); for(j=0;j<8;j++){ if(p+chkx[j]>=0 && p+chkx[j]< row && i+chky[j]>=0 && i+chky[j]< col) if(chkt[p+chkx[j]][i+chky[j]]==p+1) chkt[p+chkx[j]][i+chky[j]]=0; } } } } } void main(){ fin >> row >> col; janggi(0,0); fout << cnt; }
퀸문제
2009. 7. 29. 21:05
//1차원 배열 이용, 가지치기 & 백트래킹. 8 Queen.변경가능. #include <iostream> #include <fstream> #include <string> using namespace std; ifstream fin("input.txt"); ofstream fout("output.txt"); int n,cnt=0; int colc[20],ruc[20],luc[20],Q[8]={0}; void queen(int p){ if(p>=n){ cout << "[" << ++cnt << "]th" << endl; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(Q[i]==j) cout << "Q"; else cout << "#"; } cout << endl; } cout << endl; } else{ for(int j=0;j<n;j++){ if(colc[j]==0 && ruc[p+j]==0 && luc[p-j+n]==0){ Q[p]=j; colc[j]=ruc[p+j]=luc[p-j+n]=1; queen(p+1); colc[j]=ruc[p+j]=luc[p-j+n]=0; } } } } void main(){ n=8; for(int i=0;i<n*2;i++){ colc[i]=ruc[i]=luc[i]=0; } queen(0); }
해밀튼의 회로
2009. 7. 29. 21:03
#include <iostream> #include <fstream> #include <string> using namespace std; ifstream fin("input.txt"); ofstream fout("output.txt"); int a[8][8]={{0,1,0,1,0,1,0,0}, {1,0,1,0,0,0,1,0}, {0,1,0,1,0,0,0,1}, {1,0,1,0,1,0,0,0}, {0,0,0,1,0,1,0,1}, {1,0,0,0,1,0,1,0}, {0,1,0,0,0,1,0,1}, {0,0,1,0,1,0,1,0}}; int node,start,index,check[30],cycle[30]; void hamilton(int i,int index){ cycle[index]=i; check[i]=1; if(index == node-1 && a[i][start]==1){ for(int j=0;j<node;j++) cout << cycle[j]+1 << " "; cout << endl; } else{ for(int j=0;j<node;j++){ if(a[i][j]==1 && check[j]==0){ hamilton(j,index+1); check[j]=0; } } } } void main(){ node=8; start=0; hamilton(start,0); }
오일러 순환로
2009. 7. 29. 21:02
#include <iostream> #include <fstream> #include <string> using namespace std; ifstream fin("input.txt"); ofstream fout("output.txt"); int a[6][6]={{0,1,1,0,1,1}, {1,0,3,1,0,1}, {1,3,0,1,1,0}, {0,1,1,0,1,1}, {1,0,1,1,0,1}, {1,1,0,1,1,0}}; int node, edge, start, cycle[30]; void euler(int i,int index){ cycle[index]=i; if(index == edge && i==start){ //i==start 생략시 오일러 경로 for(int j=0;j<edge+1;j++) cout << cycle[j]+1 << " "; cout << endl; } else{ for(int j=0;j<node;j++){ if(a[i][j]>0){ a[i][j]--; a[j][i]--; euler(j,index+1); a[i][j]++; a[j][i]++; } } } } void main(){ node=6; edge=14; start=0; euler(start, 0); }