알못에서 잘알까지

    7번 문제   

    내가 풀이한 답   

 위의 그림과 같이 완전탐색으로 n 값에 대한 부분집합을 구할 수 있다. 해당 숫자를 포함하는 경우와 포함하지 않는 경우를 나누면 해결할 수 있다.  

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int n, check[11];

void dfs(int level){
	if(level==n+1){
		for(int i=1; i<=n; i++){
			if(check[i]==1) cout << i << " ";
		}
		cout << endl;
	}
	else {
		check[level] = 1;
		dfs(level+1);
		check[level] = 0;
		dfs(level+1);
	}
}

int main() {
	//freopen("input.txt", "rt", stdin);
	cin >> n;
	
	dfs(1);
	return 0;
}

    사이트의 답안   

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int n, ch[100];
void DFS(int L){
	int i;
	if(L==n+1){
		for(i=1; i<=n; i++){
			if(ch[i]==1) printf("%d ", i);
		}
		puts("");
	}
	else{
		ch[L]=1;
		DFS(L+1);
		ch[L]=0;
		DFS(L+1);
	}
}	
int main(){
	freopen("input.txt", "rt", stdin);
	scanf("%d", &n);
	DFS(1);
	return 0;
}

    6번 문제   

    내가 풀이한 답   

• 전위순회(Preorder): 부모노드를 먼저 방문하고 자식 노드를 방문
• 중위순회(Inorder): 왼쪽 자식을 먼저 방문하고 부모노드를 방문
• 후위순회(Postorder): 자식 노드를 먼저 방문하고 부모노드를 방문

 위의 그림과 같이 각 노드의 왼쪽에 있는 빨간색 점을 선으로 쭉 이어보면 전위순회가 완성된다. 중위순회와 후위순회도 마찬가지로 각각 초록색, 파란색 점을 선으로 이어보면 구할 수 있다.  

#include <iostream>
using namespace std;

//전위순회
void pre(int v, int n){
	if(v > n) return;
	else {
		cout << v << " ";
		pre(v*2, n);
		pre(v*2+1, n);
	}
}

//중위순회
void mid(int v, int n){
	if(v > n) return;
	else {
		mid(v*2, n);
		cout << v << " ";
		mid(v*2+1, n);
	}
}

//후위순회
void aft(int v, int n){
	if(v > n) return;
	else {
		aft(v*2, n);
		aft(v*2+1, n);
		cout << v << " ";
	}
}

int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int n;
	cin >> n;
	
	pre(1, n);
	cout << endl;
	mid(1, n);
	cout << endl;
	aft(1, n);

	return 0;
}

    사이트의 답안   

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;	
void D(int x){
	if(x>7) return;
	else{
		printf("%d ", x);
		D(x*2);
		D(x*2+1);
	}
}	
int main(){
	freopen("input.txt", "rt", stdin);
	D(1);
	return 0;
}

    57번 문제   

    내가 풀이한 답   

Stack 구조를 활용하여 2로 나눈 몫이 1이면 몫과 나머지 순으로 출력하고 1이 아니면 다시 재귀함수를 호출하였다.

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;

void binary(int n){
	if(n/2==1) {
		cout << n/2 << n%2;
		return;
	}
	else {
		binary(n/2);
		cout << n%2;
	}
}

int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int n;
	cin >> n;
	
	binary(n);

	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;	
void D(int x){
	if(x==0) return;
	else{
		D(x/2);
		printf("%d", x%2);
	}
}	
int main(){
	freopen("input.txt", "rt", stdin);
	int n;
	scanf("%d", &n);
	D(n);
	return 0;
}

  사이트의 답과 비슷했다.