data structure (4) 썸네일형 리스트형 [DS] Hashing 1. hash table hash table은 hashing을 통해서 데이터를 저장하는 데이터 구조이다. hashing은 내부적으로 hash function 을 사용하여서 key와 value를 mapping 하여 hash table에 저장하여 데이터 구조를 형성하는 것을 의미한다. hash table에 데이터의 key와 value가 mapping 되어 저장되기 때문에 탐색에서 average case에 대해서 시간 복잡도가 O(1)이 된다. collision이 발생하는 경우에는 O(1)의 시간 복잡도를 보장할 수 없다. 그렇기 때문에 hash table에서의 성능은 hash function과 collision 발생 시의 정책에 따라 달라진다. 다음 예제는 hash table의 크기가 6이고 hash fun.. [DS] Graph MST & Shortest path - 이전 글: [DS] Graph 개념과 탐색방법 3. MST (Minimum Spanning Tree) 최소 신장 트리 (MST)는 그래프의 최소 연결 트리를 의미한다. 최소 연결 트리란 edge의 weight가 최소인 spanning tree를 말한다. spanning tree는 그래프의 모든 정점을 cycle 없이 연결한 형태를 말한다. 최소 신장 트리는 N개의 정점과 N-1개의 간선으로 연결되어 있으며 가중치의 합이 신장 트리 중에 최소인 값이 되어야 하기 때문에 단순히 가장 적은 간선을 사용한다고 해서 최소 비용을 얻을 수 없다. MST를 찾는 대표적인 방법으로는 Kruskal 알고리즘과 Prim 알고리즘이 있다. 1) Kruskal algorithm greedy 한 방법으로 간선을 선택하여서 .. [DS] Graph 개념과 탐색방법 1. Graph 그래프는 비선형 자료구조로 정점(vertex, 또는 노드 node)과 정점들을 있는 간선(edge)으로 이루어져 있다. 간선은 E(u,v)로 표현할 수 있는데, 이는 vertex u 와 vertex v를 연결하는 간선이라는 뜻이다. undirected graph 에서는 (u,v)와 (v,u)가 같은 의미를 가지지만 directed graph 에서는 (u,v)와 (v,u) 이 서로 방향이 다르기 때문에 다른 간선을 의미한다. 간선은 weight, value, cost 등의 가중치를 주어서 실제 문제에 적용하기도 한다. 1) 용어 Undirected Graph: 정점과 간선의 연결관계에서 간선의 방향성이 존재하지 않는 그래프 Directed Graph: 정점과 간선의 연결관계에서 간선의 방향.. [DS] Heap 1. Heap 힙은 Tree 구조를 기반으로 한 자료구조의 일종으로 배열로 구현한 Complete Binary Tree (완전이진트리) 구조로 이루어져 있다. 힙은 root 노드에 위치하는 값의 성질에 따라 max heap과 min heap 두가지로 나뉜다. 1) max heap: 각 노드의 값이 해당 child 노드들의 값보다 큰 값을 가지는 완전 이진 트리. 루트노드가 트리에서 가장 큰 값을 가진다. 2) min heap: 각 노드의 값이 해당 child 노드들의 값보다 작은 값을 가지는 완전 이진 트리. 루트노드가 트리에서 가장 작은 값을 가진다. 2. 배열을 통한 구현 heap을 배열로 구현하게 되면 root 노드의 인덱스가 0이 되고, 뒤이어서 나머지 노드들의 값이 저장된다. 이때 heap은 완.. 이전 1 다음
