#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.07.29
- 장기판에 상놓기 - 가지수 2009.07.29
- 퀸문제 2009.07.29
- 해밀튼의 회로 2009.07.29
- 오일러 순환로 2009.07.29
- 퀵소트-파레토의법칙 2009.07.29
- 하노이의 탑 2009.07.29
- 템플릿 2009.07.28
- 엑셀 창 여러개 띄우기 2009.07.14
- 리눅스 rsync 사용법 2009.07.01
부분집합의 합
2009. 7. 29. 21:08
장기판에 상놓기 - 가지수
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); }
퀵소트-파레토의법칙
2009. 7. 29. 21:01
#include <iostream> #include <stdlib.h> #include <time.h> #include <fstream> #include <string> using namespace std; ifstream fin("input.txt"); ofstream fout("output.txt"); int a[100000],n; int quick(int low,int high){ int m,i,j,t,pivot; if(high-low>5) m=low+rand()%(high-low+1); else m=(int)((low+high)/2); pivot=a[m]; if(low < high){ i=low-1; j=high+1; while(1){ do{ i++; }while(pivot>a[i]); do{ j--; }while(pivot<a[j]); if(i>j) break; else{ t=a[i]; a[i]=a[j] ; a[j]=t; } } } return m; } main(){ int i,k,low,high,s; srand(time(NULL)); fin >> n; for(i=0;i<n;i++) fin >> a[i]; low=0; high=n-1; s=int(n*0.2+0.5); while(1){ k=quick(low,high); int m,i,j,t,pivot; if(high-low>5) m=low+rand()%(high-low+1); else m=(int)((low+high)/2); pivot=a[m]; if(low < high){ i=low-1; j=high+1; while(1){ do{ i++; }while(pivot>a[i]); do{ j--; }while(pivot<a[j]); if(i>j) break; else{ t=a[i]; a[i]=a[j] ; a[j]=t; } } } if(m==n-s) break; else if(m>n-s) high=m-1; else low=m+1; } fout << a[n-s] << endl; }
하노이의 탑
2009. 7. 29. 20:58
#include <iostream> #include <fstream> #include <string> using namespace std; ifstream fin("input.txt"); ofstream fout("output.txt"); int cnt; void hanoi(int n,char a,char b,char c){ cnt++; if(n>0){ hanoi(n-1,a,b,c); cout << n << "번째 판을"<< a << " ---> " << c << endl; hanoi(n-1,b,a,c); } } main(){ int n; cnt=0; n=3; hanoi(n,'A','B','C'); printf("%d\n",cnt); } /* //다른방법 int m=0; void hanoi(int n,int a,int b){ if(n>0){ hanoi(n-1,a,6-a-b); m++; cout << m << "번째 판을"<< a << " ---> " << b << endl; hanoi(n-1,6-a-b,b); } } main(){ int n; n=3; hanoi(n,1,3); } */
템플릿
2009. 7. 28. 17:55
회사에서 발표자료 - 템플릿
엑셀 창 여러개 띄우기
2009. 7. 14. 09:33
리눅스 rsync 사용법
2009. 7. 1. 18:31
man rsync 의 USAGE 만 번역
rcp 사용법과 유사합니다. 반드시 대상과 목적지를 적어야 하며 둘 중 하나는 원격일 수 있습니다.
아마도 설명하기 가장 좋은 방법은 아래의 예를 드는 것일 겁니다.
rsync -t *.c foo:src/
이 예제는 *.c 패턴과 일치하는 모든 파일을 현재의 디렉토리로 부터 foo 머신으로 전송합니다.
원격 시스템에 이미 같은 파일이 존재한다면 rsync remote-update 프로토콜은 비교해서 같은 파일은 전송하지 않습니다. 좀 더 자세하게 다음 예제를 보죠.
rsync -avz foo:src/bar /data/tmp
이 방법은 재귀적으로 foo머신에 src/bar 디렉토리의 모든 파일을 로컬머신의 /data/tmp/bar 디렉토리로 전송합니다. 파일들은 "archive" 모드로 전송이 됩니다. 이것은 링크, 장치, 속성, 허가, 소유자, 기타. 등등이 전송에 보장이 됩니다. 추가적으로, 압축은 전송 데이터 크기를 줄여주는데 사용이 되어 집니다.
rsync -avz foo:src/bar/ /data/tmp
대상위치에 붙은 / 는 "이름으로 디렉토리를 복사"가 아닌 "이 디렉토리의 내용물을 복사"라는 의미로 사용됩니다.
rsync -av /src/goo /dest
rsync -av /src/foo/ /dest/foo
한마디로 위에 2개의 의미가 같다는 뜻입니다.
또한 명심할 것은, 호스트와 모듈 참조는 디렉토리 뒤에 / 표시를 필요로 하지 않습니다.
예를 들면, 아래방법 둘 모두 원격 디렉토리의 내용물을 "/dest"에 복사합니다.
rsync -av host: /dest
rsync -av host::module /dest
물론 로컬전용 모드로 rsync를 사용할 수도 있습니다. ':' 표시가 필요하지 않겠죠.
이경우는 마치 향상된 copy 명령어로 행동합니다.
번역이 개판이네 ㅠ,,,, 다듬어야지 ㅠ
rcp 사용법과 유사합니다. 반드시 대상과 목적지를 적어야 하며 둘 중 하나는 원격일 수 있습니다.
아마도 설명하기 가장 좋은 방법은 아래의 예를 드는 것일 겁니다.
rsync -t *.c foo:src/
이 예제는 *.c 패턴과 일치하는 모든 파일을 현재의 디렉토리로 부터 foo 머신으로 전송합니다.
원격 시스템에 이미 같은 파일이 존재한다면 rsync remote-update 프로토콜은 비교해서 같은 파일은 전송하지 않습니다. 좀 더 자세하게 다음 예제를 보죠.
rsync -avz foo:src/bar /data/tmp
이 방법은 재귀적으로 foo머신에 src/bar 디렉토리의 모든 파일을 로컬머신의 /data/tmp/bar 디렉토리로 전송합니다. 파일들은 "archive" 모드로 전송이 됩니다. 이것은 링크, 장치, 속성, 허가, 소유자, 기타. 등등이 전송에 보장이 됩니다. 추가적으로, 압축은 전송 데이터 크기를 줄여주는데 사용이 되어 집니다.
rsync -avz foo:src/bar/ /data/tmp
대상위치에 붙은 / 는 "이름으로 디렉토리를 복사"가 아닌 "이 디렉토리의 내용물을 복사"라는 의미로 사용됩니다.
rsync -av /src/goo /dest
rsync -av /src/foo/ /dest/foo
한마디로 위에 2개의 의미가 같다는 뜻입니다.
또한 명심할 것은, 호스트와 모듈 참조는 디렉토리 뒤에 / 표시를 필요로 하지 않습니다.
예를 들면, 아래방법 둘 모두 원격 디렉토리의 내용물을 "/dest"에 복사합니다.
rsync -av host: /dest
rsync -av host::module /dest
물론 로컬전용 모드로 rsync를 사용할 수도 있습니다. ':' 표시가 필요하지 않겠죠.
이경우는 마치 향상된 copy 명령어로 행동합니다.
번역이 개판이네 ㅠ,,,, 다듬어야지 ㅠ