https://www.acmicpc.net/problem/5639
문제 풀이
[사용한 개념]
[재귀 코드 방식]
1. 재귀 함수의 실제 동작
2. 다음으로 넘어가기
3. 재귀 함수의 실제 동작
여기서, 재귀 함수의 실제 동작은 1번에 있을 수도 있고 3번에 있을 수도 있고, 둘 다 있을 수 있다.
1번에 있다면, 이전 상태에서 현재 상태로 왔을때 동작하는 부분이라고 생각하면 된다.
3번에 있다면, 현재 상태에서 다음 상태로 넘어갔다가, 돌아왔을 때 동작하는 부분이라고 생각하면 된다.
[트리]
이진 검색 트리는, 왼쪽 child < 부모 노드 < 오른쪽 child 로 이루어진 트리를 의미한다.
[종합 설명]
이진 검색 트리를, 전위순회 한 결과가 주어진다.
이진 검색 트리의 특성을 이용하면, 우리는 전위순회의 결과를 3부분으로 나눌 수 있다.
루트 노드 / 왼쪽 서브트리 / 오른쪽 서브트리
가장 처음에 나오는 노드가 루트 노드,
루트 노드보다 작은 노드들이 왼쪽 서브트리
루트 노드보다 큰 노드들이 오른쪽 서브트리가 된다.
결과를 3부분으로 나누는 작업이 계속되고, 노드가 1개 남게 될 때 자신을 출력하면 된다.
즉, 재귀함수를 이용하면 된다.
코드로 확인해보자
[코드]
import sys
sys.setrecursionlimit(10 ** 5)
arr = []
while True:
try:
a = int(input())
except:
break
arr.append(a)
def post_order(start,end):
# 재귀함수의 실제 동작
if start > end:
return
'''
[노드가 1개 남았을 경우 출력하는 코드]
맨 처음엔 넣었지만, 없어도 되는 이유가 있다.
여기서 굳이 출력하지 않더라도 post_order 재귀 코드가 아무 동작 안하고 리턴되므로(왼쪽,오른쪽 child가 없어서)
print(arr[start])가 실행되기 때문이다.
'''
# if start == end:
# print(arr[start])
# return
s = arr[start]
div_idx = end+1 # 만약 왼쪽 / 오른쪽 안잘리면, end 다음 번호가 div_idx이어야함
for i in range(start+1,end+1):
if s < arr[i]:
div_idx = i
break
# 다음으로 넘어가기
post_order(start+1,div_idx-1)
post_order(div_idx,end)
# 재귀함수의 실제 동작
print(arr[start])
post_order(0,len(arr)-1)
후위 순회는,
1. 왼쪽 서브트리 방문
2. 오른쪽 서브트리 방문
3. 루트 노드 방문
으로 진행됨을 생각하고, 재귀 함수를 작성해보자.
[재귀 함수 작성하기]
"1. 재귀 함수의 실제 동작"에 적어야 할 것
- 언제 해당 재귀함수가 리턴되는지
- 여기서는, start > end 인 경우 더 이상 탐색(순회)하지 않아도 되므로, 이 값을 적어준다
"2. 다음으로 넘어가기" 부분에 적어야 하는 것은,
후위순회의 특성을 생각해보면 된다.
왼쪽 서브트리를 먼저 쭈우우우우우우우우욱 방문하고,
그 다음 오른쪽 서브트리를 쭈우우우우우욱 방문하고,
그 다음 루트노드를 방문하게 된다.
따라서, 여기에 재귀 함수를 아래와 같이 적어주면 된다.
1. 왼쪽 서브트리 방문
2. 오른쪽 서브트리 방문
"3. 재귀 함수의 실제 동작" 부분에 적어야 하는 것은,
왼쪽, 오른쪽 서브트리를 쭈우우욱 다 방문했을 때, 현재의 루트 노드를 방문하면 된다.
따라서,
- 루트 노드 출력하기
를 적으면 된다.