http://www.tomkleinpeter.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/ 

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이다.
단점이라면, 당연히 숫자만 된다는 점이다.
#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;
} 



#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);
}

#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);
}



#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);  
}


#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;
}


//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);
}


#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);
}

#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);
}

+ Recent posts

티스토리툴바