자료구조 (34) 썸네일형 리스트형 [ 자료구조 ] 해시 테이블 - 03 . 개방 주소법 [ 개방 주소법 ] [ 개방 주소법 ] 개방 주소법 (Open Addressing)은 충돌이 일어날 떄 해시 함수에 의해 얻어진 주소가 아니라 다른 주소를 사용하게 허용하는 충돌해결 알고리즘이다 . 충돌이 일어나면 해시 테이블 내의 새로운 주소를 탐사 (Probe)하여 충돌된 데이터를 입력하는 방식으로 동작한다 . cf ) 체이닝은 오픈 해싱기법이자 폐쇄 주소법(Closed Addressing) 알고리즘이기도 하다 . 탐사방식은 다음과 같이 나뉜다 선형탐사 제곱탐사 이중해싱 [ 선형 탐사 ] 가장 간단한 탐사방법이다 . 해시 함수로부터 얻어낸 주소에 이미 다른 데이터가 있다면 , 해당 주소에서 고정폭 (1,2 .. )으로 빈 곳을 찾을때까지 다음 주소로 이동한여 찾는다면 그곳에 데이터를 입력한다 . ex.. [ 자료구조 ] 해시 테이블 - 02 . 충돌 해결 [ 충돌 해결 ] [ 충돌 ] 해시 함수가 서로 다른 입력값에 대해 동일한 해시 테이블 주소를 반환하는 것을 일컬어 "충돌"이라고 한다 . 어떠한 해시 함수든 , 모든 입력값에 대해 고유한 해시값을 만들지는 못한다 . 즉 ,충돌은 불가피하다 . 충돌의 해결방법은 크게 두가지이다 . 개방 해싱 (Open Hashing) : 해시 테이블의 주소 바깥에 새로운 공간을 할당 , 문제를 해결 폐쇄 해싱 (Closed Hashing) : 처음에 주어진 해시테이블의 공간 안에서 문제를 해결 [ 체이닝 ] 체이닝은 개방 해싱 기반의 충돌 해결 기법이다 . 해시 함수가 서로 다른 키에 대해 같은 주소값을 반환해서 충돌이 발생하면 , 각 데이터를 해당 주소에 있는 링크드 리스트에 삽입 , 문제를 해결하는 기법이다 . 체이.. [ 자료구조 ] 해시 테이블 - 01 . 해시와 해시 테이블 [해시에 관하여] [들어가기 전에] 1 . 이진 탐색이 아무리 빠르다 하더라도 인덱스를 이용 , 바로 목표 요소에 접근하는 배열에 비하면 아쉬운 점이 있다 . 만약 , 배열처럼 데이터 값을 이용하여 각 요소가 담길 주소를 계산하고 , 이 주소에 데이터를 담는다면 ? 2.해시는 해시 테이블 , 암호화 , 문자열 검색등 많은 알고리즘에 응용되는 알고리즘이다 . 그렇다면 해시란 ? [해시] Hash (해시)란 무엇일까? 영단어를 보면 , "잘게 자른 고기를 양파,감자와 같은 다른 재료와 함께 튀겨 한 덩어리로 만든 요리"를 뜻한다 . 이와 같이 해시는 데이터를 입력받으면 완전히 다른 모습의 데이터로 바꾸어 놓는 작업이다 . 해시는 다음의 용도로 쓰인다 . 해시 테이블 : 해시 테이블은 데이터의 해시값을 테이블.. [자료구조] 우선순위 큐와 힙 - 03 . 우선순위 큐 구현 [우선순위 큐 구현] [PQ.h] #ifndef PQ_H #define PQ_H #include #include #include typedef int PriorityType; //노드 (우선순위가 추가됨) typedef struct tagPQNode { PriorityType Priority; void* Data; }PQNode; //우선순위 큐 typedef struct tagPriorityQueue { PQNode* Nodes; int Capacity; int UsedSize; }PriorityQueue; //큐의 생성 PriorityQueue* PQ_Create(int Initialize); //큐의 삭제 void PQ_Destroy(PriorityQueue* PQ); //노드의 삽입 void PQ.. [자료구조] 우선순위 큐와 힙 - 02 . 힙 구현 [힙 구현] [Heap.h] #ifndef Heap_H #define Heap_H #include #include #include typedef int ElementType; typedef struct tagHeapNode { ElementType Data; }HeapNode; typedef struct tagHeap { //노드 배열 HeapNode* Nodes; //최대용량 int Capacity; //사용중인 사이즈 int UsedSize; }Heap; //힙의 생성 Heap* Heap_Create(int Initialize); //힙의 삭제 void Heap_Destroy(Heap* heap); //삽입 void Heap_Insert(Heap* heap, ElementType NewData); /.. [자료구조] 우선순위 큐와 힙 - 01 . 우선순위 큐와 힙 [ 들어가기 전에 ] [ 일상에서의 우선순위 큐 ] 일정한 루틴으로 살아가는 사람에게 병원 , 미팅등의 우선순위가 높은 일이 생기면 그것을 먼저 처리한다 . 혹은 , 우체국에서 먼저 들어온 일반우편보다 빠른 등기를 먼저 처리한다 . 위의 경우들은 일이 들어온 순서가 아닌 , 우선순위에 따라 일을 처리한다 . 우선순위큐 역시 마찬가지이다 . [ 우선순위 큐 ] [ 우선순위 큐의 정의 ] 큐 (Queue)는 먼저 들어간 요소가 먼저 나오는 (FIFO)자료구조이다 . 우선순위 큐는 큐와 같이 동작하지만 "우선순위 속성을 가지는 데이터를 다룬다"는 점에서 차이가 있다 . 둘의 차이는 삽입과 제거 연산이 어떻게 동작하느냐에 있다 . 우선순위큐는 새 요소에 우선순위를 부여하여 큐에 삽입하고 가장 높은 우선순위를 갖.. [ 자료구조 ] 탐색 - 04 - 3 . 레드 블랙 트리 <구현> [RBT.h] #ifndef RBT #define RBT #include #include typedef int ElementType; enum NodeColor { Red, Black }; typedef struct tagRBTNode { //부모 struct tagRBTNode* Parent; //왼쪽 자식 struct tagRBTNode* Left; //오른쪽 자식 struct tagRBTNode* Right; //색 NodeColor Color; //데이터 ElementType Data; }RBTNode; //트리의 삭제 void RBT_DestroyTree(RBTNode* Tree); //노드의 생성 RBTNode* RBT_CreateNode(ElementType NewData); //노드의 소멸.. [ 자료구조 ] 탐색 - 04 - 2 . 레드 블랙 트리 <삭제> [레드 블랙 트리의 노드 삭제] [삭제] 레드블랙트리의 삭제연산은 기본적으로 이진 탐색 트리의 삭제연산과 같다 . 다만 , 삭제후 레드 블랙 트리의 무너진 규칙을 수습하는 과정이 더해질 뿐이다 . [ 무너진 규칙의 복구 ] 무너진 규칙의 복구를 위해 레드 블랙 트리의 규칙을 다시 떠올리자면 모든 노드는 검정색 아니면 빨간색이다 . 루트 노드는 검은색이다 . 잎 노드는 검은색이다 . 빨간 노드의 자식들은 모두 검은색이다 . 하지만 검은 노드의 자식이 빨간색일 필요는 없다 . 루트 노드부터 모든 잎 노드 사이에 있는 검은색 노드의 수는 모두 동일하다 . 노드를 하나 삭제했을때 다음의 경우로 나뉜다 . 01 . 삭제한 노드가 빨간색일때 =>아무것도 처리할 필요가 없다 . 위의 규칙에 위반사항이 없다 02 . .. 이전 1 2 3 4 5 다음
