자료구조

Heap  : 힙은 각 노드의 key값을 저장하고 다음의 특성들을 만족하는 이진트리이다.     Heap's Property   1. Heap-order(순서조건) : 루트를 제외한 모든 internal node에 대해  key(v) >= key(parent(v)) 만족 → sibling node끼리는 상관 없음! 이진'탐색'트리일 필요 없음    2. Complete Binary Tree(구조조건)  - 힙의 마지막 노드는 최대 깊이의 가장 오른쪽 노드이다. → 왼쪽 노드부터 삽입. 오른쪽 노드만 존재하는 노드가 있다면 해당 트리는 완전이진트리가 아님   Height of a Heap : n개의 key를 갖고 있는 힙은 height(O(logn)) 을 갖는다.   ※ 증명 heap 의 높이만큼의 수행횟..

Priority Queue 큐는 먼저 삽입되는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. : 우선순위 큐는, 삽입 순서가 아닌, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조로 구현 방식에 따라 running-time이 달라질 수 있다.     Sequeunce-based priority queue(시퀀스 기반 우선순위 큐)1. Selected List(선택정렬) O(n^2): 1.unsorted list와 함께 구현되는 우선순위 큐 방식→ 무순리스트S → 우선순위 큐 P- 우선순위 큐에서 삭제할 때 모든 원소를 비교- 우선순위 큐에 삽입 하는 데 n개의 원소 삽입하므로 O(n)-time- 정렬순서로 삭제하는 데 n + (n-1) + ```  + 1 s..

일반적인 이진탐색트리의 경우, O(log n)의 시간복잡도를 보장하지 않습니다. skewed tree는 검색, 삽입, 삭제 모든 연산에서 O(n)의 수행시간을 갖고, complete tree는 검색은 트리의 높이에 따라 수행시간이 빠를 수 있지만, 삽입과 삭제 연산에서는 트리의 모양을 유지해줘야 하기 때문에 O(n)의 시간복잡도를 가질 수밖에 없기 때문입니다.  이를 보안하기 위해 고안된 이진탐색트리가 바로 ! BST ( Balanced Search Tree) 인데요, 모든 연산에서 O(log n)의 수행복잡도를 갖는다는 것이 장점입니다.  이 글에서는 BST 중 AVL Tree에 대해 다뤄보도록 하겠습니다.   BST는 모든 노드의 좌우 서브트리 높이의 차가 0또는 1인 균형트리입니다. 대표적인 BST..

Binary Search (이진탐색, 이분탐색) 이진탐색트리에 대해 알아보기 전에 '이진탐색' 이 무엇인지 알아야 합니다. 사전(Dictionay)에는 1) List 2) Search table 3) hash table 이 있었습니다. 이 중  2) 서치테이블은 정렬된 배열즉, sorted array를 통해 구현되는 사전을 의미합니다. 정렬된 '배열' 로 구현하는 이유는 이진탐색 방식을 수행하기 위함입니다.  탐색 연산 수행시 이미 배열이 정렬된 상태이기에, O(logn)-time 이 걸리지만, 삽입과 제거 연산에서는 '배열'이기 때문에 최악의 경우 n/2 만큼의 원소를 이동시켜야 하는 번거로움이 유발되며 이는 곧  O(n)-time 의 수행시간이 걸리게 됩니다.  find(k)O(log n)put(k)..

#include using namespace std;//노드 struct 구현 (data값과 nextNode가 존재)struct node { int data; node* nextNode;};//링크드 리스트 클래스 생성class LinkedList {private: node* head; node* tail;public: LinkedList() { head = NULL; tail = NULL; //head 와 tail의 포인터를 초기화; } //첫번째의 node 추가 void addFrontNode(int n); //마지막의 node 추가 void addNode(int n); //node 삽입 void insertNode(node* prevNode, int n); //node 삭제 void del..