[3주차] 알고리즘및코테_트리

About this offer

Chapter 04 트리 트리는 데이터를 부모와 자식의 관계로 연결하는 계층적 자료구조이다. 아래 내용은 제공된 목차에 맞춘 일반적인 자료구조 정리이며, 코드는 Python으로 작성했다. 높이와 레벨은 교재마다 기준이 다르다. 이 정리에서는 루트의 레벨을 1, 트리의 높이를 전체 레벨 수로 정한다. 04-1 트리란? 트리(Tree) : 노드들을 계층적으로 연결한 비선형 자료구조이다. 리스트와 스택처럼 데이터를 한 줄로 나열하는 구조와 달리, 하나의 노드에서 여러 갈래로 뻗어나갈 수 있다. 대표적인 예: 컴퓨터의 폴더 구조, 회사의 조직도, 가계도. 루트가 있는 트리는 하나의 루트와 그 아래에 연결된 여러 서브트리로 구성된다. 비어 있지 않은 트리에서 루트를 제외한 각 노드는 부모를 정확히 하나 가진다. 트리는 연결되어 있고 사이클이 없으며, 두 노드 사이의 단순 경로는 유일하다. 트리 관련 용어 다음 관계를 예로 사용한다. A의 자식: B, C B의 자식: D, E C의 자식: F D, E, F는 자식이 없다. 용어 의미 예시 노드(Node) 데이터를 저장하는 기본 단위 A, B, C, D, E, F 간선(Edge) 두 노드를 연결하는 선 A와 B의 연결 루트(Root) 트리의 가장 위에 있는 노드 A 부모(Parent) 바로 위에 연결된 노드 D의 부모는 B 자식(Child) 바로 아래에 연결된 노드 B의 자식은 D, E 형제(Sibling) 부모가 같은 노드 D와 E 조상(Ancestor) 루트에서 해당 노드까지의 경로에 있는 상위 노드 D의 조상은 A, B 자손(Descendant) 해당 노드 아래의 모든 노드 B의 자손은 D, E 단말 노드(Leaf) 자식이 없는 노드 D, E, F 내부 노드(Internal node) 자식이 하나 이상 있는 노드 A, B, C 노드의 차수(Degree) 해당 노드의 자식 수 B의 차수는 2 트리의 차수 모든 노드의 차수 중 최댓값 2 깊이(Depth) 루트에서 해당 노드까지의 간선 수 A는 0, D는 2 레벨(Level) 노드가 속한 층 A는 1, D는 3 높이(Height) 이 정리에서는 트리의 전체 레벨 수 3 경로(Path) 한 노드에서 다른 노드로 이동할 때 거치는 노드들의 순서 A → B → D 경로 길이 경로에 포함된 간선 수 A → B → D의 길이는 2 서브트리(Subtree) 한 노드와 그 노드의 모든 자손으로 이루어진 트리 B, D, E로 이루어진 트리 포리스트(Forest) 서로 분리된 트리들의 모임 루트 A를 제거한 뒤 남은 두 트리 꼭 기억할 성질 노드가 n개인 비어 있지 않은 트리의 간선 수는 n - 1개 이다. 루트에는 부모가 없고, 나머지 노드에는 부모가 하나씩 있다. 단말 노드의 차수는 0 이다. 빈 트리의 높이는 0, 루트 하나만 있는 트리의 높이는 1로 계산한다. 높이를 간선 수로 정의하는 교재에서는 루트 하나의 높이가 0이다. 문제를 풀 때 기준을 먼저 확인한다. 트리의 표현 방법 1. 부모-자식 관계를 그림으로 표현 루트를 위에 놓고, 자식 노드를 아래에 배치한다. 부모와 자식을 선으로 연결하면 계층 구조를 쉽게 파악할 수 있다. 2. 중첩된 괄호로 표현 부모 뒤의 괄호 안에 자식들을 나열한다. 위 예시: A(B(D, E), C(F)) A의 자식은 B와 C이며, B의 자식은 D와 E라는 뜻이다. 3. 들여쓰기로 표현 깊이가 깊어질수록 들여쓰기를 늘린다. 폴더 목록이나 목차에서 자주 사용하는 방식이다. A B D E C F 4. 프로그램 내부에서 표현 부모 배열 : 각 노드의 부모를 저장한다. 부모를 찾기 쉽다. 자식 리스트 : 각 노드에 자식 노드들의 목록을 저장한다. 자식 수가 서로 달라도 표현하기 쉽다. 첫째 자식-다음 형제 표현 : 첫 번째 자식과 바로 다음 형제를 가리키는 두 링크를 사용한다. 일반 트리는 자식 수에 제한이 없지만, 이진 트리는 왼쪽과 오른쪽 두 자식 위치를 사용한다. 04-2 이진트리 이진 트리(Binary tree) : 각 노드가 최대 두 개의 자식을 가지는 트리이다. 두 자식은 각각 왼쪽 자식 과 오른쪽 자식 으로 구분한다. 자식이 하나뿐이어도 왼쪽 자식인지 오른쪽 자식인지 구분해야 한다. 왼쪽 서브트리와 오른쪽 서브트리도 각각 이진 트리이다. 빈 트리도 이진 트리로 취급한다. 이진 트리의 기본 성질 높이 h와 레벨의 기준은 루트가 1이다. 레벨 i의 최대 노드 수: 2^(i - 1) 높이 h인 이진 트리의 최대 노드 수: 2^h - 1 높이 h인 이진 트리의 최소 노드 수: h 노드가 n개인 비어 있지 않은 이진 트리의 최소 높이: ceil(log2(n + 1)) 노드가 n개인 이진 트리의 최대 높이: n ceil 은 소수점 아래를 올림한다는 뜻이다. 예: 높이가 3이면 노드 수는 최소 3개, 최대 7개이다. 이진 트리의 종류 종류 특징 기억할 점 포화 이진 트리(Perfect binary tree) 모든 레벨이 노드로 가득 차 있다 높이 h일 때 노드 수는 2^h - 1 완전 이진 트리(Complete binary tree) 마지막 레벨을 제외한 모든 레벨이 가득 차고, 마지막 레벨은 왼쪽부터 빈틈없이 채워진다 배열로 표현하기 좋다 정 이진 트리(Full/Proper binary tree) 모든 노드의 자식 수가 0개 또는 2개이다 자식이 1개인 노드가 없다 편향 이진 트리(Skewed binary tree) 노드들이 왼쪽 또는 오른쪽 한 방향으로만 이어진다 연결 리스트처럼 길어진다 높이 균형 이진 트리 모든 노드에서 두 서브트리의 높이 차이를 제한한다 대표적으로 AVL 트리는 차이가 1 이하이다 포화·완전·정 이진 트리 구분 포화 : 모든 층이 꽉 찼는가? 완전 : 위층이 꽉 차 있고, 마지막 층도 왼쪽부터 채웠는가? 정 : 각 노드의 자식 수가 0개 또는 2개인가? 포화 이진 트리는 완전 이진 트리이면서 정 이진 트리이다. 완전 이진 트리라고 해서 반드시 포화 이진 트리이거나 정 이진 트리인 것은 아니다. 영문 용어와 한글 번역이 교재마다 다를 수 있으므로 이름보다 정의를 기준으로 구분한다. 주의: 이진 트리와 이진 탐색 트리는 다르다. 일반 이진 트리에는 값의 대소 관계에 따른 배치 규칙이 없다. 이진 트리의 표현 방법 1. 배열을 이용한 표현 루트를 인덱스 1에 저장하고, 노드의 위치에 따라 배열 인덱스를 정한다. 대상 현재 노드의 인덱스가 i일 때 부모 i // 2, 단 루트 제외 왼쪽 자식 2 * i 오른쪽 자식 2 * i + 1 예: 1번 노드의 왼쪽 자식은 2번, 오른쪽 자식은 3번에 저장한다. 존재하지 않는 위치는 None 등으로 표시한다. 장점: 부모와 자식의 위치를 계산으로 바로 구할 수 있다. 단점: 편향 트리처럼 비어 있는 자리가 많으면 배열 공간을 낭비한다. 완전 이진 트리에서는 중간에 빈자리가 없어 효율적이다. 루트를 인덱스 0에 저장할 때는 공식이 달라진다. 부모: (i - 1) // 2 , 단 루트 제외 왼쪽 자식: 2 * i + 1 오른쪽 자식: 2 * i + 2 2. 링크를 이용한 표현 각 노드에 데이터, 왼쪽 자식 참조, 오른쪽 자식 참조를 저장한다. class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right data : 노드에 저장할 값 left : 왼쪽 자식 노드. 없으면 None right : 오른쪽 자식 노드. 없으면 None 장점: 실제로 존재하는 노드만 만들 수 있고, 연결 구조를 바꾸기 쉽다. 단점: 자식을 가리키는 참조를 저장할 공간이 추가로 필요하다. 04-3 이진 트리의 연산 이진 트리의 표준순회 순회(Traversal) 란 트리의 모든 노드를 정해진 순서에 따라 한 번씩 방문하는 것이다. 방문은 해당 노드의 데이터를 출력하거나 계산에 사용하는 등의 처리를 뜻한다. 표준 순회 세 가지는 모두 깊이 우선 탐색(DFS)에 해당한다. 순회 방식 방문 순서 루트 처리 시점 대표 활용 전위 순회(Preorder) 루트 → 왼쪽 → 오른쪽 가장 먼저 계층 구조 출력, 전위 수식 중위 순회(Inorder) 왼쪽 → 루트 → 오른쪽 가운데 이진 탐색 트리의 정렬 출력, 중위 수식 후위 순회(Postorder) 왼쪽 → 오른쪽 → 루트 가장 나중 수식 계산, 자식부터 처리하는 연산 순회 예시 다음과 같은 이진 트리를 가정한다. A: 왼쪽 B, 오른쪽 C B: 왼쪽 D, 오른쪽 E C: 왼쪽 F, 오른쪽 G D, E, F, G: 단말 노드 순회 결과 전위 A B D E C F G 중위 D B E A F C G 후위 D E B F G C A 재귀로 구현하기 def preorder(node): if node is not None: print(node.data, end=" ") preorder(node.left) preorder(node.right) def inorder(node): if node is not None: inorder(node.left) print(node.data, end=" ") inorder(node.right) def postorder(node): if node is not None: postorder(node.left) postorder(node.right) print(node.data, end=" ") node is None 이면 더 내려갈 노드가 없으므로 호출을 끝낸다. 세 함수는 현재 노드를 처리하는 print의 위치 만 다르다. 왼쪽과 오른쪽 서브트리에서도 같은 규칙을 반복한다. n개 노드를 모두 방문하므로 시간 복잡도는 O(n) 이다. 재귀 호출 스택의 추가 공간은 높이 h에 대해 O(h) 이다. 암기: 전위는 루트를 앞에, 중위는 가운데에, 후위는 뒤에 처리한다. 주의: 중위 순회의 결과가 정렬되는 것은 이진 탐색 트리 일 때이다. 일반 이진 트리에서는 정렬이 보장되지 않는다. 레벨 순회 레벨 순회(Level-order traversal) : 루트부터 시작하여 같은 레벨의 노드를 왼쪽에서 오른쪽으로 방문한다. 위에서 아래로 한 층씩 방문하는 너비 우선 탐색(BFS)이다. 먼저 발견한 노드를 먼저 처리하기 위해 큐(Queue) 를 사용한다. 동작 과정 루트를 큐에 넣는다. 큐의 맨 앞에서 노드를 꺼내 방문한다. 그 노드의 왼쪽 자식, 오른쪽 자식을 순서대로 큐에 넣는다. 큐가 빌 때까지 반복한다. 위 예시의 레벨 순회 결과: A B C D E F G from collections import deque def levelorder(root): if root is None: return queue = deque([root]) while queue: node = queue.popleft() print(node.data, end=" ") if node.left is not None: queue.append(node.left) if node.right is not None: queue.append(node.right) append() : 큐의 뒤에 넣는다. popleft() : 큐의 앞에서 꺼낸다. 시간 복잡도: O(n) 최대 레벨 너비를 w라고 할 때 큐의 추가 공간: O(w) , 최악의 경우 O(n) Python 리스트의 pop(0) 은 원소 이동이 필요하므로, 큐에는 deque 를 사용한다. 이진 트리의 연산들 1. 전체 노드 수 구하기 전체 노드 수 = 왼쪽 서브트리 노드 수 + 오른쪽 서브트리 노드 수 + 1 def count_nodes(node): if node is None: return 0 return count_nodes(node.left) + count_nodes(node.right) + 1 빈 트리에는 노드가 없으므로 0을 반환한다. 마지막의 + 1 은 현재 노드 자신을 센 것이다. 2. 단말 노드 수 구하기 def count_leaves(node): if node is None: return 0 if node.left is None and node.right is None: return 1 return count_leaves(node.left) + count_leaves(node.right) 왼쪽과 오른쪽 자식이 둘 다 없어야 단말 노드이다. 단말 노드를 만나면 1을 반환하고, 나머지는 양쪽 결과를 더한다. 3. 트리의 높이 구하기 높이 = max(왼쪽 높이, 오른쪽 높이) + 1 def height(node): if node is None: return 0 return max(height(node.left), height(node.right)) + 1 두 서브트리 중 더 깊은 쪽을 기준으로 한다. 현재 노드가 차지하는 한 층을 더한다. 예: 왼쪽 높이 2, 오른쪽 높이 4이면 현재 트리 높이는 5이다. 4. 특정 값 탐색하기 def find(node, target): if node is None: return None if node.data == target: return node result = find(node.left, target) if result is not None: return result return find(node.right, target) 현재 노드 → 왼쪽 → 오른쪽 순서로 찾는다. 찾으면 해당 노드, 찾지 못하면 None 을 반환한다. 일반 이진 트리에는 값의 배치 규칙이 없으므로 최악의 경우 모든 노드를 확인한다. 연산 시간 복잡도 재귀 추가 공간 전체 노드 수 O(n) O(h) 단말 노드 수 O(n) O(h) 높이 O(n) O(h) 값 탐색 최악 O(n) O(h) 삽입과 삭제는 트리의 목적에 따라 규칙이 다르다. 일반 이진 트리, 이진 탐색 트리, 힙에 동일한 삽입·삭제 규칙을 적용하지 않는다. 테스트 프로그램 앞에서 정의한 Node 클래스와 순회·연산 함수들 아래에 다음 코드를 붙여 실행한다. root = Node( "A", Node("B", Node("D"), Node("E")), Node("C", Node("F"), Node("G")) ) print("전위:", end=" ") preorder(root) print() print("중위:", end=" ") inorder(root) print() print("후위:", end=" ") postorder(root) print() print("레벨:", end=" ") levelorder(root) print() print("전체 노드 수:", count_nodes(root)) print("단말 노드 수:", count_leaves(root)) print("높이:", height(root)) result = find(root, "E") print("탐색 결과:", result.data if result is not None else "없음") 예상 출력: 전위: A B D E C F G 중위: D B E A F C G 후위: D E B F G C A 레벨: A B C D E F G 전체 노드 수: 7 단말 노드 수: 4 높이: 3 탐색 결과: E 추가 확인 기준: 빈 트리: 전체 노드 수 0, 단말 노드 수 0, 높이 0 루트만 있는 트리: 전체 노드 수 1, 단말 노드 수 1, 높이 1 노드 3개가 한 방향으로 이어진 트리: 전체 노드 수 3, 단말 노드 수 1, 높이 3 04-4 모스코드결정트리 결정 트리(Decision tree) : 조건이나 입력에 따라 가지를 선택하며 결과를 찾는 트리이다. 모스 코드는 점 . 과 선 - 의 조합으로 문자를 표현한다. 점과 선이라는 두 가지 입력을 이진 트리의 두 방향에 대응시킬 수 있다. 여기서는 점은 왼쪽, 선은 오른쪽 으로 이동하도록 정한다. 결정 트리를 이용한 모스 코드의 디코딩 모스 코드 트리의 구조 루트는 문자를 나타내지 않는 시작 지점이다. 루트에서 왼쪽으로 한 번 이동하면 E( . ), 오른쪽으로 한 번 이동하면 T( - )이다. 루트에서 특정 노드까지 이동한 경로가 그 노드의 모스 코드이다. 문자 모스 코드 루트에서의 이동 E . 왼쪽 T - 오른쪽 I .. 왼쪽 → 왼쪽 A .- 왼쪽 → 오른쪽 N -. 오른쪽 → 왼쪽 M -- 오른쪽 → 오른쪽 S ... 왼쪽 → 왼쪽 → 왼쪽 O --- 오른쪽 → 오른쪽 → 오른쪽 디코딩 과정 현재 위치를 루트로 설정한다. 입력 기호가 . 이면 왼쪽 자식으로 이동한다. 입력 기호가 - 이면 오른쪽 자식으로 이동한다. 한 문자의 코드가 끝나면 현재 노드에 저장된 문자를 읽는다. 다음 문자를 해독할 때는 다시 루트로 돌아간다. 예: ... --- ... ... → 왼쪽 세 번 → S --- → 오른쪽 세 번 → O ... → 왼쪽 세 번 → S 최종 결과: SOS 문자 경계가 중요한 이유 E의 코드 . 은 A의 코드 .- 의 앞부분이기도 하다. 따라서 문자가 저장된 노드에 도착했다고 즉시 한 글자를 확정하면 안 된다. 모스 코드 트리에서는 내부 노드에도 문자가 저장될 수 있다. 실제 신호에서는 시간 간격으로, 텍스트 예시에서는 공백으로 글자를 구분한다. 텍스트에서 단어 사이를 / 로 표시하기도 하지만, 이는 구분을 위한 표기 관례이다. def decode_letter(root, code): if not code: raise ValueError("빈 코드는 해독할 수 없습니다.") node = root for symbol in code: if node is None: raise ValueError("트리에 없는 코드입니다.") if symbol == ".": node = node.left elif symbol == "-": node = node.right else: raise ValueError("점과 선만 입력할 수 있습니다.") if node is None or node.data is None: raise ValueError("문자가 배정되지 않은 코드입니다.") return node.data 위 함수는 모스 코드 규칙에 맞는 트리가 이미 만들어져 있다고 가정한다. 코드 길이가 k이면 이동 횟수도 k이므로 시간 복잡도는 O(k) 이다. 트리 구축 비용을 제외하고, 총 m개 기호를 해독하는 시간은 O(m) 이다. 04-5 수식트리 수식 트리(Expression tree) : 연산자와 피연산자의 관계를 트리로 표현한 것이다. 여기서는 + , - , * , / 처럼 피연산자가 두 개인 이항 연산자를 사용한다. 단말 노드 에는 숫자나 변수 같은 피연산자를 저장한다. 내부 노드 에는 연산자를 저장한다. 왼쪽 서브트리는 왼쪽 피연산자, 오른쪽 서브트리는 오른쪽 피연산자를 나타낸다. 각 연산자 노드에 자식이 둘씩 있으므로, 이 조건의 수식 트리는 정 이진 트리이다. 예: (3 + 2) * (4 - 1) 루트: * 루트의 왼쪽 자식: + , 오른쪽 자식: - + 의 왼쪽·오른쪽 자식: 각각 3, 2 - 의 왼쪽·오른쪽 자식: 각각 4, 1 수식 트리의 계산 계산에는 후위 순회를 사용한다 연산자를 계산하려면 양쪽 피연산자의 값을 먼저 알아야 한다. 따라서 왼쪽 계산 → 오른쪽 계산 → 현재 연산자 적용 순서로 처리한다. 예: (3 + 2) * (4 - 1) 왼쪽 서브트리에서 3 + 2 = 5 를 계산한다. 오른쪽 서브트리에서 4 - 1 = 3 을 계산한다. 루트에서 5 * 3 = 15 를 계산한다. def evaluate(node): if node is None: raise ValueError("빈 수식입니다.") if node.left is None and node.right is None: return float(node.data) if node.left is None or node.right is None: raise ValueError("연산자의 피연산자가 부족합니다.") left_value = evaluate(node.left) right_value = evaluate(node.right) if node.data == "+": return left_value + right_value if node.data == "-": return left_value - right_value if node.data == "*": return left_value * right_value if node.data == "/": return left_value / right_value raise ValueError("지원하지 않는 연산자입니다.") 이 코드는 피연산자가 숫자인 수식을 계산한다. 변수까지 계산하려면 변수 이름에 대응하는 값을 별도로 제공해야 한다. 뺄셈과 나눗셈에