CS17 [자료구조] Priority Queue 정의 Queue는 각 요소들 간의 우선순위(Priority)가 없이 FIFO(First In First Out, 선입선출법) 방식으로 데이터를 처리하였다. 반면, Priority Queue의 모든 요소는 로 이루어져 있다. 그리고 이 Key가 요소들 간의 우선순위를 결정한다. 가령, Priority(Key)의 값이 낮을수록 더 높은 우선순위를 부여한다고 가정하자. {, , , } 와 같은 Priority Queue가 있을 때, remove 연산을 수행하면 가장 Key 값이 낮은 가 Priority Queue에서 제거되고, {, , }가 되는 방식이다. 구현 Priority Queue를 구현하는 방식에는 다음 두 가지가 있다. 1. Unsorted List로 구현 2. Sorted List로 구현 위 두 .. 2024. 1. 17. [자료구조] Binary Search Tree 정의 다음과 같은 조건을 만족하는 binary tree를 binary search tree(BST) 라고 한다. 1. left subtree의 element들이 root element보다 작을 것. 2. right subtree의 element들이 root element보다 클 것. 가령, 1,2,3,4,5,6,7을 위 BST로 구현하면 다음과 같이 될 것이다. 특징 1. 앞서 binary tree를 포스팅하면서 binary tree의 순회 방식에는 pre-, in- , post- order의 3 가지 형태가 있다고 했었다. 이 중 inorder traversal은 root node의 방문 순서가 중간에 오는 방식이다. (left -> root -> right node 순서로 방문) 따라서, BST를 i.. 2024. 1. 12. [자료구조] Binary Tree Binary Tree는 ordered tree의 일종으로, 각 node가 최대 2개까지의 children을 가질 수 있는 tree이다. 이 때, 모든 node의 children 개수가 모두 0 또는 2이면 이 binary tree는 'proper'하다고 하고, 그렇지 않으면 'improper' 하다고 한다. Binary Tree의 특징 모든 node의 children 갯수가 2 이하라는 특징 때문에, (nonempty) binary tree는 다음과 같은 특징을 지닌다. 1. 높이가 h일 때, 전체 노드의 갯수는 h+1 보다 크거나 같고 2^(h+1)-1 보다 작거나 같다. 전체 노드의 갯수가 h+1인 경우는 각 internal node가 단 하나의 child만을 가질 때, 전체 노드의 갯수가 2^(h+.. 2024. 1. 10. [자료구조] Tree 앞서 다룬 자료 구조들과 다르게, 지금부터 다룰 tree는 비선형(non-linear) 자료구조이다. 즉, 하나의 element 뒤에 여러 개의 element가 올 수 있다. 보다 정확히 얘기하면 전자와 후자가 부모자식 관계로 얽힌 hierarchy가 있는 것이다. 앞서 다뤘던 array, linked list, queue, stack 등의 선형(linear) 자료구조가 어떤 element '앞, 뒤에' 어떤 element가 오는지에 초점이 맞춰저 있었다면, tree는 어떤 element가 어떤 element의 '부모인지 자식인지'에 초점이 맞춰져 있다고 이해하였다. Tree의 모든 element들은 (unique) parent를 가지고, 0개 이상의 children을 갖는다. 이 때, hierarchy.. 2023. 9. 16. 이전 1 2 3 4 5 다음
