백준 5639 - 이진탐색트리를 분할정복으로

문제

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

예시

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

50
30
24
5
28
45
98
52
60

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

5
28
24
45
30
60
52
98
50

이진탐색트리 자료구조

사실 이진탐색트리 자료구조를 이해하고자 이 문제를 선택하였습니다. 이진탐색트리의 찾기,삽입,삭제 과정 및 시간 복잡도는 첨부된 링크로 공부할 수 있었습니다.

이진탐색트리

preorder,postorder

이런 자료 구조가 주어졌다고 하였을 때

preorder 의 경우

def pre_order(self,index=0):
  self.preorder.append(self.key[index])
  if self.left[index]!=-1:
    self.pre_order(self.left[index])
  if self.right[index]!=-1:
    self.pre_order(self.right[index])
  return

입니다.

즉 재귀함수이므로 index=0 인 노드4의 pre_order 함수를 풀기 위해서는 왼쪽 오른쪽 노드 2,5 각각의 pre_order 함수가 풀려야하고 또 2,5의 pre_order 함수를 풀기 위해서는 각각 1,3 pre_order 함수 / 5 pre_order 함수가 풀려야합니다.

left 에 걸어준 if 문이 항상 먼저 들어가므로 노드2로부터 이어진 1,3 pre_order 함수가 먼저 풀립니다. (자식이 없으므로)

그런데 self.preorder.append(self.key[index]) 로 미리 내려가는 과정 중에 있는 노드를 추가해주면서 가기 때문에 경로가 그대로 저장됩니다.

4->4를 풀기 위해서 2->2를 풀기 위해서 1(2의 left)->2를 풀기 위해서 3(2의 right) 여기까지 4를 풀기 위한 4의 left -> 4를 풀기 위해서 5 (4의 right) -> 최종 4 (4의 left,right 재귀 모두 돌고 리턴)

이어서 preorder 은 4 2 1 3 5 가 됩니다.

postorder 의 경우

def post_order(self,index=0):
  if self.left[index]!=-1:
    self.post_order(self.left[index])
  if self.right[index]!=-1:
    self.post_order(self.right[index])
  self.postorder.append(self.key[index])
  return

인데 left,right 두 조건문 밑에 self.postorder.append(self.key[index]) 가 있으므로

4->4를 풀기 위해서 2->2를 풀기 위해서 1(2의 left)->2를 풀기 위해서 3 (2의 right) 여기까지 4를 풀기 위한 4의 left -> 4를 풀기 위해서 5 (4의 right) -> 최종 4 (4의 left,right 재귀 모두 돌고 리턴)

에서 과정 제일 밑으로 내려간 낭떠러지 노드부터 저장이 됩니다.

즉 2의 left 낭떠러지 1이 먼저 저장되고 2의 right 낭떠러지 3이 저장되고 풀린 2가 저장되고 4의 right 낭떠러지 5가 저장되고 최종적으로 풀린 4가 저장됩니다.

따라서 postorder 은 1 3 2 5 4 입니다.

푸는 법

입력이 preorder 이기 때문에 미리 내려가는 과정 중에 있는 노드를 추가해주면서 가기 때문에 경로가 그대로 저장됩니다.

postorder 은 반면 맨 밑으로 내려간 left 낭떠러지 -> right 낭떠러지 -> 두 낭떠러지가 풀림으로써 풀린 parent node 이렇게 거슬러 올라가기 때문에

재귀함수로 분할정복해가면서 풀 수 있습니다. (무지개색깔 순서입니다)

코드

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readlines

class BST:
    def read(self):
        self.tree=input()
        self.tree=[int(str.rstrip()) for str in self.tree]
        self.answer=[]
        
    
    def solve(self,a):
        top=a[0]
        left=[item for item in a if item<top]
        right=[item for item in a if item>top]
        #left 가 있다면
        if len(left)>0:
            self.solve(left)
        #right 이 있다면
        if len(right)>0:
            self.solve(right)
    
        self.answer.append(top)
            
    def Answer(self):
        self.solve(self.tree)
        for node in self.answer:
            print(node,end='\n')
    
    
bst=BST()
bst.read()
bst.Answer()

처음에는 감을 전혀 못 잡아서 ‘분할 정복을 이용해야한다!’ 힌트를 보고 풀었습니다. 그러니까 제가 실제로 푼 건 50% 정도 ? 인 문제에요. 트리구조 문제는 확실히 재귀함수로 푸는 문제가 많은 것 같습니다.

그나저나 이번 주에는 논문을 많이 못 읽어서 큰 일이 난 것 같습니다. 시간 배분을 잘 해서 알고리즘은 기초 위주로 남는 시간에 공부하고 (저는 기초도 워낙에 부족하니😓) 논문 읽는 것을 놓지 말아야할 듯 합니다.

이번 주 주말을 갈아서 (그래봤자 토요일은 알바 후 놀기 계획이지만🙄) 트랜스포머 코드를 뜯어보면서 면밀히 이해해보고 어텐션이 활용된 시계열 분석 논문을 꼭 읽어보는게 목표입니다.