자료구조
| 니앙팽이 - 자료구조 | 4 | 해시 테이블 노트
해시 테이블 개요 접근 삭제 시간 복잡도 : O(1) 개빠르다 Collision : 동일한 key 값에 복수 개의 데이터가 하나의 테이블에 존재할 수 있게 되는 것 해시 함수 인덱스 값을 설정해주는 함수 보통 나머지연산은 큰 소수로 이뤄지면 좋다. 단 등가교환이 있다 과유불급 좋은 해시 함수는 최대한 Collsion이 적어야한다. Collsion이 많아지면 O(1)에서 O(n)으로 가까워진다. 그런데 너무 심각하게 Collsion이 있다면 메모리를 너무 차지하게 된다. Collsion의 해결 개방 주소법 linear 하게 버킷을 탐색한다 Double hashing probing 하나의 해쉬 함수에서 충돌이 발생하면 2 차 해쉬 함수를 이용해 새로운 주소를 할당한다. 분리 연결법 동일버킷 : 연결 리스트를..
| 니앙팽이 - 자료구조| 3 | 트리, 이진트리 노트
트리 트리의 구성 요소 ❗ 기본 트리의 구성 요소 노드 간선 노드와 노드를 연결하는선 서브 트리 트리를 구성하는 작은 트리 트리는 재귀적이다. ❗ 관점에 따른 노드 분류 👉 위치에 대한 관점 루트 노드 ■ 맨 꼭데기 노드 단말 노드 ■ 자식이 없는 노드 내부 노드 ■ 단말 노드 이외 노드 👉 상위, 하위 관점 부모 노드 ■ 자식을 가지고 있는노드 자식 노드 ■ 부모가 있는 노드 형제 노드 ■ 부모가 있고 Depth가 동일한 노드 트리의 분류 ❗ depth / level 트리의 깊이혹은 높이라 부른다 어떤 트리의 depth / level을 물어볼때 최대 depth를 말하면 된다. 가족관계 현재 노드 : i; 부모 : i/2; 왼쪽 : 2i; 오른쪽 : 2i + 1; 👉 이진 트리 노드 하나를 중심으로 2개..
|자료구조| 3 | BinSearchTree | 이진 탐색 트리
이진 탐색 트리 구현 이진 탐색트리 구현은 다음 깃허브를 참고했습니다 https://gist.github.com/harish-r/a7df7ce576dda35c9660 Visual Studio 솔루션 구성 구현부 노드 - 헤더 : Node.h #pragma once class Node { friend class BinSearchTree; public: int data; Node* lch; Node* rch; }; 이진 탐색 트리 - 헤더 : BinSearchTree.h #pragma once #include "Node.h" class BinSearchTree { friend class Node; private: Node* mRoot; Node* mMakeEmpty(Node *_t); Node* mInser..
| 니앙팽이 - 자료구조| 2 | 스택,큐 노트
스택과 큐 스택 ❗ 스택의 특징 👉 자료구조 LIFO (후입선출) 👉 메모리에 올라간 구조 프로세스 메모리 구조 코데힙스 코드 영역 컴파일후 생성된 기계어 CPU가 기계 명령어를 가져올때 사용되는 영역 프로그램 종료후에도 남아있음 데이터 영역 전역변수 정적변수 컴파일후 할당됨 프로그램 종료후에 같이 삭제 힙 영역 동적할당된 메모리 영역 new delete, malloc free 컴파일중에 할당 프로그램 종료후에 같이 삭제 스택 영역 함수, 지역변수, 매개변수 스택 프레임이라고 함수의 호출 정보를 스택처럼 쌓도록 동작하는 구조 컴파일중에 할당 프로그램 종료후에 같이 삭제 👉 미로찾기 그래프탐색 DFS는 보통 재귀로 해결하기도 하지만 스택을 이용해서도 DFS를 진행할 수 있다. 코드는 다음과 같다 미로찾기 ..
| 니앙팽이 - 자료구조| 1 | 연결 리스트 노트
배열과 연결리스트 Quest ❗ 배열과 연결리스트의 차이 ___ 배열 연결리스트 형식 정적 동적 접근 random Access : O(1) Sequential Access : O(N) 삽입 맨앞 O(N) 맨뒤 O(1) 맨앞O(1) 맨뒤 O(N) 삭제 맨앞 O(N) 맨뒤 O(1) 맨앞O(1) 맨뒤 O(N) 연결리스트 1. 더미노드 ❗ 더미노드는 왜 쓰는건가? 연결리스트(더미노드 없음) 구현 - 2. 원형 연결리스트 ❗ 작동방식 👉 구성은? list->tail 원형리스트의 마지막임 list->tail->next (내지는 head) 원형리스트의 시작임 👉 복잡도는? ___ 연결리스트 형식 동적 접근 Sequential Access : 맨앞 : O(1) 맨뒤 : O(N) 삽입 맨뒤 O(1) 삭제 맨앞O(1) 원..
|자료구조| 1 | Double LinkedList_3 | 이중 연결 리스트
양방향 연결 리스트 구현 Visual Studio 솔루션 구성 구현부 노드 - 헤더 : Node.h #pragma once class Node { friend class D_List; protected: int data; Node* next; Node* prev; }; 양방향 연결 리스트 - 헤더 : D_List.h #pragma once #include"Node.h" class D_List { friend class Node; private: Node* mHead; Node* mTail; Node* mCur; int mLength = 0; public: D_List(); int length(); void insert(int); int front(); int back(); void pop_front();..
|자료구조| 1 | Circular LinkedList_2 | 원형 연결 리스트
원형 연결 리스트 구현 Visual Studio 솔루션 구성 구현부 노드 - 헤더 : Node.h #pragma once #include "CircuitLinkedList.h" class Node { friend class CircuitLinkedList; protected : int data; Node* next; }; 원형 연결 리스트 - 헤더 : CircuitLinkedList.h #pragma once #include "Node.h" class CircuitLinkedList { friend class Node; private : //멤버변수 Node* tail; int length; public : //매서드 CircuitLinkedList(); void LInsert(int data); int..
|자료구조| 1 | LinkedList_1 | 연결리스트(더미노드 없음)
연결리스트 구현 Visual Studio 솔루션 구성 구현부 헤더 : CrocusLinkedList.h #pragma once class CrocusLinkedList { private : int m_data = 0; CrocusLinkedList* next; public : CrocusLinkedList(); void SetData(int _data); int GetData(); void Linking(CrocusLinkedList* _Node1); void SearchAll(CrocusLinkedList* head); }; 메소드 : CrocusLinkedList.cpp #define _CRTDBG_MAP_ALLOC #include "CrocusLinkedList.h" #include #include..