기억을 위한 기록들

- 해시 테이블에서 데이터를 저장할 위치를 사용하기 위해 사용 - 길이가 긴 데이터 둘을 빨리 비교하기 위해 (단, 해시값이 다른 경우만 빨리 비교 가능) - 누출되면 곤란한 데이터의 원본을 저장하지 않기 위해 - 용도에 따라 해시 알고리즘의 요구수항이 조금씩 달라질 수 있다. - 어떤 입력값을 받으면 어떤 해시함수의 규칙에 의해 특정 비트라던가 어떤 정수로 된 값으로 변하게 하는데, 이렇게 변한 값을 해쉬값, 해쉬코드라고 부른다. - 함수임으로 입력값이 같으면 출력값도 일치 해야한다.

초안 : 2021년 1월 3일 1차 수정 : 2023년 4월 10일 해시테이블이란? 해시 테이블(Hash Table)은 키(Key)와 값(Value)으로 이루어진 데이터를 저장하기 위한 자료구조 중 하나입니다. 해시 테이블은 일반적으로 배열(Array)과 연결 리스트(Linked List)를 조합하여 구현됩니다. 해시 테이블의 핵심 아이디어는 키를 해시 함수(Hash Function)에 넣어서 고유한 해시 코드(Hash Code)를 생성하고, 이 해시 코드를 배열의 인덱스로 사용하여 값을 저장하는 것입니다. 이렇게 하면 키와 값 쌍을 빠르게 찾을 수 있습니다. 해시 테이블의 장점은 검색, 삽입, 삭제 등의 연산이 O(1)의 시간 복잡도로 수행된다는 것입니다. 하지만 해시 함수의 충돌이 발생할 경우 해결하..

초안 : 2020년 12월31일 1차수정 : 2023년 4월 10일 트리는 이름처럼 나무(tree)와 같은 자료구조이다. 뿌리를 가지고 뻗어져 나뭇가지에서 잎들이 있는 모습을 거꾸로 뒤집으면 자료구조에서의 트리가 된다. 트리 관련 용어 - 노드(Node) : 실제로 저장하는 데이터 - 루트 노드(Root Node) : 최상위에 위치한 데이터 - 리프 노드(Leaf Node) : 마지막에 위치한 데이터들 - 부모-자식 : 연결된 노드들 간의 상대적 관계 - 깊이(Depth) : 노드 -> 루트 경로의 길이 - 높이(Height) : 노드 -> 리프 경로의 최대 길이 - 하위 트리(Subtree) : 어떤 노드 아래의 모든 것을 포함하는 트리 트리의 용도 - 계층적 데이터를 표현한다. - 검색 트리를 통해 ..

std::set ? - std::set은 std::map과 동일한 자료구조를 사용하므로, 서능의 특성은 맵과 동일하다. - 차이점 한가지는 검색으로 반환된 항목이 std::set에 있다는 것이다. - key는 있지만 value는 없다 - 중복을 허락하지 않고, 정렬되는 집합 - 용도로 특정 값에 대해 검색을 빠르게 하고 싶을때 사용 std::set 사용법 https://blockdmask.tistory.com/79 [C++] set container 정리 및 사용법 안녕하세요. BlockDMask 입니다 ! 오늘은 연관 컨테이너 set, multiset, map, multimap 중 set에 대해 학습해보겠습니다. 순서는 set container -> set의 사용법 -> set의 생성자와 연산자 -> ..

std::map은? - 순서가 지정된 연관 컨테이너 - 항목을 삭제하는 경우를 제외하고 반복자와 참조가 절대 무효화 되지않는다. - 반복자는 항목을 정렬한 순서나 역순으로 정렬한 순서로 생성 - 노드기반 자료구조. 하지만 키의 값에 따라 노드를 자동으로 정렬 - 내부는 균형 이진트리로 구현 - 트리를 사용하지만 트리는 아니다. - 메모리 관리자와 매우 간단하고 예측 가능한 방법으로 상호작용 - 각 항목에 할당된 저장 공간의 크기는 모두 같음.(메모리 단편화 생길 가능성 낮음) - 검색은 std::vector로 std::lower_bound 사용하는게 더 빠름 사용 방법 : https://blockdmask.tistory.com/87 [C++] map container 정리 및 사용법 안녕하세요. Bloc..

hyo-ue4study.tistory.com/111 [자료구조]트리(Tree) 특징 / 운행 3가지 / C++ 트리는 이름처럼 나무와 같은 자료구조이다. 뿌리를 가지고 뻗어져 나뭇가지에서 잎들이 있는 모습을 거꾸로 뒤집으면 자료구조에서의 트리가 된다. 게임에서의 트리 게임 개발을 할때의 트리 hyo-ue4study.tistory.com #include #include #include using namespace std; class Node { public: Node() : mData(0) , mLeft(nullptr) , mRight(nullptr) , mRoot(nullptr) {} Node(int data) : mData(data) , mLeft(nullptr) , mRight(nullptr) , m..

정점 : 지점을 나타낸것 간선 : 2개 이상의 정점을 연결한 것 인접(Adjacent) : 나와 이웃하고 있는 정점 경로(Path) : 한 정점에서 다른 정점까지의 길 사이클(Cycle) : 단순 경로의 시작과 종료 정점이 동일한 경로 연결성 : 모든 정점이 서로 연결되어 있는것 방향성 그래프(Directed Graph) : 간선이 방향성을 가짐. 무방향성 그래프(Undirected Graph) : 간선에 방향성이 없음. 그래프는 정점의 집합? 간선의 집합? 정점의 집합 표현 방법 : 배열, 링크드 리스트 등 간선의 집합 표현 방법 : 간선은 그냥 선이 아니라 '인접관계'를 나타냄. 그래서 인접행렬(Adjacent Matrix) 또는 인접리스트(Adjacent List)로 표현 간선의 집한 표현방법 2가..

hyo-ue4study.tistory.com/127?category=907498 힙(Heap) 특징 힙은 완전 이진트리 자료구조의 일종. 힙에서는 항상 루트노드를 제거. 최소 힙 : 루트 노드가 가장 작은 값/ 값이 작은 데이터가 우선적으로 제거 최대 힙 : 루트 노드가 가장 큰값/ 값이 가장 큰 hyo-ue4study.tistory.com hyo-ue4study.tistory.com/189?category=862971 [C++]STL 우선순위 큐(priority_queue) 0. 기본 우선순위는 less (내림차순 높은값이 루트값) #include #include #include using namespace std; int main() { //priority_queue //아무것도 입력하지 않으면 기본..

- 힙은 힙 순서 속성(Heap Order Property)을 만족하는 완전 이진트리 자료구조의 일종. * 힙 순서 속성 : 트리 내의 모든 노드가 부모 노드보다 커야한다는 규칙 - 힙에서의 삭제는 항상 루트노드(최소값)를 제거. 왜냐! 가장 작은 데이터를 갖는 노드는 루트노드이기 때문. 삭제 후 에도 힙 순서속성 유지. - 최소 힙 : 루트 노드가 가장 작은 값/ 값이 작은 데이터가 우선적으로 제거 - 최대 힙 : 루트 노드가 가장 큰값/ 값이 가장 큰 데이터가 우선적으로 제거

#include using namespace std; template class Node { public: Node() : mdata(static_cast(0)) , mPre(nullptr) , mNext(nullptr) {}; Node(T _data) : mdata(_data) , mPre(nullptr) , mNext(nullptr) {} ~Node() { delete mPre; delete mNext; }; public: T mdata; Node * mPre; Node * mNext; }; template class DoubleLinked_List { public: DoubleLinked_List() : mHead(nullptr) , mTail(nullptr) {}; ~DoubleLinked_Lis..

이번엔 링크드 리스트다. 장점: - 새로운 노드의 추가/삽입/삭제 쉽고 빠름( 배열은 요소를 삽입하거나 제거하기 어렵) 단점 : - 다음 노드를 가리키려는 포인터 때문에 각 노드마다 4바이트의 메모리가 추가로 필요. - 특정 위치에 있는 노드를 얻는데 드는 비용이 크며, 속도도 느리다. 링크드리스트의 필요한 기본 연산은 5가지 - 노드생성/소멸 - 노드 추가 - 노드 탐색 - 노드 삭제 - 노드 삽입 코드 : #include using namespace std; template class Node { public: Node() {}; Node(T _data) :data(_data) {} ~Node() {}; T data; //현재 노드에 있는 데이터 Node * next; //현재 노드의 다음 노드를 가..

이번엔 스택이다. 스택 쌓자 스택 클래스와 해당 스택에 쌓는 노드 클래스 2개의 클래스로 구성 되어 있다. template class Node { public: Node(T _data) : mData(_data) {}; ~Node() { delete mNextNode; }; T mData; //현재 노드에 있는 데이터 Node* mNextNode; //현재 노드의 다음 노드를 가리키는 포인터 }; template class Stack { public: Stack() {}; ~Stack() {}; void Push(T newItem); T Pop(); T GetTopData(); bool IsEmpty() const; int GetStackSize() const; private: Node * mTopNod..