코딩테스트 - 트리(feat. Python)

2024.07.19·6분

트리에 대해 알아보자! 🌳

트리(Tree)란? 🤔

트리는 계층적인 구조를 가진 자료구조입니다. 루트(root) 노드에서 시작해 여러 개의 자식 노드를 가지며, 각각의 자식 노드도 다시 서브 트리를 형성합니다. 트리는 그래프의 한 종류로, 사이클이 없는 방향성 비순환 그래프(DAG)입니다.

노드(Node): 트리의 기본 요소로, 데이터와 자식 노드에 대한 참조를 가집니다. 루트 노드(Root Node): 트리의 최상위 노드입니다. 리프 노드(Leaf Node): 자식 노드가 없는 노드입니다. 간선(Edge): 노드 간의 연결을 나타냅니다. 서브 트리(Subtree): 트리의 부분 집합으로, 특정 노드와 그 노드의 모든 자식 노드를 포함합니다.

트리의 종류 🌳

이진 트리(Binary Tree): 모든 노드가 두 개 이하의 자식을 가지는 트리입니다. 이진 탐색 트리(BST, Binary Search Tree): 이진 트리의 일종으로, 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 가집니다. 균형 이진 트리(Balanced Binary Tree): 모든 리프 노드의 높이가 거의 같은 이진 트리입니다. 힙(Heap): 완전 이진 트리의 일종으로, 부모 노드가 자식 노드보다 크거나(최대 힙) 작은(최소 힙) 특성을 가집니다.

트리의 장단점 🎢

장점 계층적 데이터 표현: 데이터의 계층 구조를 표현하기에 적합합니다. 빠른 탐색: 이진 탐색 트리와 같이 탐색에 최적화된 구조를 가질 수 있습니다. 단점 복잡한 구현: 트리의 삽입, 삭제, 탐색 등의 연산이 비교적 복잡합니다. 불균형 문제: 트리가 불균형해지면 성능이 저하될 수 있습니다.

파이썬에서 트리 구현 💻

파이썬에서는 클래스를 사용해 트리를 구현할 수 있습니다.

text

1class Node:
2    def __init__(self, key):
3        self.left = None
4        self.right = None
5        self.val = key
6
7# 이진 트리 예제
8root = Node(1)
9root.left = Node(2)
10root.right = Node(3)
11root.left.left = Node(4)
12root.left.right = Node(5)
13
14print(root.val)  # 출력: 1
15print(root.left.val)  # 출력: 2

프로그래머스 트리 문제 🚀

문제: 길 찾기 게임 🗺️ 문제 설명 이진 트리에서 노드의 좌표를 기반으로 주어진 노드들을 삽입하여 트리를 구성하고, 전위(preorder) 순회와 후위(postorder) 순회의 결과를 반환하는 문제입니다.

입력 예시 nodeinfo = [[5, 3], [11, 5], [13, 3], [3, 5], [6, 1], [1, 3], [8, 6], [7, 2], [2, 2]] 출력 예시 [[7, 4, 6, 9, 1, 8, 5, 2, 3], [5, 1, 8, 9, 6, 4, 2, 3, 7]]

코드 작성하기 💻

text

1import sys
2sys.setrecursionlimit(10**6)
3
4class Node:
5    def __init__(self, key, x, y):
6        self.key = key
7        self.x = x
8        self.y = y
9        self.left = None
10        self.right = None
11
12def insert_node(root, node):
13    if node.x < root.x:
14        if root.left is None:
15            root.left = node
16        else:
17            insert_node(root.left, node)
18    else:
19        if root.right is None:
20            root.right = node
21        else:
22            insert_node(root.right, node)
23
24def preorder(node, traversal):
25    if node:
26        traversal.append(node.key)
27        preorder(node.left, traversal)
28        preorder(node.right, traversal)
29
30def postorder(node, traversal):
31    if node:
32        postorder(node.left, traversal)
33        postorder(node.right, traversal)
34        traversal.append(node.key)
35
36def solution(nodeinfo):
37    nodes = sorted([(i + 1, x, y) for i, (x, y) in enumerate(nodeinfo)], key=lambda x: (-x[2], x[1]))
38    root = Node(*nodes[0])
39    for node in nodes[1:]:
40        insert_node(root, Node(*node))
41
42    preorder_traversal = []
43    postorder_traversal = []
44
45    preorder(root, preorder_traversal)
46    postorder(root, postorder_traversal)
47
48    return [preorder_traversal, postorder_traversal]
49
50# 테스트
51nodeinfo = [[5, 3], [11, 5], [13, 3], [3, 5], [6, 1], [1, 3], [8, 6], [7, 2], [2, 2]]
52print(solution(nodeinfo))  # 출력: [[7, 4, 6, 9, 1, 8, 5, 2, 3], [5, 1, 8, 9, 6, 4, 2, 3, 7]]

설명 📋

노드를 y좌표 기준으로 내림차순, x좌표 기준으로 오름차순 정렬합니다. 정렬된 순서대로 트리를 구성합니다. 전위 순회와 후위 순회를 수행하여 결과를 반환합니다.

팁 🌟

재귀 사용: 트리의 탐색이나 순회에는 재귀 함수를 많이 사용합니다. 정렬 기준 이해: 문제의 요구사항에 맞게 정렬 기준을 설정하는 것이 중요합니다. 트리의 특성 이해: 트리의 기본적인 특성과 트리 순회의 방법(전위, 중위, 후위)을 이해하고 있으면 문제 해결에 큰 도움이 됩니다.