Programming/Data Structure (3) 썸네일형 리스트형 Hash Table(해시 테이블) 해시 테이블(Hash Table) Key값에 Value를 저장하는 데이터 구조로 key값을 통해 데이터에 접근한다. 그렇기에 데이터 접근 시간 복잡도가 O(1)이 되어 탐색이 빠르다는 장점을 갖는다. 이때 해시 테이블의 문제가 발생할 수 있는데 충돌에 관한 문제이다. 만약 다수의 Value 중 Key값이 겹치는 Value들이 존재하면 충돌이 발생한다. 이를 해결할 수 있는 방법은 다양하다. 첫째로 Chaining 방식은 Linked List를 이용하는 방법으로 저장하려는 해시 테이블에 같은 키 값의 데이터가 존재할 경우, 노드를 추가해 다음 노드를 가리키는 방식으로 체인을 이어서 해시 테이블을 구성하는 방식이다. 둘째로 Open addressing 방식은 index에 대한 충돌 처리에 대해서 Linked.. Linked List(연결 리스트) 연결 리스트(Linked List) 연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당한다. 종류에는 단일, 이중, 원형 등의 연결 리스트가 있다. 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 있다. 보통 조회가 드물고 추가, 삽입, 삭제가 잦은곳에 사용한다. ::보통 삽입/삭제 시 시간복잡도가 O(1)이라고 하는데, 그 위치를 찾아가는데 O(n)만큼 걸리므로 실제로는 O(n):: *출저 : 위키백과 1) 선형 연결 리스트 12345678910111213141516171.. Heap(힙) & Priority Queue(우선순위 큐) 힙(Heap) 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다. ::A가 B의 부모노드(parent node)이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다:: 힙에는 두 가지 종류가 있으며 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 '최대 힙', 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 '최소 힙'이라고 부른다. 키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다. 각 노드의 자식노드의 최대개수는 힙의 종류에 따라 다르지만.. 이전 1 다음