✔ 풀이를 위한 아이디어
- 자료구조 중 트리 (Tree), 그리고 트리 순회의 응용
- 분할 정복 (Divide-and-conquer algorithm)
- 재귀 (Recursion)
✔ 트리 순회 심화편
-
일반적인 트리 순회에 대한 개념은 다음 게시물을 참조하자 - https://hongku.tistory.com/160
-
후위 순회 (Postorder traverse) 에서 우리가 쉽게 알 수 있는 것은, 맨 마지막에 루트 노드의 데이터가 오게 된다는 것이다.
-
이를 통해, 중위 순회 (Inorder traverse) 에서 루트 노드를 찾을 수 있고, 중위 순회의 특성상 왼쪽에서 오른쪽으로 진행하므로, 루트 노드를 기준으로 왼쪽 오른쪽의 sub tree로 나눌 수 있다. (좌측 그림 참조)
-
나눠진 sub tree를 후위 순회의 결과에서 찾아보면, 역시 함께 묶여있음을 확인할 수 있다. 이 각 묶음에서도 맨 마지막에 오는 데이터가 루트 노드에 해당한다. (우측 그림 참조)
-
이러한 과정을 계속해서 반복 (Recursion) 하며 중위 순회와 후위 순회의 결과를 쪼개나가면 (Divide-and-conquer) 전체 Tree를 밝혀낼 수 있다.
✔ 정답 코드
import sys
sys.setrecursionlimit(10**6) # 파이썬의 기본 재귀 깊이 제한은 1000으로 매우 얕은 편이므로 필수
n = int(sys.stdin.readline())
inOrder = list(map(int, sys.stdin.readline().split()))
postOrder = list(map(int, sys.stdin.readline().split()))
directInOrder = [-1]*(n+1)
for i in range(n):
directInOrder[inOrder[i]] = i
def fillTree(stIndx_i, edIndx_i, stIndx_p, edIndx_p, currentRoot):
currentRoot['data'] = postOrder[edIndx_p]
mid = directInOrder[postOrder[edIndx_p]]
if stIndx_i < mid:
leftRoot = {}
currentRoot['left'] = leftRoot
fillTree(stIndx_i, mid-1, stIndx_p, stIndx_p+(mid-stIndx_i-1), leftRoot)
if mid < edIndx_i:
rightRoot = {}
currentRoot['right'] = rightRoot
fillTree(mid+1, edIndx_i, edIndx_p-(edIndx_i-mid), edIndx_p-1, rightRoot)
def preOrder(currentRoot):
print("{} ".format(currentRoot['data']), end="")
if 'left' in currentRoot:
preOrder(currentRoot['left'])
if 'right' in currentRoot:
preOrder(currentRoot['right'])
ultimateRoot = {}
fillTree(0, n-1, 0, n-1, ultimateRoot)
preOrder(ultimateRoot)
print()
위에서 설명한 원리에 따라, 분할 정복 (Divide-and-conquer algorithm) 과 재귀 (Recursion) 를 활용해 작성한 코드는 위와 같다. 지금부터 이 코드를 부분별로 나누어 설명하도록 하겠다.
- directInOrder 정의
매번 inOrder 배열을 탐색하는 것은 시간복잡도를 증가시키므로, 아래와 같이 처리하여 inOrder의 각 data들이 몇 번째 index에 있는지 한번에 알 수 있도록 한다.directInOrder = [-1]*(n+1) for i in range(n): directInOrder[inOrder[i]] = i
- fillTree 정의
재귀적으로 호출되며, Tree를 밝혀내는 함수이다. 4가지 변수를 활용해 배열을 분할하고, 전체 Tree를 정복한다.def fillTree(stIndx_i, edIndx_i, stIndx_p, edIndx_p, currentRoot): # stIndx_i, edIndx_i: inOrder 배열에서 살펴볼 곳의 시작점과 끝점 # stIndx_p, edIndx_p: postOrder 배열에서 살펴볼 곳의 시작점과 끝점 currentRoot['data'] = postOrder[edIndx_p] mid = directInOrder[postOrder[edIndx_p]] if stIndx_i < mid: leftRoot = {} currentRoot['left'] = leftRoot fillTree(stIndx_i, mid-1, stIndx_p, stIndx_p+(mid-stIndx_i-1), leftRoot) if mid < edIndx_i: rightRoot = {} currentRoot['right'] = rightRoot fillTree(mid+1, edIndx_i, edIndx_p-(edIndx_i-mid), edIndx_p-1, rightRoot)
- 우선, InOrder 배열과 postOrder 배열에서 살펴봐야할 부분이 계속해서 바뀌므로 총 4개의 parameter을 활용해 각 재귀호출에서 알 수 있도록 한다.
또한, 루트 노드부터 시작해 sub tree의 루트 노드들로 내려가며 전체 Tree를 밝혀나가는 흐름이므로 , 현재의 루트 노드도 같이 넘겨준다.
- 후위 순회의 맨 마지막 값이 현재의 루트 노드의 data에 해당하므로, 값을 넣어준다.
또한, 현재 루트노드의 값이 InOrder에서 몇번째 index에 있는지를 파악하여 mid라는 변수에 넣어준다.
- 살펴볼 inOrder 배열의 범위에서 루트 노드 왼쪽에 data가 있다면 좌측 자식 노드를 만들 수 있으므로, 새로운 dictionary를 만들어서 넣어준다.
이때, 다음에 inOrder에서 살펴볼 부분은 현재 루트 노드의 왼쪽이므로 stIndx_i와 mid-1을 넘겨준다.
또한, 다음에 postOrder에서 살펴볼 부분은 기존에 살펴보던 시작점부터, inOrder에서 살펴볼 부분의 크기만큼 (mid-1-stIndx_i) 이므로 위와 같이 넘겨준다.
- 살펴볼 inOrder 배열의 범위에서 루트 노드 오른쪽에 data가 있다면 우측 자식노드를 만들 수 있으므로, 새로운 dictionary를 만들어서 넣어준다.
이때, 다음에 inOrder에서 살펴볼 부분은 현재 루트 노드의 오른쪽이므로, mid+1과 edIndx_i를 넘겨준다.
또한, 다음에 postOrder에서 살펴볼 부분은 기존에 살펴보던 끝점에서 하나를 뺀 edIndx_p-1부터, inOrder에서 살펴볼 부분의 크기만큼이므로 위와 같이 넘겨준다.
- preOrder 정의
재귀적으로 전위 순회 하며 순서대로 data를 출력하는 함수이다. dictionary에 key값이 있는지 확인할 때는 아래와 같이 처리한다.def preOrder(currentRoot): print("{} ".format(currentRoot['data']), end="") if 'left' in currentRoot: preOrder(currentRoot['left']) if 'right' in currentRoot: preOrder(currentRoot['right'])
- main부 정의
처음에는, 전체 배열을 살펴보며 시작하므로 0과 n-1을 넘겨준다. 또한, 루트 노드 역할을 할 dictionary를 선언하고 fillTree 함수에 넘겨주어, Tree가 완성되도록 한다. 이후 이 루트 노드를 preOrder 함수에 넣어서 정답을 출력한다.ultimateRoot = {} fillTree(0, n-1, 0, n-1, ultimateRoot) preOrder(ultimateRoot) print()
-
처음에는 위에서 설명한 원리들을 완벽히 구현하지 않았기 때문에 틀렸으며, RecursionError은 setrecursionlimit 메서드를 활용해 쉽게 해결하였다.
-
문제를 푸는데 활용한 반례들: https://bingorithm.tistory.com/5
