알고리즘 문제 풀기

백준 9934번: 완전 이진 트리 / 프로그래머스(카카오) : 길 찾기 게임 / 백준 12909번: 그래프 만들기.

studying develop 2020. 1. 21. 16:53

백준 9934번

 

음 알고리즘 분류가 트라이라서 트라이 문제일 줄 알았는데 그냥 완전 이진 트리 같다.

 

음 근데 문제는 전위 순회 결과에서 트리를 재구성하라는거 같다.

 

반대는 몇번 해봤는데 ;;

 

일단 K에 따라서 트리의 깊이는 미리 알 수 있는데 10으로 깊지 않다.

 

음 내 생각에 풀이는 임의로 트리를 만들고 순서대로 순회 하면서 도착 지점에 도달하면 주어진 인풋의 맨 앞부터 순서대로 해당 트리 노드에 넣어주면 될거 같다....

 

구현했는데 예제는 맞는데 틀렸다 함....음 ㅋㅋ 

 

음 완전 이진트리라는 조건에 뭔가 안맞게 설계한거 같다.

 

#define _CRT_SECURE_NO_WARNINGS

#include <string>
#include <vector>
#include <iostream>
#include <cstdio>
#include<queue>
using namespace std;

queue<int> output[11];
int K,N=0;
int tree[2000];
queue<int> q;

void pre_traverse(int node,int depth) {
	if (node > N) return;

	pre_traverse(2 * node,depth+1);
	//to do
	tree[node] = q.front();
	q.pop();
	output[depth].push(tree[node]);

	pre_traverse(2 * node + 1,depth+1);

}


int main() {
	ios_base::sync_with_stdio(false);

	freopen("input.txt", "r", stdin);

	cin >> K;
	int tmp;

	while (scanf("%d", &tmp) == 1) {
		q.push(tmp);
		N++;
	}
	//입력.
	pre_traverse(1, 0);

	//출력.
	for (int i = 0; i < 11; i++) {
		if (output[i].empty())
			break;
		while (!output[i].empty()) {
			cout << output[i].front() << " ";
			output[i].pop();
		}
		cout << "\n";
	}

	return 0;
}

 

내가 왜 틀린지 모르겠어서 검색해 보았다. 이런 풀이도 있따. https://www.crocus.co.kr/504

 

[9934번] 완전 이진 트리

문제 출처 : https://www.acmicpc.net/problem/9934 알고리즘 분석 : 문제 해결에 필요한 사항 1. 완전 이진 트리 이해 2. 완전 이진 트리의 구성 3. 중위 순회 예제 입력 자체가 현재 중위 순회로 되어있다. 이..

www.crocus.co.kr

매우 현명한 생각같다. 트리를 만들 필요 없이 트리의 모양을 알 수 있다!

 

깊이로 제한을 바꾸니까 맞았다. 완전이진 트리라 갯수로 해도 될거 같았는데 무슨 차이인지 아직 모르겠다.

#define _CRT_SECURE_NO_WARNINGS
#include<math.h>
#include <string>
#include <vector>
#include <iostream>
#include <cstdio>
#include<queue>
using namespace std;

queue<int> output[11];
int K, N = 0;
int tree[3000];
queue<int> q;

void pre_traverse(int node, int depth) {
	//K가 5이면
	//node : 1~31 , N : 31개.
	if (node > N) return;
	if (depth >= K) return;

	pre_traverse(2 * node, depth + 1);
	//to do
	tree[node] = q.front();
	q.pop();
	output[depth].push(tree[node]);

	pre_traverse(2 * node + 1, depth + 1);

}


int main() {
	ios_base::sync_with_stdio(false);

	freopen("input.txt", "r", stdin);

	cin >> K;
	int tmp;

	for(int i=0;i<pow(2,K)-1;i++) {
		cin >> tmp;
		q.push(tmp);
		N++;
	}
	//입력.
	pre_traverse(1, 0);

	//출력.
	for (int i = 0; i < 11; i++) {
		if (output[i].empty())
			break;
		while (!output[i].empty()) {
			cout << output[i].front();
			output[i].pop();
			if (!output[i].empty())
				cout << " ";
		}
		cout << "\n";
	}

	return 0;
}

 

 

길찾기 게임

음 그냥 이진 트리 만들어서 순회하면 되는 문제로 보인다. 전에는 사실 순회할 줄 몰랐다. 순회 하는 방법을 몰랐음.....

 

지금은 음 트리 만드는게 관건 일듯 ㅋㅋ

 

음 배열로 선언해서 트리를 구성하려고 하니까, 노드가 루트부터 순서대로 주어지는 경우가 아니라서 그건 힘들어 보이지만. 음~ 이렇게 쓰고 나니까 정렬해서 처리하면 되는거 아닌가 ㅋㅋ

 

근데 이제 문제는 출력할때 노드 인덱스 번호가 문제다. 음 노드 번호를 어떻게 저장하지. x,y를 해쉬로 처리하는 방법이 생각나긴 하는데 음

 

그거보다 쉬워보여서 그냥 vector<int>에 추가로 인덱스를 넣은 다음에 정렬했다. 구조체 처럼 같이 정렬되서 좋구나...

 

아 근데 문제가 완전 이진트리가 아니라는 점이다. ....

 

그래서 이 구현은 틀림

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int tree[20001];

bool cmp(vector<int>a, vector<int>b) {
	if (a[0] > b[0]) return true;
	else if (a[0] == b[0]) {
		if (a[1] < b[1]) return true;
		else return false;
	}
	else {
		return false;
	}
}
vector<int> vec1;
vector<int> vec2;

void preOrder(int index,vector<vector<int>>&nodeinfo) {
	preOrder(2 * index, nodeinfo);
	vec1.push_back(nodeinfo[index - 1][3]);
	preOrder(2 * index + 1, nodeinfo);
}

void postOrder(int index, vector<vector<int>>&nodeinfo) {
	postOrder(2 * index, nodeinfo);
	postOrder(2 * index + 1, nodeinfo);
	vec2.push_back(nodeinfo[index - 1][3]);
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
	vector<vector<int>> answer;

	for (int i = 0; i < nodeinfo.size(); i++) {
		nodeinfo[i].push_back(i + 1);
	}

	sort(nodeinfo.begin(), nodeinfo.end(),cmp);

	preOrder(1, nodeinfo);
	postOrder(1, nodeinfo);

	answer.push_back(vec1);
	answer.push_back(vec2);

	return answer;
}

 

이진 트리 만드는 방법을 찾아 보고 했다..... 내가 구현하려니까 잘 안되더라 ㅠ 음 일단 완전 이진트리가 아니라는 점이 달랐다. 또 루트 부터 순서대로 들어오는게 아니였다. 

https://jeongw00.tistory.com/307

 

아래 구현대로 하면 순서대로 들어올 필요가 없다.(상식적으로 순서대로 들어와야 된다고 만드는거 자체가 좀 이상한듯 그냥 막 넣어야지....)

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
//vector<int> tree[20001];

struct coor {
	int x, y;
};

bool cmp(vector<int>a, vector<int>b) {
	if (a[1] > b[1]) return true;
	else if (a[1] == b[1]) {
		if (a[0] < b[0]) return true;
		else return false;
	}
	else {
		return false;
	}
}

vector<int> vec1;
vector<int> vec2;

struct node {
	node*left=NULL, *right=NULL;
	int val;
	coor cord;
};



void insertRecur(node* r, node* n) {
	//n이 자식.
	if (n->cord.y < r->cord.y) {
		//n이 왼쪽으로 자식일듯.
		if (n->cord.x < r->cord.x) {
			if (r->left == NULL) {
				r->left = n;
			}
			else {
				insertRecur(r->left, n);
			}
		}
		else if (n->cord.x > r->cord.x) {
			if (r->right == NULL) {
				r->right = n;
			}
			else {
				insertRecur(r->right, n);
			}
		}
	}
}

node* root;

void makeTree(vector<vector<int>>&nodeinfo) {
	for (int i = 0; i < nodeinfo.size(); i++) {
		node * nNode = (node*)malloc(sizeof(node));
		nNode->val = nodeinfo[i][2];
		nNode->cord.x = nodeinfo[i][0];
		nNode->cord.y = nodeinfo[i][1];
		nNode->left = NULL;
		nNode->right = NULL;

		if (i == 0)root = nNode;
		else insertRecur(root, nNode);
	}
}

void preOrder(node* cur) {

	//To Do.
	vec1.push_back(cur->val);
	if (cur->left != NULL)
		preOrder(cur->left);
	if(cur->right != NULL)
		preOrder(cur ->right );
}
void postOrder(node* cur) {
	if (cur->left != NULL)
		postOrder(cur->left);
	if (cur->right != NULL)
		postOrder(cur->right);
	//To Do.
	vec2.push_back(cur->val);
}

vector<vector<int>> solution(vector<vector<int>> nodeinfo) {
	vector<vector<int>> answer;

	for (int i = 0; i < nodeinfo.size(); i++) {
		nodeinfo[i].push_back(i + 1);
	}

	sort(nodeinfo.begin(), nodeinfo.end(),cmp);

	makeTree(nodeinfo);

	preOrder(root);
	postOrder(root);

	answer.push_back(vec1);
	answer.push_back(vec2);

	return answer;
}

int main() {
	vector<int>tmp;
	vector<vector<int>>nodeinfo;
	

	tmp.push_back(5);
	tmp.push_back(3);
	nodeinfo.push_back(tmp);
	tmp.clear();

	tmp.push_back(11);
	tmp.push_back(5);
	nodeinfo.push_back(tmp);
	tmp.clear();
	
	tmp.push_back(13);
	tmp.push_back(3);	
	nodeinfo.push_back(tmp);
	tmp.clear();

	tmp.push_back(3);
	tmp.push_back(5);	
	nodeinfo.push_back(tmp);
	tmp.clear();

	tmp.push_back(6);
	tmp.push_back(1);	
	nodeinfo.push_back(tmp);
	tmp.clear();


	tmp.push_back(1);
	tmp.push_back(3);	
	nodeinfo.push_back(tmp);
	tmp.clear();

	tmp.push_back(8);
	tmp.push_back(6);	
	nodeinfo.push_back(tmp);
	tmp.clear();

	tmp.push_back(7);
	tmp.push_back(2);	
	nodeinfo.push_back(tmp);
	tmp.clear();

	tmp.push_back(2);
	tmp.push_back(2);	
	nodeinfo.push_back(tmp);
	tmp.clear();
	
	solution(nodeinfo);

	return 0;
}

 

 

백준 12909번 : 그래프 만들기.

 

음 그래프 조건이 노드가 N개 간선이 N-1개 이다. 

 

두번 째 줄에는 각 차수에 대한 점수가 주어진다. 음 가장 높은 점수인 차수가 많을 수 록 좋겠지....

 

음 노드 수가 50개다.

 

음 모든 경우에 대해서 그래프를 만들어서 최대 값인 경우를 구해야 될거 같다.

 

근데 그래프를 어떻게 만들지 하나의 노드를 추가할때 연결되어 있는 모든 노드에 추가해보면 되는거 아닌가? 

 

그런데 예상되는 문제는 그래프 위상이 같은지 알 수 가 없다는 것이다. 중복된 것이 있을듯 그래도 해볼까?

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int weight[51];
vector<int> adj[51];
int maxv;
int N;

void addNode(int r, int n,int N) {
	
	if (n > N) {
		int sum = 0;
		for (int i = 1; i <= N; i++) {
			sum +=  weight[adj[i].size()];
		}
		if (maxv < sum)
			maxv = sum;

		return;
	}

	adj[r].push_back(n);
	adj[n].push_back(r);

	for (int i = 1; i <= N; i++) {
		addNode(i, n + 1, N);
	}
	adj[r].pop_back();
	adj[n].pop_back();

}



int main() {
	ios_base::sync_with_stdio(false);

	freopen("input.txt", "r", stdin);

	cin >> N;
	for (int i = 1; i <= N - 1; i++) {
		int tmp;
		cin >> tmp;
		weight[i] = tmp;
	}
	//처음에 1,2번 노드는 연결 해 놓아야 한다.
	addNode(1, 2,N);

	cout << maxv;

	return 0;
}

 

음 구현하긴 했는데 문제가 dfs인 완전 탐색이라 2^50 ㅋㅋ 시간이 걸린다..... 즉 이건 아니다~ 

 

사실 실제로 만들 필요 없는거 아닌가. 그냥 N-1을 N개 이하로 분할하는 문제 같다. 

 

음 자연수 분할이라는 건가 이게 https://m.blog.naver.com/PostView.nhn?blogId=vollollov&logNo=220989048062&proxyReferer=https%3A%2F%2Fwww.google.com%2F

 

 

자연수의 분할 P(n, k)

1. 자연수 n을 k 개의 자연수의 합으로 나타낸다. P(n, k)자연수 7을 3개의 자연수의 합으로 직접 나타내...

blog.naver.com

음 이걸로 구현했는데, 분할 된다고 해서 그런 그래프가 존재하는게 아니더라..?아 아닌가 아~ 갑자기 생각났는데 노드 갯수만큼으로 분할 하면 될듯??

 

일단 구현한 코드. N은 좀 바꿔서 분할해야 한다. 2*(N-1)로 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int weight[51];
vector<int> adj[51];
int maxv=0;
int N;

vector<int> vec;

void partition(int n, int r) {
	if (n < 0) return;
	if (n == 0) {
		int sum = 0;
		for (int i = 0; i < vec.size(); i++) {
			sum += weight[vec[i]];
		}
		if (maxv < sum)
			maxv = sum;
	}

	for (int i = 1; i <= r; i++)
	{
		vec.push_back(i);
		partition(n - i, r);
		vec.pop_back();
	}

}


int main() {
	ios_base::sync_with_stdio(false);

	freopen("input.txt", "r", stdin);

	cin >> N;
	for (int i = 1; i <= N - 1; i++) {
		int tmp;
		cin >> tmp;
		weight[i] = tmp;
	}

	partition(2 * (N - 1), N - 1);

	cout << maxv;

	return 0;
}

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int weight[51];
vector<int> adj[51];
int maxv=0;
int N;

vector<int> vec;

void partition(int n, int r) {
	if (n < 0) return;
	if (n == 0 ) {
		if (vec.size() == N) {
			int sum = 0;
			for (int i = 0; i < vec.size(); i++) {
				sum += weight[vec[i]];
			}
			if (maxv < sum)
				maxv = sum;
		}
		return;
	}

	for (int i = 1; i <= r; i++)
	{
		vec.push_back(i);
		partition(n - i, r);
		vec.pop_back();
	}

}


int main() {
	ios_base::sync_with_stdio(false);

	freopen("input.txt", "r", stdin);

	cin >> N;
	for (int i = 1; i <= N - 1; i++) {
		int tmp;
		cin >> tmp;
		weight[i] = tmp;
	}

	partition(2 * (N - 1), N - 1);

	cout << maxv;

	return 0;
}

음 이게 시간초과난다. 메모이제이션을 써야 되나? https://blankspace-dev.tistory.com/73여기 방법이 있다.

 

음 해봤는데 구현에 실패했다. 내가 하는 방법이랑 맞는건가? 코드가 좀 다른듯... 이해 잘 못해서 n,r 이게 뭔소리지 

n을 m 이하의 수로 표현한다고?ㅠㅠ

 

나중에 다시하자.

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int weight[51];
vector<int> adj[51];
int maxv=0;
int N;

vector<int> vec;

void partition(int n, int r) {
	static int memo[1000][1000];

	if (n < r) r=n;

	if (memo[n][r] > 0)
		return;

	if ( n == 0 ) {
		if (vec.size() == N) {
			int sum = 0;
			for (int i = 0; i < vec.size(); i++) {
				sum += weight[vec[i]];
			}
			if (maxv < sum)
				maxv = sum;
		}
		memo[n][r] = 1;
		return;
	}

	for (int i = 1; i <= r; i++)
	{
		vec.push_back(i);
		partition(n - i, i);
		vec.pop_back();
	}
	memo[n][r] = 1;
}


int main() {
	ios_base::sync_with_stdio(false);

	freopen("input.txt", "r", stdin);

	cin >> N;
	for (int i = 1; i <= N - 1; i++) {
		int tmp;
		cin >> tmp;
		weight[i] = tmp;
	}

	partition(2 * (N - 1), N - 1);

	cout << maxv;

	return 0;
}

'알고리즘 문제 풀기' 카테고리의 다른 글

백준 : 4358번 생태학 ,17837번 새로운 게임2  (0) 2020.01.25
프로그래머스 - 가장 먼 노드, 정수 삼각형  (0) 2020.01.23
프로그래머스 - 탐욕법 : 체육복, 조이스틱  (0) 2020.01.20
프로그래머스 - 이분 탐색 : 예산, 입국 심사,  (0) 2020.01.19
백준 - 11004번 K번째 수  (0) 2020.01.16

'알고리즘 문제 풀기'의 다른글

  • 현재글백준 9934번: 완전 이진 트리 / 프로그래머스(카카오) : 길 찾기 게임 / 백준 12909번: 그래프 만들기.

관련글

댓글

티스토리툴바