C++/자료구조7 [c++] Heap 1. 힙 : 관련 내용은 아래 글 참조 2023.11.20 - [Python/자료구조] - [python] 우선순위 큐 [python] 우선순위 큐 1. Heap(힙) : 주로 완전이진트리 기반으로 구현하며 정렬하는 용도의 이진트리이다 -> 마지막 레벨 노드 제외하고는 포화상태인 트리 cf> 힙 구현 : 완전이진트리 기반이기에 연결리스트보다 배열 growingupis.tistory.com 1-1. 힙 기본 동작 구성 swim_up : 특정 인덱스에서 위로 올라가며 조건 만족하면 swap sink_down : 특정 인덱스에서 아래로 내려가며 조건 만족하면 swap trim : 힙의 루트노드 반환 grow : 힙에 원소 삽입 swap : 노드 교환 Heap.h #pragma once #include usin.. 2023. 12. 8. [C++]AVL Tree 1. 균형이진탐색트리 (Adelson-Velskii&Landis) : 균형인수(Balance Factor:BF)를 이용하여 트리가 비균형 상태로 되면 스스로 노드들을 재배치하여 균형 상태를 유지하도록 하는 트리 : 평균, 최선, 최악 시간복잡도 : O(log(n)) : 모든 노드의 BF가 ±1이하이면 AVL트리라고 할 수 있음 cf. AVL의 자세한 동작은 아래 사이트에서 알 수 있음 https://www.cs.usfca.edu/~galles/visualization/AVLtree.html AVL Tree Visualzation www.cs.usfca.edu 1-1. 해당 트리 구성하는 동작 높이 균형 인수(BF) RR/LL/RL/LR 유형에 따른 rotation (=rebalancing) 노드 삽입 노.. 2023. 12. 7. [C++]Reverse doubly linked list with sentinel nodes 1. 연결리스트 구현 : 구현 방법 관련한 자세한 설명은 아래 글에 2023.11.29 - [C++/자료구조] - [C++]Doubly linked list with sentinel nodes [C++]Doubly linked list with sentinel nodes 1. 설명 : head와 tail이 직접 리스트의 첫번째 노드와 마지막 노드를 가리키는 것이 아닌 sentinel node로 설정하여 각각의 next/prev 노드가 첫번째 노드와 마지막 노드를 가리키게 함으로써 노드 삽입/ growingupis.tistory.com 2. 연결리스트 역순으로 첫 번째 노드부터 마지막 노드까지 순회 해당 노드의 next는 노드의 prev를 해당 노드의 prev는 노드의 next를 이때, 노드의 next/p.. 2023. 11. 29. [C++]Doubly linked list with sentinel nodes 1. 설명 : head와 tail이 직접 리스트의 첫번째 노드와 마지막 노드를 가리키는 것이 아닌 sentinel node로 설정하여 각각의 next/prev 노드가 첫번째 노드와 마지막 노드를 가리키게 함으로써 노드 삽입/삭제 구현을 좀 더 용이하게함 1-1. 함수 구성 begin : 리스트의 첫 번째 노드 (연결리스트의 head 노드의 next노드) end : 리스트의 마지막 노드가 아닌 마지막 노드를 지나간 다음의 노드 (연결리스트의 tail 노드) → 어떤 노드가 마지막 노드인지 알려면 next노드가 NULL인지 판단하는 게 아닌 tail노드인지 판단 isEmpty : 연결리스트가 비어있는지 판단 last : 리스트의 마지막 노드 Size : 리스트의 노드의 개수 ( 데이터가 있는 실질적인 노드 .. 2023. 11. 29. [c++] 스택 활용한 수식 계산 2023.09.15 - [C/알고리즘] - 스택 응용(수식 계산) 스택 응용(수식 계산) 1. 수식표기법 (1) 중위표기법(infix notation) : 연산자를 피연산자의 가운데 표기하는 방법 => 우리가 사용하는 방식 ex) A+B (2) 후위표기법(postfix notation) : 연산자를 피연산자 뒤에 표기하는 방법 => 컴 growingupis.tistory.com => 해당 알고리즘의 자세한 내용은 위의 글에 기재되어있다 1-1. 스택 구현 클래스 Stack.h #pragma once #define MAX_SIZE 100 #include template class Stack { private: T stack[MAX_SIZE]; int top; public: Stack():top(-1) { .. 2023. 11. 16. [C++]원형큐 circular_queue.cpp #include "cir_queue.h" #include using namespace std; bool cir_queue::IsEmpty() { return front == rear ; } bool cir_queue::IsFull() { return (rear+1)%size == front%size; } void cir_queue::enqueue(int item) { if (IsFull()) { cout 2023. 11. 14. 이전 1 2 다음
