[BOJ] 2263 : 트리의 순회 [트리, 분할정복](Python)

문제 링크

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

2263번: 트리의 순회

소스 코드

import sys
sys.setrecursionlimit(10**6)

def main():
    n = int(input())
    in_order = list(map(int, input().split()))
    post_order = list(map(int, input().split()))

    position = [0] * (n+1)
    for i in range(n):
        position[in_order[i]] = i # inorder에서의 인덱스를 저장

    answer = []
    def preorder(in_start,in_end,post_start,post_end):
        if (in_start > in_end) or (post_start > post_end):
            return

        root = post_order[post_end]
        size = position[root] - in_start
        answer.append(root)
        
        preorder(in_start, position[root]-1, post_start, post_start+size-1) # 왼쪽
        preorder(position[root]+1, in_end, post_start+size, post_end-1) # 오른쪽

    preorder(0,n-1,0,n-1)
    print(*answer)

if __name__ == '__main__':
    main()

 

해설

• 트리, 분할 정복

전위, 중위, 후위 탐색도 처음 봤었는데 이걸 조합하니까 더 어지럽네요..

확실히 지금 배워두고 나중에 다시 또 공부해야 제 것으로 소화될 것 같은 기분입니다.

 

시간복잡도

리스트들을 입력으로 받고 초기화 하는 것은 뭐 당연히 O(N)입니다.

 

preorder 함수 내에서 명령들을 수행하는데 걸리는 시간은 O(N)입니다.

그런데 이 함수는 항상 재귀적으로 분할됩니다.

따라서 여기서 O(logN)의 시간이 추가적으로 걸립니다.

하지만 이는 N에 비하면 굉장히 작은 값이므로 마치 상수처럼 무시될 수 있습니다.

 

결과적으로 이 알고리즘의 시간복잡도는 O(N)이라고 볼 수 있습니다.

 

중위 순회의 인덱스 저장

중위 순회는 '루트 노드가 중간'인 방식을 말합니다.

따라서 우리는 루트 노드를 구하고 이를 기준으로 좌/우로 나눌 것이기 때문에 각 노드의 위치(인덱스)를 미리 기록해두는 것입니다.

position = [0] * (n+1)
for i in range(n):
    position[in_order[i]] = i # inorder에서의 인덱스를 저장

 

사이즈를 계산하여 좌우로 나누기

여기서 사이즈라 함은 쪼개질 좌/우 리스트의 크기 입니다.

우선 후위 순회의 특징에 따라 '후위 순회의 가장 마지막 값이 루트 노드'임을 이용합니다.

이제 그 위치를 기존에 중위 순회의 위치를 저장해두었던 리스트로부터 꺼냅니다.

이제 쪼개지는 리스트는 좌우가 각각 '시작부터 루트 노드 직전까지', '루트 노드 직후부터 끝까지'가 될 것입니다.

 

이때 주의할 것은 중위 순회와 후위 순회의 시작 끝점은 매번 달라질 수 있다는 것입니다.

따라서 갱신되는 사이즈를 어디에 더할지 잘 살펴보아야 합니다.

def preorder(in_start,in_end,post_start,post_end):
    if (in_start > in_end) or (post_start > post_end):
        return

    root = post_order[post_end]
    size = position[root] - in_start
    answer.append(root)

    preorder(in_start, position[root]-1, post_start, post_start+size-1) # 왼쪽
    preorder(position[root]+1, in_end, post_start+size, post_end-1) # 오른쪽