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

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

Development·
#노드#부모노드#자식노드#코딩테스트#코테#트리#파이썬
코딩테스트 - 트리(feat. Python)

트리에 대해 알아보자! 🌳

트리(Tree)란? 🤔

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

트리의 기본 개념 🌟

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

트리의 종류 🌳

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

트리의 장단점 🎢

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

파이썬에서 트리 구현 💻

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

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key


# 이진 트리 예제
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)


print(root.val)  # 출력: 1
print(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]]

코드 작성하기 💻

import sys
sys.setrecursionlimit(10**6)


class Node:
    def __init__(self, key, x, y):
        self.key = key
        self.x = x
        self.y = y
        self.left = None
        self.right = None


def insert_node(root, node):
    if node.x < root.x:
        if root.left is None:
            root.left = node
        else:
            insert_node(root.left, node)
    else:
        if root.right is None:
            root.right = node
        else:
            insert_node(root.right, node)


def preorder(node, traversal):
    if node:
        traversal.append(node.key)
        preorder(node.left, traversal)
        preorder(node.right, traversal)


def postorder(node, traversal):
    if node:
        postorder(node.left, traversal)
        postorder(node.right, traversal)
        traversal.append(node.key)


def solution(nodeinfo):
    nodes = sorted([(i + 1, x, y) for i, (x, y) in enumerate(nodeinfo)], key=lambda x: (-x[2], x[1]))
    root = Node(*nodes[0])
    for node in nodes[1:]:
        insert_node(root, Node(*node))


    preorder_traversal = []
    postorder_traversal = []


    preorder(root, preorder_traversal)
    postorder(root, postorder_traversal)


    return [preorder_traversal, postorder_traversal]


# 테스트
nodeinfo = [[5, 3], [11, 5], [13, 3], [3, 5], [6, 1], [1, 3], [8, 6], [7, 2], [2, 2]]
print(solution(nodeinfo))  # 출력: [[7, 4, 6, 9, 1, 8, 5, 2, 3], [5, 1, 8, 9, 6, 4, 2, 3, 7]]

설명 📋

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

팁 🌟

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

© 2026 raw