1R/2015 09 12 - Revision history

Maintenance script: Repair pages found by live-compare batch 0001

2026-03-26T14:46:15Z

Repair pages found by live-compare batch 0001

219.255.207.30 at 02:30, 13 September 2016

2016-09-13T02:30:30Z

← Older revision		Revision as of 02:30, 13 September 2016
Line 5:		Line 5:

	= 참가자 =		= 참가자 =
	* 15이원준		* 15이원준, 박인서
	= 코드 =		= 코드 =
	== 15이원준 ==		== 15이원준 ==

223.62.229.104 at 15:50, 12 September 2016

2016-09-12T15:50:10Z

← Older revision		Revision as of 15:50, 12 September 2016
Line 153:		Line 153:
	== 박인서 ==		== 박인서 ==
	1. 이 문제를 어떻게 해야 할 것인가?		1. 이 문제를 어떻게 해야 할 것인가?
			일단 노드의 갯수가 1000개 이하이므로 일일히 노드에 대하여 탐색을 하여도 시간이 부족하지는 않다. 따라서 일일이 탐색을 하는 것을 목적으로 한다.

	~~일단 노드의 갯수가 1000개 이하이므로 일일히 노드에 대하여 탐색을 하여도 시간이 부족하지는 않다. 따라서 일일이 탐색을 하는 것을 목적으로 한다.~~
	2. 중위순회란 무엇인가?		2. 중위순회란 무엇인가?

	위키 페이지를 참고하여주세요.		위키 페이지를 참고하여주세요.
	https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C		https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

	3. 그러면 이 문제는 어떻게 해결해야 되는가?		3. 그러면 이 문제는 어떻게 해결해야 되는가?

	이 문제에서 열 번호가 왼쪽자식->자기자신->오른쪽자식(중위순회) 순서로 되어 있다. 따라서, 이를 따라서 함수를 호출하여 번호를 매긴다. 그리고 depth에 따라서 배열에 열 번호의 최소값과 최대값을 저장하여 해결 할 수 있다.		이 문제에서 열 번호가 왼쪽자식->자기자신->오른쪽자식(중위순회) 순서로 되어 있다. 따라서, 이를 따라서 함수를 호출하여 번호를 매긴다. 그리고 depth에 따라서 배열에 열 번호의 최소값과 최대값을 저장하여 해결 할 수 있다.

	== 곽정흠 ==		== 곽정흠 ==

223.62.229.104 at 15:49, 12 September 2016

2016-09-12T15:49:39Z

@@ Line 152: / Line 152: @@
 # 각 행의 너비를 구하고 가장 큰 값을 찾아 그 행의 번호와 너비를 출력한다.
 == 박인서 ==
 == 곽정흠 ==

223.62.229.104 at 15:40, 12 September 2016

2016-09-12T15:40:07Z

← Older revision		Revision as of 15:40, 12 September 2016
Line 99:		Line 99:
	#include <iostream>		#include <iostream>
	#define LEN 10001		#define LEN 10001

	using namespace std;		using namespace std;
	int tree[LEN][2],maxgap[LEN],mingap[LEN];		int tree[LEN][2], maxgap[LEN], mingap[LEN];
	int cnt=0,maxdep=0;		int cnt = 0, maxdep = 0;

	//왼쪽자식->자기자신->오른쪽 자식 순으로 cnt를 세가며 위치를 지정(너비도 같이 생각)		//왼쪽자식->자기자신->오른쪽 자식 순으로 cnt를 세가며 위치를 지정(너비도 같이 생각)
	void solve(int node, int depth)		void solve(int node, int depth)
	{		{
	//초기화 및 maxdep 설정		//초기화 및 maxdep 설정
	if(depth>maxdep) maxdep=depth,mingap[depth]=1001,maxgap[depth]=-1;		if (depth>maxdep) maxdep = depth, mingap[depth] = 1001, maxgap[depth] = -1;
	if(tree[node][0]!=-1) solve(tree[node][0], depth + 1);//왼쪽 자식 호출		if (tree[node][0] != -1) solve(tree[node][0], depth + 1);//왼쪽 자식 호출
	cnt++;//node 1개 증가		cnt++;//node 1개 증가
	//maxgap,mingap 설정		//maxgap,mingap 설정
	if(mingap[depth]>cnt) mingap[depth]=cnt;		if (mingap[depth]>cnt) mingap[depth] = cnt;
	if(maxgap[depth]<cnt) maxgap[depth]=cnt;		if (maxgap[depth]<cnt) maxgap[depth] = cnt;
	if(tree[node][1]!=-1) solve(tree[node][1], depth + 1);//오른쪽 자식 호출		if (tree[node][1] != -1) solve(tree[node][1], depth + 1);//오른쪽 자식 호출
	}		}

	int main()		int main()
	{		{
	int ~~a, i,~~ num, ~~res=-1, index=0~~;		int num, root;
	//입력		//입력
	cin>>num;		cin >> num;
	for(i=1; i<=num; i++)		for (int i = 1; i <= num; i++)
	{		{
	cin>>a;		int a;
	cin>>tree[a][0]>>tree[a][1];		cin >> a;
	}		cin >> tree[a][0] >> tree[a][1];
	//함수 번호 매기기		if (i==1 \|\| tree[a][0] == root \|\| tree[a][1] == root) root = a;
	solve(1, 1);		}
	//너비가 가장 큰 것 찾기		//함수 번호 매기기
	for(i=1; i<=maxdep; i++)		solve(root, 1);
	if(res<maxgap[i]-mingap[i]) res=maxgap[i]-mingap[i],index=i;		//너비가 가장 큰 것 찾기
	//출력		int res = -1, index = 0;
	cout<<index<<" "<<res+1<<'\n';		for (int i = 1; i <= maxdep; i++)
	return 0;		if (res<maxgap[i] - mingap[i]) res = maxgap[i] - mingap[i], index = i;
			//출력
			cout << index << " " << res + 1 << '\n';
			return 0;
	}		}

223.62.229.32 at 15:17, 12 September 2016

2016-09-12T15:17:30Z

← Older revision		Revision as of 15:17, 12 September 2016
Line 98:		Line 98:
	== 박인서 ==		== 박인서 ==
	#include <iostream>		#include <iostream>
	#define LEN ~~1001~~		#define LEN 10001

	using namespace std;		using namespace std;

223.62.229.32 at 15:12, 12 September 2016

2016-09-12T15:12:03Z

@@ Line 97: / Line 97: @@
+  }
 == 박인서 ==
 == 곽정흠 ==

imported>vkdnjdldnjsw at 15:07, 12 September 2016

2016-09-12T15:07:26Z

← Older revision		Revision as of 15:07, 12 September 2016
Line 102:		Line 102:
	= 아이디어 =		= 아이디어 =
	== 15이원준 ==		== 15이원준 ==
	# 각각의 노드들의 왼쪽에 연결된 노드들의 수와 오른쪽에 연결된 노드들의 수를 구한다.		# 루트를 찾으면 모든 입력을 저장한다.(arr에 저장)
	# root노드의 열 넘버는 자신의 왼쪽에 연결된 노드들의 수 + 1 이다.		# 각각의 노드들의 왼쪽에 연결된 노드들의 수와 오른쪽에 연결된 노드들의 수를 구한다.(ex에 저장)
	# 각 노드의 왼쪽노드의 열 넘버 = (자신의 열넘버) - (왼쪽노드의 오른쪽에 연결된 노드들의 수) - 1 이다.		# root노드의 열 넘버는 자신의 왼쪽에 연결된 노드들의 수 + 1 이다.(myNum에 저장)
	# 각 노드의 오른쪽노드의 열 넘버 = (자신의 열넘버) + (오른쪽노드의 왼쪽에 연결된 노드들의 수) + 1 이다.		# 각 노드의 왼쪽노드의 열 넘버 = (자신의 열넘버) - (왼쪽노드의 오른쪽에 연결된 노드들의 수) - 1 이다. (myNum에 저장)
	# 행에서 가장 왼쪽에 있는 노드의 열넘버와 가장 오른쪽에 있는 노드의 열넘버를 저장한다.		# 각 노드의 오른쪽노드의 열 넘버 = (자신의 열넘버) + (오른쪽노드의 왼쪽에 연결된 노드들의 수) + 1 이다.(myNum에 저장)
			# 행에서 가장 왼쪽에 있는 노드의 열넘버와 가장 오른쪽에 있는 노드의 열넘버를 저장한다.(level에 저장)
	# 각 행의 너비를 구하고 가장 큰 값을 찾아 그 행의 번호와 너비를 출력한다.		# 각 행의 너비를 구하고 가장 큰 값을 찾아 그 행의 번호와 너비를 출력한다.
	== 박인서 ==		== 박인서 ==
	== 곽정흠 ==		== 곽정흠 ==

imported>vkdnjdldnjsw at 15:06, 12 September 2016

2016-09-12T15:06:02Z

← Older revision		Revision as of 15:06, 12 September 2016
Line 102:		Line 102:
	= 아이디어 =		= 아이디어 =
	== 15이원준 ==		== 15이원준 ==
			# 각각의 노드들의 왼쪽에 연결된 노드들의 수와 오른쪽에 연결된 노드들의 수를 구한다.
			# root노드의 열 넘버는 자신의 왼쪽에 연결된 노드들의 수 + 1 이다.
			# 각 노드의 왼쪽노드의 열 넘버 = (자신의 열넘버) - (왼쪽노드의 오른쪽에 연결된 노드들의 수) - 1 이다.
			# 각 노드의 오른쪽노드의 열 넘버 = (자신의 열넘버) + (오른쪽노드의 왼쪽에 연결된 노드들의 수) + 1 이다.
			# 행에서 가장 왼쪽에 있는 노드의 열넘버와 가장 오른쪽에 있는 노드의 열넘버를 저장한다.
			# 각 행의 너비를 구하고 가장 큰 값을 찾아 그 행의 번호와 너비를 출력한다.
	== 박인서 ==		== 박인서 ==
	== 곽정흠 ==		== 곽정흠 ==

imported>vkdnjdldnjsw at 15:00, 12 September 2016

2016-09-12T15:00:57Z

@@ Line 8: / Line 8: @@
 = 코드 =
 == 15이원준 ==
+ #include&lt;iostream&gt;
 == 박인서 ==