2263 트리의 순회, 5639 이진 검색 트리

두개의 문제는 전위,중위,후위순회을 활용해서 문제를 풀어봐야한다.

2263 트리의 순회

https://www.acmicpc.net/problem/2263

1.접근

생각하기 어려웠지만 직접 트리를 그려서 중위탐색과 후위 탐색을 해보면 전위 탐색을 어떤식으로 해야할지 보였다.

2.풀이

중위순회과 후위순회을 그려보면 규칙을 찾을 수 있다. 후위 탐색된 리스트에서 맨 마지막 값은 중위 순회의 루트노드일 것이다.따라서 중위 탐색에서 그 루트노드의 인덱스를 구해서 왼쪽 오른쪽 나눠서 재귀적인 문제로 만들어 풀면 된다.

여기서 후위순회에서 구한 루트값의 인덱스를 구할 때 일일이 탐색하게 되면 시간초과가 날게 분명하므로 

for i in range(n):
     num[in_order[i]-1]=i 루트값이 어디있는지 인덱스를 빠르게 구할 수 있도록 만들어 주는 이 스킬이 중요했다.

<<중위 순회

 

 

<<후위 순회

 

3.코드

	import sys
	input=sys.stdin.readline
	sys.setrecursionlimit(10**9)
	def divide(root,left,right,plus):
	if left>right or right<left:
	return
	print(root,end=' ')
	temp=num[root-1]
	L=temp-left
	R=right-temp
	if plus+L-1<n:
	divide(post_order[plus+L-1],left,temp-1,plus)
	if plus+L+R-1<n:
	divide(post_order[plus+L+R-1],temp+1,right,plus+L)
	n=int(input())
	in_order=list(map(int,input().split()))
	post_order=list(map(int,input().split()))
	num=[0]*n
	for i in range(n):
	num[in_order[i]-1]=i
	root=post_order[-1]
	divide(root,0,n-1,0)

view raw 2263트리의 순회.py hosted with ❤ by GitHub

4.배운점

• 숫자가 n까지 순서대로 나왔을 때 그 값이 어느 인덱스에 있는지 쉽게 구할 수 있는 코드를 익숙하게 쓰자
• 재귀함수에 범위를 잡아줄 때 많이 어려웠다.오른쪽은 plus를 해준 곳 기준으로 움직였어야 하는데 plus변수 사용이 어려웠다.

 

5639 이진 검색 트리

https://www.acmicpc.net/problem/5639

1.접근

위 문제와 비슷하게 트리를 전위 순회한 결과를 보면 어떻게 재귀적으로 나눠서 풀어야 할지 보였다

2.풀이

전위 순회가 주어지므로 첫 수는 당연히 전체 트리의 루트노드일 것이다.

그 루트노드 값보다 큰것은 오른쪽 작은것은 왼쪽으로 나눠진다는 생각을 가지고 재귀를 만들면 된다.

왼쪽 오른쪽 나눠서 들어가면 또 맨 앞에 있는 숫자가 서브트리의 루트노드일 것이다.

오른쪽과 왼쪽을 구분짓는 구간을 찾기위해서 일일히 해보기 보다는 공부했던 이진탐색을 활용해서 시간을 단축했다.

3.코드

	import sys
	sys.setrecursionlimit(10**9)
	input=sys.stdin.readline
	Q=[]
	ans=[]
	while True:
	try:
	Q.append(int(input()))
	except:
	break
	def BS(L,R,root):
	x=L
	if Q[R]>root:
	while L<=R:
	mid=(L+R)//2
	if Q[mid]>root:
	R=mid-1
	else:
	L=mid+1
	if Q[mid]>root:
	return mid
	else:
	return mid+1
	else:
	return x
	def divide(left,right):
	if left==right:
	ans.append(Q[left])
	return
	root=Q[left]
	ans.append(root)
	temp=BS(left+1,right,root)
	if temp==left+1:
	divide(temp,right)
	return
	else:
	divide(temp, right)
	divide(left+1,temp-1)
	divide(0,len(Q)-1)
	for i in ans[::-1]:
	print(i)

view raw 5639이진트리.py hosted with ❤ by GitHub

4.배운점

• 재귀 함수나 DFS같은 함수를 만들 때 탈출조건을 더 신중히 생각해서 설정해야겠다.
• 입력이 몇개들어오는지 모를 때는 while에 try,except문을 합쳐서 구현하면 된다. 익숙하지 않아서 쓰지 않았는데 이참에 외워야 겠다.