Algorithm/data structure4 [자료 구조] 트리(Tree) - 2. 파이썬 구현 * 해당 글은 패스트캠퍼스의 자료구조 알고리즘 강의를 듣고 정리하였습니다. 저작권은 패스트캠퍼스에 있습니다. 📌 노드 클래스 만들기 ✔️ Node 는 data값과 brach에 대한 정보를 가지고 있다. class Node: def __init__(self, value): self.value = value self.left = None self.right = None 📌 이진 탐색 트리 삽입/ 탐색 구현 ✔️ 이진 탐색 트리를 control 하는 class를 생성한다. => NodeMgmt class NodeMgmt: def __init__(self, head): # 제일 위에있는 root node를 설정 self.head = head def insert(self, value): # root node 부터.. 2021. 6. 25. [자료 구조] 트리(Tree) - 1.구조 이해 * 해당 글은 패스트캠퍼스의 자료구조 알고리즘 강의를 듣고 정리하였습니다. 저작권은 패스트캠퍼스에 있습니다. 📌 트리(Tree)란 Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 그 중에서 노드의 Branch가 최대 2개인 경우를 이진 트리라고 부른다. ✔️ 이진 트리 종류 이진 탐색 트리 완전 이진 트리 (Heap에서 사용) ... ✔️ 이진 트리에서 알아야 하는 용어 노드(Node) : 트리에서 데이터를 저장하는 기본 요소 (그림에선 동그라미임. data + branch 정보) 루트 노드(Root Node) : 트리 맨 위에 있는 노드 레벨 (Level) : 최상위 노드를 Lv0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄. 부모 노드 (Parent .. 2021. 6. 25. [자료구조] 힙(Heap) - 2. 파이썬 구현 * 해당 글은 패스트캠퍼스의 자료구조 알고리즘 강의를 듣고 정리하였습니다. 저작권은 패스트캠퍼스에 있습니다. 📌힙과 배열 일반적으로 힙 구현시 배열 자료구조를 활용한다. 주의할 점은 배열은 인덱스가 0부터지만, 힙 구현의 편의를 위해 root의 인덱스를 1로 지정한다. 부모 인덱스 번호 = 자식 노드 인덱스 번호 // 2 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 *2 + 1 📌 힙에서 데이터 삽입 구현 (Max Heap) ✔️ move_up, insert 구현 class Heap: def __init__(self, data): # 배열로 힙을 구현 self.heap_array = list() # heap_array[0]은 사용.. 2021. 6. 25. [자료구조] 힙(heap) - 1.구조 이해 * 해당 글은 패스트캠퍼스의 자료구조 알고리즘 강의를 듣고 정리하였습니다. 저작권은 패스트캠퍼스에 있습니다. 📌힙 (Heap) 이란 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Complete Binary Tree)이다. 여기서 완전 이진 트리는 노드를 삽입할 때, 최하단 왼쪽 노드부터 차례대로 삽입하는 트리이다. 따라서 완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다. 📌힙을 사용하는 이유 배열에 데이터를 넣고 최대값/ 최소값을 찾으려면 O(n)이 걸린다. 하지만 힙에 데이터를 넣고, 최대값과 최소값을 찾으면 O(logn)이 걸린다. ✔️ 이처럼 최대값 또는 최소값을 빨리 찾아야 하는 자료구조 및 알고리즘 구현에 활용된다. 📈 시간 복잡도 배열에 데이.. 2021. 6. 25. 이전 1 다음
