[기본과정, 3단계]

접속을 축하합니다^^

이번 단계는 가장 어렵고 중요한 3단계입니다.

암기하면 실수하는 것입니다.


3-1. n!-순환알고리즘

#include<stdio.h>
int f(int p)
{
    if(p==1) return 1;
    
    int u;
    u = p*f(p-1);
    return u;
}
int main()
{
    int n,k;
    
    scanf("%d",&n);
    k=f(n);
    printf("k=%d\n",k);
    
    return 0;
} 




3-2. 피보나치수열-순환알고리즘

#include<stdio.h>
int f(int p)
{
    if(p==1 || p==2) return 1;
    return f(p-1)+f(p-2);
}
int main()
{
    int n,k ;
    
    scanf("%d",&n);
    k=f(n);
    printf("%d\n",k);
    
    return 0;
}



3-3. 2진수 구하기-순환알고리즘

#include<stdio.h>
int f(int p)
{
    if(p==0) return 0;
    f(p/2);
    printf("%d",p%2);
    return 0;
}
int main()
{
    int n;
    scanf("%d",&n);
    f(n);
    printf("\n");
    return 0;
}



3-4. 2진트리-순환알고리즘

#include<stdio.h>
int n;
int f(int p)
{
    if(p>n) return 0;

    f(p*2);
    printf("%d ",p);
    f(p*2+1);
    return 0;
}
int main()
{
    scanf("%d",&n);
    f(1);
    printf("\n");
    return 0;
}



3-5. 2진 트리 깊이
(intput)
1 2 4 7 -1 -1 8 -1 -1 -1 3 5 -1 -1 6 -1 -1
(output)
4 1 3
4

#include<stdio.h>
int count[3],ans;

int dfs(int d)
{
	int v,cnt=0;
	
	scanf("%d",&v);
	if(v==-1) return 0;
	if(ans < d) ans = d;
	cnt += dfs(d+1);
	cnt += dfs(d+1);
	++count[cnt];
	
	return 1;	
}

int main()
{
	dfs(1);
	for(int i=0; i<3; i++)printf("%d ",count[i]);
	printf("\n%d\n",ans);
	
	return 0;
}




3-6. 2진 트리-순환알고리즘
(intput)
1 2 4 7 -1 -1 8 -1 -1 -1 3 5 -1 -1 6 -1 -1
(output)
-1 7 -1 4 -1 8 -1 2 -1 1 -1 5 -1 3 -1 6 -1
-1 -1 7 -1 -1 8 4 -1 2 -1 -1 5 -1 -1 6 3 1


#include<stdio.h>
int N, num[1004], left[1004], right[1004];

int dfs()
{
	int v;
	
	scanf("%d", &v);
	if(v==-1) return 0;
	int n=++N, k;
	num[n]=v;
	if(k=dfs()) left[n]=k;
	if(k=dfs()) right[n]= k;
	
	return n;
}

int in(int n)
{
	if(!n){printf("-1 ");return 0;}
	in(left[n]);
	printf("%d ",num[n]);
	in(right[n]);
	
	return 0;
}

int pos(int n)
{
	if(!n){printf("-1 ");return 0;}
	pos(left[n]);
	pos(right[n]);
	printf("%d ",num[n]);
	return 0;
}

int main()
{
	dfs();
	in(1); puts("");
	pos(1); puts("");
	return 0;
}



3-7. 무한 이진 트리
(intput)
17 73
(output)
4 6

#include<stdio.h>
int L,R;

int f(int a, int b)
{
	if(a==1 && b == 1) return 0;
	if(a == 1){
		R += b-1;
		return 0;
	}
	if(b==1){
		L += a-1;
		return 0;
	}
	if(a > b){
		L += a/b;
		f(a%b, b);
	}
	if(a < b){
		R += b/a;
		f(a, b%a);
	}
}

int main()
{
	int a,b;
	
	scanf("%d %d",&a, &b);
	f(a,b);
	printf("%d %d\n",L,R);
	
	return 0;
}



3-8. 하노이탑-순환알고리즘

#include<stdio.h>
int f(int p, int s, int e)
{
    int k;
    if(p<=0) return 0;
    
    k=6-(s+e);
    f(p-1,s,k);
    printf("%d %d %d\n",p,s,e);
    f(p-1,k,e);
    
    return 0;
}
int main()
{
    int n;
    
    scanf("%d",&n);
    f(n,1,3);
    
    return 0;
}



3-9. 부분 집합(BT)

#include<stdio.h>
int n,d[100],z[100];
int f(int p, int s)
{
    int i;
    
    if(p==n+1){
        printf("{");
        for(i=1; i<=n; i++){
            if(z[i]==1) printf("%d ",d[i]);
        }
        printf("}=%d\n",s);
        return 0;
    }
    z[p]=0;    f(p+1, s);
    z[p]=1;    f(p+1, s+d[p]);
    return 0;
}
int main()
{
    int i;
    scanf("%d",&n);
    for(i=1; i<=n; i++){
        scanf("%d",&d[i]);
    }
    f(1,0);
    return 0;
} 



3-10. 미로 찾기-dfs(BT)

#include<stdio.h>
#include<stdlib.h>
int d[101][101],n, dx[101], dy[101];
int f(int x, int y, int p)
{
    int i;
    
    if(x==n && y==n){
        dx[p]=x; dy[p]=y;
        for(i=1; i<=p; i++) printf("%d %d\n",dx[i], dy[i]);
        printf("ok!\n");
        return 0;
    }
    if(d[x][y]==1){
        dx[p]=x; dy[p]=y;
        d[x][y]=0;
        f(x-1, y, p+1);
        f(x, y-1, p+1);
        f(x+1, y, p+1);
        f(x, y+1, p+1);
        d[x][y]=1;
    }
    
    return 0;
}
int main()
{
    int i,j;
    freopen("input.txt","r",stdin);
    scanf("%d",&n);
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++){
            scanf("%d",&d[i][j]);
        }
    }
    f(1,1,0);
    return 0;
}



3-11. 중복 순열-dfs

#include<stdio.h>
int n,m,d[101];
int f(int p, int q)
{
    int i,j;
    
    if(q>=m){
        for(j=1; j<=m; j++)printf("%d ",d[j]);
        printf("\n");
        return 0;
    }
    for(i=1; i<=n; i++){
        d[q+1]=i;
        f(i,q+1);
    }
    return 0;
}

int main()
{
    scanf("%d %d",&n, &m);
    f(0,0);
    return 0;
}




3-12. 순열-dfs

#include<stdio.h>
int n,m,d[101],z[101];
int f(int p, int q)
{
    int i,j;
    
    if(q>=m){
        for(j=1; j<=m; j++)printf("%d ",d[j]);
        printf("\n");
        return 0;
    }
    for(i=1; i<=n; i++){
        if(z[i]==0){
            z[i]=1;
            d[q+1]=i; f(i,q+1);
            z[i]=0;
        }
    }
    return 0;
}

int main()
{
    scanf("%d %d",&n, &m);
    f(0,0);
    return 0;
}



3-13. 조합-dfs

#include<stdio.h>
int n,m,d[101];
int f(int p, int q)
{
    int i,j;
    
    if(q>=m){
        for(j=1; j<=m; j++)printf("%d ",d[j]);
        printf("\n");
        return 0;
    }
    for(i=p+1; i<=n; i++){
        d[q+1]=i; f(i,q+1);
    }
    return 0;
}

int main()
{
    scanf("%d %d",&n, &m);
    f(0,0);
    return 0;
}



3-14. 중복조합-dfs

#include<stdio.h>
int n,m,d[101];
int f(int p, int q)
{
    int i,j;
    
    if(q>=m){
        for(j=1; j<=m; j++)printf("%d ",d[j]-(j-1));
        printf("\n");
        return 0;
    }
    for(i=p+1; i<=n; i++){
        d[q+1]=i; f(i,q+1);
    }
    return 0;
}

int main()
{
    scanf("%d %d",&n, &m);
    n=n+m-1;
    f(0,0);
    return 0;
}





3-15. 퀵정렬(1단계 분할 정복)

(프로그램)
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int d[100];
int f(int s, int e)
{
    int ss,ee,t;
    
    if(s>=e) return 0;
    while(1)
    {
        ss=s+1; ee=e;
        while(d[s]>=d[ss] && ss <= e)ss++;
        while(d[s]<=d[ee] && ee > s)ee--;
        if(ss>=ee)break;
        t=d[ss]; d[ss]=d[ee]; d[ee]=t;
    }
    t=d[s]; d[s]=d[ee];d[ee]=t;
    f(s, ee-1);
    f(ee+1, e);   
   
    return 0;
}
int main()
{
    int i,n;
    srand(time(0));

    scanf("%d",&n);
    for(i=1; i<=n; i++){
        d[i]=rand()%100;
    }

    for(i=1; i<=n; i++)printf("%d ",d[i]);   
    printf("\n\n");
   
    f(1,n);

    for(i=1; i<=n; i++)printf("%d ",d[i]);   
    printf("\n");

    return 0;
}



3-16.2진트리-비순환알고리즘

2진트리 전위
#include<stdio.h>
int s[1004];
int main()
{
	int n,sp=0,nl,nr;

	scanf("%d",&n);
	sp++; s[sp]=1;
	while(1){
	        printf("%d ",s[sp]);
		nl=s[sp]*2; nr=s[sp]*2+1; sp--;
		if(nr<=n){sp++; s[sp]=nr;}
		if(nl<=n){sp++; s[sp]=nl;}
		if(sp==0)break;
	}
	cout << endl;
	return 0;
}

2진트리 중위
#include<stdio.h>
int s[1004]; bool d[1004];
int main()
{
	int n,sp=0,nl,nr; 

	scanf("%d",&n);
	sp++; s[sp]=1;
	memset(d,0,sizeof(d));
	while(1){
		if(d[s[sp]]==0){
			nl=s[sp]*2; d[s[sp]]=1;
			if(nl <= n){
				sp++; s[sp]=nl;
			}
		}else{
			printf("%d ",s[sp]);
			nr=s[sp]*2+1; sp--;
			if(nr<=n){
				sp++; s[sp]=nr;
			}
		}
		if(sp==0)break;
	}
	
	return 0;
}

2진트리 후위
#include<stdio.h>
int s[1004]; bool d[1004];
int main()
{
	int n,sp=0,a,nl;

	scanf("%d",&n);
	sp++; s[sp]=1;
	while(1){
		if(d[s[sp]]==0){
			nl=s[sp]*2; d[s[sp]]=1;
			if(nl<=n){sp++; s[sp]=nl;}
		}
		else {
			printf("%d ",s[sp]);			
			a=s[sp]; sp--;
			if(a%2==0){
				if(a+1<=n){sp++; s[sp]=a+1;}
			}
		}
		if(sp==0)break;
	}
	
	return 0;
}





3-17. 색종이 만들기(2단계 분할 정복)


#include<stdio.h>

int a[200][200];
int blue, white;

int f(int x, int y, int p)
{
	int b=0, w=0,i,j;
	
	for (i=x;i<x+p;i++){
		for (j=y;j<y+p;j++){
			if (a[i][j]==1) b++; 
			else w++;
		}
	}
	if (b==0) {white++; return 0;}
	if (w==0) {blue++; return 0;}
	f(x, y, p/2);
	f(x, y+p/2, p/2);
	f(x+p/2, y, p/2);
	f(x+p/2, y+p/2, p/2);
	
	return 0;
}

int main()
{
	int n,i,j;

	scanf("%d",&n);
	for (i=0;i<n;i++){
		for (j=0;j<n;j++){
			scanf("%d",&a[i][j]);
		}
	}

	f(0,0,n);

	printf("%d\n", white);
	printf("%d\n", blue);
	
	return 0;
}



3-18. 여왕문제(BT)

#include<stdio.h>

int qq[100];
int n;
int bound(int pp)
{
    int i;
    for(i=1; i<pp; i++){
        if(qq[pp] == qq[i]) return 0;
        if(pp+qq[pp] == i+qq[i]) return 0;
        if(pp-qq[pp] == i-qq[i]) return 0;
    }
    return 1;
}
int q(int p)
{
    int i, k;
    if(p>n){
        for(k=1; k<=n; k++) printf("(%d %d)", k, qq[k]);
        printf("\n");
        return 0;
    }
    for(i=1; i<=n; i++){
        qq[p]=i;
        if(bound(p)) q(p+1);
    }
    return 0;
}
int main()
{
    scanf("%d", &n);
    q(1);
   
    return 0;
}