딩코딩 : Computer Science 블로그

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
using namespace std;

int data[10], tmp[10];

void divide(int lt, int rt){
	int mid, p1, p2, p3;
	if(lt<rt){
		mid = (lt+rt)/2;
		divide(lt, mid);
		divide(mid+1, rt);
		p1=lt;
		p2=mid+1;
		p3=lt;
		while(p1<=mid && p2<=rt){
			if(data[p1]<data[p2]) tmp[p3++]=data[p1++];
			else tmp[p3++]=data[p2++];
		}
		while(p1<=mid){
			tmp[p3++]=data[p1++];
		}
		while(p2<=rt){
			tmp[p3++]=data[p2++];
		}			
		for(int i=lt; i<=rt; i++){
			data[i] = tmp[i];
		}
		
		
	}
		
}


int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n, i;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&data[i]);
	}
	divide(1,n);
	for(i=1;i<=n;i++){
		printf("%d",data[i]);
	}
	return 0;
	
	
	return 0;	
}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
using namespace std;

int n,ch[20];

//후위순회 출력 
void D(int L){
	if(L==n+1){
		for(int i=1; i<=n; i++){
			if(ch[i]==1) printf("%d ",i);
		}
		printf("\n");
	}
	else{
		ch[L]=1;
		D(L+1);
		
		ch[L]=0;
		D(L+1);	
	}
}

int main() {
	//freopen("input.txt.txt","rt",stdin);
	scanf("%d",&n);
	D(1);

	return 0;	
}

부분집합 찾기

-----

활용

합이 같은 부분집합 찾기

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
using namespace std;

int n,arr[11],ch[20],sum;
bool already_yes = false;
void DFS(int x){
	if(already_yes) return;
	if(x==n + 1){
		int half = 0;
		for(int i=1; i<=n; i++){
			if(ch[i]==1){
				half+=arr[i];
				
				//printf("%d ",arr[i]);
			}
		}
		//printf("\n");
		if(sum==2*half){
			printf("YES");
			already_yes = true;
			return;
		}
	}	
	else{
		ch[x] = 1;
		DFS(x+1);
		
		ch[x] = 0;
		DFS(x+1);
	
	}
}

int main() {
	//freopen("input.txt.txt","rt",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d", &arr[i]);
		sum+=arr[i];
	}
	
	DFS(1);
	if(!already_yes) printf("NO");

	return 0;	
}

매개변수를 이용해 간결하게 표현할 수 있다

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
using namespace std;

int n,a[11],total=0;
bool end;
void DFS(int L,int sum){
	if(end) return;
	if(L==n+1){
		if(sum*2 == total){
			printf("YES");
			end = true;
		}
	}
	else{
		DFS(L+1, sum+a[L]);	
		DFS(L+1, sum);
	}
}

int main() {
	//freopen("input.txt.txt","rt",stdin);
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d", &a[i]);
		total+=a[i];
	}
	DFS(1,0);


	if(!end) printf("NO");
	return 0;	
}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>

using namespace std;


//후위순회 출력 
void D1(int v){
	if(v>7) return;
	else{
		D1(v*2);
		D1(v*2+1);	
		printf("%d ", v);
	}
}

// 전위순회 출력  
void D2(int v){
	if(v>7) return;
	else{
		printf("%d ", v);
		D2(v*2);
		D2(v*2+1);	
	}
}

// 중위순회 출력  
void D3(int v){
	if(v>7) return;
	else{
		D3(v*2);
		printf("%d ", v);
		D3(v*2+1);	
	}
}

int main() {
	//freopen("input.txt.txt","rt",stdin);
	D1(1);
	printf("\n");
	D2(1);
	printf("\n");
	D3(1);
	printf("\n");
	return 0;	
}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>

using namespace std;

void recur(int x){
	if(x==0) return;
	recur(x/2);
	printf("%d", x%2);
}
int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n;
	scanf("%d", &n);
	recur(n);
	
	return 0;	
}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>

using namespace std;


int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n,i,arr[31],order=1,pos=1,cnt=0;
	scanf("%d", &n);
	for(i=1;i<=n;i++){
		scanf("%d", &arr[i]);
	}
	stack<int> s;
	string ans = "";
	for(i=1;i<=n;i++){
		s.push(arr[i]);
		ans+='P';
		
		while(!s.empty()&&s.top()==order){
			ans+='O';
			order++;
			s.pop();
		}
	}
	
	if(s.empty()) printf("%s\n",ans.c_str());
	else printf("impossible\n");

	return 0;	
}

기차 교차로 문제

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n,k,i;
	scanf("%d %d", &n, &k);
	vector<int> v;
	
	
	while(n>0){
		v.push_back(n%k);
		n = n/k;
	}	
	for(i=v.size()-1; i>=0; i--){
		if(v[i]>=10){
			printf("%c", ('A'+(v[i]-10)));
		}
		else printf("%d",v[i]);
	}
	
	return 0;	
}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

int stack[100], top=-1;
void push(int x){
	stack[++top] = x;
}
int pop(){
	return stack[top--];
}

int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n,k,i;
	scanf("%d %d", &n, &k);
	char str[20]="0123456789ABCDEF";
	while(n>0){
		push(n%k);
		n = n/k;
	}
	while(top!=-1){
		printf("%c",str[pop()]);
	}
	
	return 0;	
}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

int a[1501];
int main() {
	//freopen("input.txt.txt","rt",stdin);
	int n, i, p2, p3, p5, min=INT_MIN;
	scanf("%d",&n);
	a[1]=1;
	p2=p3=p5=1;
	for(i=2; i<=n; i++){
		if(a[p2]*2 < a[p3]*3) min=a[p2]*2;
		else min=a[p3]*3;
		if(a[p5]*5<min) min=a[p5]*5;
		if(a[p2]*2==min) p2++;
		if(a[p3]*3==min) p3++;
		if(a[p5]*5==min) p5++;
		a[i] = min;
	}
	printf("%d",a[n]);
	
	
	return 0;	
}

1. ceil() 사용

2. int a = 46.7 + 0.5

a == 47

0.5를 더하고 int 자료형에 넣어주면 반올림된다.

46.2 + 0.5 --> 46