DataStructures
-
[자료구조] 힙(heap) #javaDataStructures 2021. 11. 17. 17:51
힙(heap) 자료구조 안녕하세요? 장장스입니다. 오늘은 힙자료구조에 대해 알아보겠습니다. 힙 (heap) 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기반으로 한 자료구조입니다. 힙에는 최대 힙(max heap)과 최소 힙(min heap)이 있습니다. 부모 노드가 자식 노드보다 크면 최대 힙, 반대이면 최소 힙입니다. 가장 큰 숫자가 뿌리에 있게 하려면 최대 힙, 가장 작은 숫자로부터 시작하려면 최소 힙을 사용하면 됩니다. 최대 힙 (max heap) max heap은 root에 가장 큰 값이 오는 heap 입니다. 최소 힙 (min heap) min heap은 root에 가장 작은 값이 오는 heap 입니다. 힙 추가 그렇다면 새로운 데이터를 추가하거나 제거는 어..
-
[자료구조] 트리(Tree)DataStructures 2021. 11. 16. 16:12
트리(Tree) 안녕하세요? 장장스입니다. 오늘은 Tree 자료구조에 대해 알아보겠습니다. 트리 (Tree) 가계도처럼 노드를 나무 형태로 연결한 구조를 트리라고 합니다. 트리에 있는 각각의 요소는 노드입니다. 위 사진에서처럼 노드는 부모, 자식 형태로 이어집니다. 뿌리 (root): 트리의 시작 부분입니다. 뿌리를 통해 들어가서 트리를 탐색합니다. 잎 (leaf): 자식이 딸려있지 않은 부분입니다. 노드라고 부르기도 합니다. 간선 (edge): 두 노드를 연결하는 선입니다. 뿌리로부터의 간선의 수에 따라 level을 나눕니다. 트리의 높이, 깊이, 레벨 트리 자료구조에 대해 이야기하다 보면 높이, 깊이, 레벨에 대해 언급이 됩니다. 차이점에 대해 알아봅시다 높이(height): 루트에서 가장 먼 잎(노..
-
[자료구조] 해시 구현하기 #javaDataStructures 2021. 10. 5. 16:46
해시 자료구조 자바로 구현하기 해시 자료구조 설명 해시 자료구조 JAVA 구현 Hash.java public class Hash implements HashInterface{ class HashElement implements Comparable{ K key; V value; public HashElement(K key, V value){ this.key = key; this.value = value; } @Override public int compareTo(HashElement o) { return (((Comparable)this.key).compareTo(o.key)); } } int numElements; int tableSize; //array size double maxLoadFactor; ..
-
[자료구조] 해시(hash) #javaDataStructures 2021. 10. 1. 22:37
해시(Hash) 해시 자료구조 설명 해시 자료구조 JAVA 구현 해시 (hash) linkedList 에서 원하는 요소를 찾기 위해선 처음부터 끝까지 모든 요소를 탐색해야 합니다. n개의 요소가 있다면 O(n)의 시간복잡도가 걸리게 됩니다. 이것은 매우 비효율적입니다. 여러 상황에서 빠르게 데이터를 추가하거나 제거하도록 하고 싶었습니다. 그리고 무언가 찾아야 할때 빠르게 찾을 수 있어야 했습니다. 해시는 이러한 단점을 해결 할 수 있습니다. Hash는 Key, 그리고 연관된 Value를 가지고 있습니다. 모든 요 소를 살펴본 후 동일한 노드를 찾는 LinkedList와 달리 Hash는 Key가 주어지면 빠르게 Value를 찾을 수 있습니다. Hash는 Key와 Value를 저장하기 위해 연상배열(Asso..
-
[Big Oh Notation] 빅 오 표기법이란?DataStructures 2021. 8. 9. 21:35
빅 오 표기법이란? 알고리즘을 공부하면서 접하게되는 단어가 있습니다 바로 '빅 오(Big Oh)' 입니다. 빅 오 표기법은 알고리즘의 복잡도를 단순화할 때 사용하는 점근 표기법의 하나입니다. Big Oh? 빅 오 표기법은 알고리즘의 효율성을 표시하는 표기법입니다. 빅 오 표기법을 사용하면 어떤 알고리즘을 다른 알고리즘과 비교해서 표현하는 것이 가능합니다. 점근 표기법 O (빅 오 복잡도) : 비교 대상인 그래프가 일치 혹은 아래에 있을 때. 비교 대상인 다른 알고리즘과 같거나 더 빠르다. o (리틀 오 복잡도) : 비교 대상인 그래프가 아래에 있을 때. 비교 대상인 다른 알고리즘보다 더 빠르다. θ (세타 복잡도) : 비교 대상인 그래프가 일치할 때. 비교 대상인 다른 알고리즘과 같다. ω (리틀 오메가..