[골드 II] 4256번. 트리

 문제 

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

4256번: 트리

 사용 언어 

Python3

 풀이 과정 

이진트리의 전위 순회-중위 순회-후위 순회는 학부시절부터 공부했던 것이지만 이걸 코드로 구현한다 하더라도 각각을 구현했지 두 가지 트리 정보로 나머지 순회를 구하는 것은 처음이라 어떻게 풀어야 할 지 막막했다.

그래도 전위 + 중위 > 후위나 중위 + 후위 > 전위는 쉬운 편이고 전위 + 후위 > 중위가 생각할 점이 훨씬 많은 것 같아 나중에 따로 공부해보려 한다.

 

일단 전위 순회의 첫 번째 값이 전체 트리의 루트 노드가 된다는 것과 중위 순회의 루트 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리가 나뉜다는 것은 생각할 수 있었는데 그 이후에 어떻게 풀어야 할지 막막하고 (붙잡고 있을 시간도 없어서) 다른 블로그를 좀 참고했다.

그랬더니 한 번에 뜬 맞았습니다!!지만 뿌듯하진 못한😐

재귀도 직관적으로 이해하기가 힘들어서 내용을 출력해보며 이해했다.

+++)

여기까지가 스터디 하기 전에 준비한 내용이었는데 스터디 후에 블로그를 참고해서 시간복잡도와 공간복잡도가 개선되었다는 코드로 고쳐보았다. 그랬더니 무려...!? 두 번째 줄과 같이 208ms가 걸렸다. 메모리 역시 눈에 띄게 줄어든걸 확인할 수 있다. 이렇게까지 차이가 날줄이야😮

 제출 답안 

<처음 코드>

from sys import stdin

def PostOrder(preorder, inorder):
    if preorder:
        root = preorder[0] # 전위 순회의 첫 번째 값은 전체 트리의 루트노드
        mid = inorder.index(root) # 중위 순회에서는 루트를 기준으로 왼쪽이 서브트리/오른쪽 서브트리
        PostOrder(preorder[1:mid+1], inorder[:mid]) # 왼쪽 서브트리의 순회 결과 출력
        PostOrder(preorder[mid+1:], inorder[mid+1:]) # 오른쪽 서브트리의 순회 결과 출력
        print(root, end = " ") # 후위이므로 탐색 끝나고 출력

input = stdin.readline
T = int(input())
for _ in range(T):
    n = int(input())
    preorder = list(map(int, input().strip().split()))
    inorder = list(map(int, input().strip().split()))
    PostOrder(preorder, inorder)
    print()

<개선한 코드>

from sys import stdin

def PostOrder(preL, preR, inL, inR): # ex) 전위순회 왼쪽 서브트리 끝의 좌표값 = 0, 중위순회 오른쪽 서브트리 끝의 좌표값 = n - 1
    if preL > preR or inL > inR:
        return
    root = preorder[preL]
    mid = pos[root]
    left = mid - inL # 왼쪽 서브트리 노드 개수
    right = inR - mid # 오른쪽 서브트리 노드 개수
    PostOrder(preL + 1, preL + left, inL, inL + left - 1) # 왼쪽 서브트리 탐색
    PostOrder(preR - right + 1, preR, inR - right + 1, inR) # 오른쪽 서브트리 탐색
    print(root, end = " ") # 후위이므로 탐색 끝나고 출력

input = stdin.readline
T = int(input())
for _ in range(T):
    n = int(input())
    preorder = list(map(int, input().strip().split()))
    inorder = list(map(int, input().strip().split()))
    pos = [0 for _ in range(n + 1)] # [0] * (n + 1) 1번 노드부터 시작하므로 하나를 더 만들어 줌
    for i in range(n):
        pos[inorder[i]] = i # 각 노드번호 인덱스에 중위 순회의 인덱스 값을 넣어줌
    PostOrder(0, n - 1, 0, n - 1)
    print()

 공부한 내용 

트리

1. 이진트리

이진트리는 각 노드가 최대 두 개의 자식을 갖는 트리를 뜻한다. 즉, 각 노드는 자식이 없거나 한 개 이거나 두 개만을 갖는 것이다.  

2. 완전이진트리

1) 완전 이진트리는 마지막 레벨을 제외 하고 모든 레벨이 완전히 채워져 있다.

2) 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 한다.

3) 마지막 레벨 h에서 1~2h-1 개의 노드를 가질 수 있다.

4) 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다.

 

3. 이진탐색트리

이진 탐색 트리는 이진트리이면서 아래와 같은 속성을 갖는 트리를 뜻한다.

1) 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다.

2) 부모의 키가 왼쪽 자식 노드의 키보다 크다.

3) 부모의 키가 오른쪽 자식 노드의 키보다 작다.

4) 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

 

이진 탐색 트리는 효율적인 탐색을 위해 고안된 트리이다. 

 

출처: https://code-lab1.tistory.com/8

이진 트리의 순회

트리 순회란 트리 구조에서 각 노드를 모두 방문하는 것을 말한다.

트리의 순회를 말하면 대표적으로 전위 순회, 중위 순회, 후위 순회 3가지를 말할 수 있다. 추가적으로 계층별로 탐색하는 레벨 순회도 있는데 많이 사용하진 않는 것 같다.

 

1. 전위 순회(preorder)

트리의 전위 순회는 현재노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 순으로 순회하는 방식이다.

순회 순서 : A -> B ->D -> E -> G -> H ->C -> F -> I

 

코드 역시 현재 노드를 출력한 후, 왼쪽, 오른쪽 순서대로 함수를 호출한다.

def preorder(node):
    if node:
        print(tree[node][1], end=" ")
        preorder(tree[node][2])
        preorder(tree[node][3])

 

2. 중위순회(inorder)

트리의 전위 순회는 왼쪽 서브 트리 -> 현재노드 -> 오른쪽 서브 트리 순으로 순회하는 방식이다.

순회 순서 : D -> B -> G -> E -> H -> A -> C -> I -> F

 

코드는 왼쪽 함수 호출, 현재 노드 출력, 오른쪽 함수 호출 순서로 진행된다.

def inorder(node):
    if node:
        inorder(tree[node][2])
        print(tree[node][1], end=" ")
        inorder(tree[node][3])

 

3. 후위순회(postorder)

트리의 전위 순회는 왼쪽 서브 트리 -> 오른쪽 서브 트리 ->현재노드 순으로 순회하는 방식이다.

순회 순서 : D -> G -> H -> E -> B -> I -> F -> C -> A

 

후위 순회 또한 왼쪽 함수 호출, 오른쪽 함수 호출, 현재 노드 출력 순서로 진행된다.

def postorder(node):
    if node:
        postorder(tree[node][2])
        postorder(tree[node][3])
        print(tree[node][1], end=" ")

출처: https://sweetlog.netlify.app/data_structure/tree_traversal/

전위 순회, 중위 순회로 후위 순회 구하기 or 중위 순회, 후위 순회로 전위 순회 구하기

사실 참고한 블로그에 따르면 위와 같은 방식은 슬라이싱을 사용하기 때문에 생성된 신규 리스트를 재귀함수에 전달하는 식으로 메모리를 사용하고 따라서 공간복잡도가 좋지 않다고 한다. 따라서 위의 <개선한 코드>는 블로그를 참고하여 내 코드를 그에 맞게 수정한 것이다.

 

이를 해결하기 위해서는 크게 두 가지가 달라졌는데

1. 슬라이싱하지 않고 왼쪽, 오른쪽 서브트리를 나타내는 양 끝점의 좌표값을 넘겨줌

<바꾸기 전>

PostOrder(preorder[1:mid+1], inorder[:mid]) # 왼쪽 서브트리의 순회 결과 출력
PostOrder(preorder[mid+1:], inorder[mid+1:]) # 오른쪽 서브트리의 순회 결과 출력

<바꾼 후>

PostOrder(preL + 1, preL + left, inL, inL + left - 1) # 왼쪽 서브트리 탐색
PostOrder(preR - right + 1, preR, inR - right + 1, inR) # 오른쪽 서브트리 탐색

 

2. root 노드의 인덱스를 매 번 index() 내장함수를 이용해 계산하는 것이 아닌 pos 리스트에서 직접 접근

<바꾸기 전>

mid = inorder.index(root)

<바꾼 후>

pos = [0 for _ in range(n + 1)] # [0] * (n + 1) 1번 노드부터 시작하므로 하나를 더 만들어 줌
for i in range(n):
    pos[inorder[i]] = i # 각 노드번호 인덱스에 중위 순회의 인덱스 값을 넣어줌
mid = pos[root]

 

사실 2번은 pos를 사용하는 것이 이해가 안되어 그 부분만 이전과 같이 바꾸어보았는데 이만큼이나 차이가 났다... 나는 슬라이싱을 안 쓴 것만으로 이렇게 차이가 나는 줄 알았는데 pos의 역할도 컸던 것이다. index() 내장함수를 쓰는 것과 리스트의 인덱스에 직접 접근하는 것의 차이인 것 같은데 차이가 많이 난다는 것을 우연히 깨달았다.

결론은 값이 아니라 인덱스만 필요한데 재귀함수와 같이 많이 접근해야 하는 경우 처음에 for문으로 인덱스 리스트를 하나 만들어서 접근하는게 훨씬 효율적이라는 것!!!

 

출처:  https://8iggy.tistory.com/112 | https://kimmeh1.tistory.com/506