Hash Table은 key로부터 매핑된(key-value 형식) 자료구조로 Hahsing이라는 기술을 사용합니다. Hash, Hashing해시는 O(1)을 지향합니다. 데이터 개수 N과 무관하게 단번에 값을 찾아내겠다는 것입니다.주어진 키를 사용해서 실제 레코드의 주소를 직접적으로 계산해내는 것을 해시라고 합니다.해시 함수에 주어진 레코드의 키에 해시 함수를 가하면 그 레코드가 저장되어야 할 인덱스가 나옵니다. 당연히 이 계산은 매우 빨라야 합니다. 키에 해시 함수를 가하여 채운 도표가 해시 테이블입니다. Hash function주어진 데이터를 실제 정수 값으로 변환하는 함수입니다. 여기서 나오는 정수값은 테이블의 인덱스로 사용할 수 있는 정수(해시 코드)입니다. key-value 값으로 연결될 때, ..

Dijkstra algorithm(다익스트라 알고르즘) 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘 일반적인 형태로는 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단 경로를 찾는다. 원래 알고리즘은 우선순위 큐를 사용하지 않았기 때문에 시간 복잡도 $$O(|V|^2)$$ 우선적으로 구현해볼 것은 일반적인 형태이지만, 음의 간선을 포함할 수 없다. 사진에서 보이는 표 같은 경우는 "노드 1"을 기준 삼아서 연결되어 있는 꼭짓점과 연결을 확인한다. 이 다음 "노드"를 기준삼아서 기존에 값과 비교를 한 뒤에 최소값으로 표기를 하게 되면 된다. 이러한 방법은 모든 꼭짓점을 기준으로 할 때까지 반복이기에 위에서 말한 시간 복잡도를 갖게 된다.

Graph 연결되어 있는 객체간의 관계를 표현한 자료구조 G(V, E) 그래프에서의 표현으로 V는 정점 혹은 노드라고 불리며, E 노드간의 연결을 해주는 간선으로 나타난다. 그래프의 종류를 나뉘는 것을 보면 간선의 방향치양방향 혹은 한쪽 방향으로만 이동이 가능 간선의 가중치간선마다 비용이나 가중치를 책정 방향 그래프 : G2, G4 와 같은 그래프로 모든 간선은 방향을 가지고 두 정점의 쌍으로 표현 무방향 그래프 : G1, G3 와 같은 그래프로 간선을 표현하는 두 정점의 쌍에 순서가 없다. 방향이 없는 그래프 인접 : 무방향 그래프 G1 에서 간선 (V0, V1)가 노드 V0와 V1은 서로 인접 부속 : 무방향 그래프 G1 에서 간선 (V0, V1)가 간선 (V0, V1)은 정점 V0와 V1의 부속이 ..

동작이 되지 않던 코드를 수정 insertElementBST : 수정 전의 형태를 하게 되면 p->pLeftChild, p->pRightChild 가 가르키는 곳이 무엇인지 정해지지 않은 상태에서 element 로 할당이 되었기 때문에, 이후 삽입과정에서 element 를 찾을 수 없어서 오류가 발생하게 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 if (pBinSearchTree->pRootNode == NULL) { pBinSearchTree->pRootNode = element; return TRUE; } while(TRUE) { if (p == NULL) { p = element; return TRUE; } if (p->key > elem..

BST 이진트리 중에서 탐색을 위해 고안된 것으로 노드 위치를 키 값 기준으로 결정된다. 이진 탐색트리의 효율 편향 이진트리, 모습에 따라 탐색 효율이 달라지기에 최악의 경우에는 N이기에 염두를 해야 한다. 이진 탐색트리의 조건 노드 N에 대하여 왼쪽 하위트리에 있는 노드는 N보다 작다. 노드 N에 대하여 오른쪽 하위트리에 있는 노드는 N보다 크다. 노드 N의 왼쪽 하위트리와 오른쪽 하위트리도 이진 탐색트리이다. 키값은 유일 구현해야 하는 사항 이진 탐색트리의 탐색 이진 탐색트리의 삽입 탐색을 전제로 삽입 트리의 루트로부터 시작해서 삽입할 키와 하위 트리의 키과 비교 (반복) 이진 탐색트리의 삭제 삭제할 노드가 리프노드 삭제할 노드가 자식노드 하나만 있는 경우 삭제할 노드가 자식노드 두 개 있는 경우 이..

Heap 우선순위 큐를 구현하기 위한 자료구조, 완전 이진 트리의 형태로 구성 최대값 및 최솟값을 찾아내는 연산을 빠르기 하기 위한 용도로 사용 큐는 여기 글에서 설명이 되어있고, 우선순위 큐는 먼저 들어온 데이터가 아닌 우선순위가 높은 데이터가 먼저 나가는 형태 특징 완전이진트리의 형태 부모노드와 자식노드 간에만 대소 관계가 성립(형제 사이에는 정해지지 않는다) 중복된 값 허용 복잡도 Max Heap (최대 힙) 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙 루트노드의 값은 최대값 Min Heap (최소 힙) 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙 루트노드의 값은 최솟값 연산 createHeap() : 히프 생성 deleteHeap() : 히프 삭제 insert() : 자료 추가 트리의..

계층적인 관계를 나타내는 데 편리한 것이 트리로써, 트리의 구성 요소에 해당 하는 것을 노드라 칭한다 트리의 개념 Root Node : 부모가 없는 노드 (원조격인 노드) leaf or Terminal Node (단일 노드) : 자식이 없는 노드 Internal Node : 리프 노드를 제외한 모든 노드 부모 노드 : B, G 노드의 부모 노드는 F이다. 자식 노드 : F 노드의 자식 노드는 B, G이다. 선조 노드 : 주어진 노드의 상위에 있는 노드들, B, F는 D의 선조 노드이다. 후손 노드 : 역으로 어떤 노드의 하위에 있는 노드들, F의 후손은 그 아래 모든 노드들이다. 형제 노드 : 같은 부모를 두고 있는 노드들, B, G 노드는 형제 노드이다. 트리의 차수 : 자식 노드의 개수 트리의 레벨 ..

FIFO(First-In First-Out), 선입선출의 특성 구현해야 하는 필수 요소 인큐 연산 데이터 삽입하는 연산 ⚠️ 큐의 크기를 초과해 새로운 자료를 추가하지 못하는 현상을 오버플로 디큐 연산 데이터 삭제하는 연산 ⚠️ 아무 자료가 없는 빈 큐에 연산을 하게 되면 언더플로 현상 발생 피크 연산 프론트에 있는 데이터 제거 🚫 기다리는 줄, 공유된 프린터 하나에서 일쇄될 차례를 기다리는 것 등에 사용 #include #include #include # define TRUE 1 # define FALSE 0 typedef struct DequeNodeType { int data; struct DequeNodeType *pLLink; struct DequeNodeType *pRLink; } DequeN..