[Day+12] 백준 알고리즘(트리)

오늘은 알고리즘 트리순회, 이진검색트리와 CS cache메모리에 대해서 공부를 했다.

 

1991 트리순회

 

전체 코드

N=int(input())


## 딕셔너리(사전형)을 이용한 풀이
tree ={}

for _ in range(N):
    root,left,right = input().split()

    tree[root] = [left, right]

def preorder(root):
    if root != '.':
        print(root,end='')
        preorder(tree[root][0])
        preorder(tree[root][1])

def inorder(root):
    if root!='.':
        inorder(tree[root][0])
        print(root,end='')
        inorder(tree[root][1])

def postorder(root):
    if root !='.':
        postorder(tree[root][0])
        postorder(tree[root][1])
        print(root,end='')

preorder('A')
print()
inorder('A')
print()
postorder('A')

 

이 문제는 전위순회, 중위 순회, 후위 순회를 한 결과를 각각 출력하는 문제이다.

 

전위 순회 : Root노드를 가장 먼저 방문

중위 순회 : 왼쪽 하위 트리를 방문 후 Root 노드를 방문

후위 순회 : 하위 트리를 모두 방문 후 Root 를 방문

 

위의 개념으로 보았을때 우리는 재귀를 통해서 출력하는 타이밍과 재귀를 하는 타이밍만 잘 생각하면 코드를 쉽게 짤 수 있다.

 

이 다음 문제인 이진 검색트리를 풀고 있는데 메모리 초과 문제가 뜬다.. 이를 해결하기 위한 방안을 계속 생각중이다.