cs51 [Priority Queue]26. Priority Queue(우선순위 큐) 목차 1. Priority Queue ADT(우선순위 큐) 2. minPQ, maxPQ 1. Priority Queue ADT(우선순위 큐) 1) 특징 - Priority Queue ADT(우선순위 큐)는 queue의 성질을 따르지만, 필요한, 그리고 중요한 내용을 먼저 꺼내는 방식을 말합니다. 2) 주요 기능 - insert(e): e라는 element를 insert하는 함수 - removeMin(): 가장 작은 key를 지닌 값을 제거하는 함수 3) 부가 기능 - min(): 가장 작은 key를 지닌 값을 반환, 제거하지는 않는다 - size(), empty() 2. minPQ, maxPQ Priority Queue는 크게 2가지로 나뉘는데, minPQ와 maxPQ로 나뉘어집니다. 이름에서 추측할 수.. 2021. 2. 26. [Trees]25. Binary Trees Traversal(이진 트리 탐색) 목차 1. Inorder Traversal(중위 순회) 2. Print Arithmetic Expressions 3. Evaluate Arithmetic Expressions 2. Euler Tour Traversal(오일러 탐색) 1. Inorder Traversal(중위 순회) Inorder Traversal(중위 순회)는 해당 node가 external이 아니라면, 1) 왼쪽 자식의 node를 방문한 후 2) 현재 node를 print 3) 그 후 오른쪽 자식의 node를 방문함 위의 과정을 거치는 방법을 말합니다. 이는 실제로 이진 탐색 트리를 그리는 경우, 활용될 수 있습니다. - x(v) = inorder traversal 순위 - y(v) = node v의 높이 2. Print Arithme.. 2021. 2. 25. [Trees]24. Binary Trees(이진 트리) 목차 1. Binary Trees(이진 트리) 2. Arithmetic Expression Tree 3. Decision Tree 4. 이진 트리의 종류 1. Binary Trees(이진 트리) Binary tree(이진 트리)는 다음과 같은 특징들을 따르는 tree를 말합니다. 1) 각각의 internal node는 최대 두개의 children을 지닌다(proper binary tree를 위해서는 정확히 2개) 2) node의 children은 ordered pair이다. 따라서 root 한개만 보유하고 있는 tree, 혹은 하나의 root와 root의 자식 2개로 이루어져 있는 tree도 binary tree의 일종이라고 할 수 있습니다. 2. Arithmetic Expression Tree 일반적인.. 2021. 2. 25. [Trees]23. Tree Traversal(트리 순회) 구현 목차 1. class Node, class Tree 2. def pre_order, def post_order 3. main 4. 예상 출력 1. class Node, class Tree class Node, class Tree는 전 게시물 21번에 구현한 것을 사용합니다. imgzon.tistory.com/62 [Trees]21. Tree 구현 목차 1. class Node 2. class Tree 3. def insert_node 4. def del_node 5. def print_chi 6. def print_sib 7. __main__ 8. 예상 입력, 출력 1. class Node class Node: def __init__(self, e: object): self.ele.. imgzon.tis.. 2021. 2. 25. [Trees]22. Tree Traversal(트리 순회 모음) 목차 1. Recursion(재귀) 1. Preorder Traversal(전위 순회) 2. Postorder Traversal(후위 순회) 1. Recursion(재귀) Recursion(재귀)는 자신을 정의할 때, 자기 자신(함수)를 재참조하는 방법을 말합니다. 재귀 함수는 함수를 정의할 때 자기 자신이 포함되며, 따라서 재귀 함수 설계시, 무한 루프에 빠지지 않도록 주의가 필요합니다. 2. Preorder Traversal(전위 순회) Node들의 관계로 이루어져 있는 Tree를 탐색하기 위해서는, 트리의 node들을 체계적인 방법으로 방문해야 합니다. 그 중에서 자신을 우선 방문하고, 자식 node들을 순차적으로 방문하는 방식을 Preorder Traversal(전위 순회)라고 합니다. 3. Po.. 2021. 2. 25. [Trees]21. Tree 구현 목차 1. class Node 2. class Tree 3. def insert_node 4. def del_node 5. def print_chi 6. def print_sib 7. __main__ 8. 예상 입력, 출력 1. class Node class Node: def __init__(self, e: object): self.element = e self.parent = None self.child = [] def insert_child(self, n): # 해당 node에 자식을 삽입할 때 사용하는 함수 self.child.append(n) def del_child(self, n): # 현재 node의 자식 node 중 특정 node를 제거 for i in self.child: if i==n: .. 2021. 2. 25. [Trees]20. Tree 목차 1. Tree(트리) 2. Tree Terminology 3. Tree ADT 1. Tree(트리) Tree(트리)는 hierachical structure(계층 구조)를 지닌 추상 모델입니다. Tree는 각각 element를 지닌 node들을 parent-child relation(부모-자식 관계)로 묶어서 분류한다는 점을 특징으로 삼을 수 있습니다. 2. Tree Terminology Tree를 구성하는 요소들은 다음과 같습니다. 1) Root: - parent를 가지지 않는 node이다. - (A) 2) Internal node: - 최소한 하나의 children를 지닌 node이다. - (A, B, C, F) 3) External node(leaf): - children를 지니고 있지 않는 .. 2021. 2. 21. [Vector/List]19. Double Linked List 구현 목차 1. class Node 2. class D_linked_list 3. insert() 4. erase 5. 테스트 1. class Node class Node: def __init__(self, e: object): self.element = e # node가 저장하는 element self.front = None # 앞에 있는 node의 주소 저장 self.back = None # 뒤에 있는 node의 주소 저장 2. class D_linked_list class D_linked_list: def __init__(self): self.head = Node('head') # head역할을 하는 node 지정 self.tail = Node('tail') # tail역할을 하는 node 지정 def .. 2021. 2. 21. 이전 1 2 3 4 5 6 7 다음
