늘 겸손하게

Hashing 키(Key)값을 해시 함수(Hash Function)에 대입하여 나온 결과를 주소로 사용하여 값(value)에 접근하는 방법 Hash Function 키(Key)값을 값(Value)이 저장된 주소로 바꾸어주는 함수. 키(Key)값을 값(Value)이 저장된 주소로 바꾸는 일을 매핑(Mapping)이라고 한다. 장점 데이터의 탐색을 O(1)만에 가능하다. 데이터의 빠른 저장과 탐색이 필요할때 유용한 방법 해싱은 주로 '사전(dictionary)' 자료 구조를 구현할 때 사용 단점 단점으로는 메모리에 데이터가 순차적으로 저장되지 않아 메모리상에 빈 공간이 많이 생기는 메모리 낭비가 발생한다. 해시 함수는 중복이 발생 가능하다. 다른 키값을 입력했는데 같은 해시 값이 도출될 수 있다. 그래서 연..

[ 이진 탐색 트리 ] 이진 탐색 + 연결 리스트 이진 탐색: 탐색에 소요되는 시간복잡도 O(log N). 하지만 새로운 데이터 삽입, 삭제 불가능 연결 리스트 : 삽입, 삭제의 시간복잡도는 O(1), 하지만 데이터 탐색 시간복잡도 O(N) 이진 탐색의 빠른 탐색 + 연결 리스트의 빠른 데이터 삽입, 삭제 를 합친것이 '이진탐색트리'

[ Tree ] 노드(Node)와 간선(Edge)로 이루어진 자료구조 최상위 노드를 루트(root) 노드라고 부른다. 노드는 여러 개의 자식 노드를 가질 수 있다. 자식 노드를 최대 2개까지 가지는 노드를 '이진 트리' (binary tree) 라고 부른다. [ 트리 순회 방식 ] 1. 전위 순회 (pre-order) 루트 -> 왼쪽 자식 -> 오른쪽 자식 순으로 방문 10 -> 20 -> 40 -> 50 -> 30 public static void dfs(int cur) { // cur := 현재 탐색 중인 정점의 번호 if(cur > n) return; System.out.println(arr[cur]); dfs(cur*2); dfs(cur*2 + 1); } 2. 중위 순회 (In-order) 왼쪽 ..

Heap(힙)은 최댓값 및 최솟값을 빠르게 찾아내기 위한 자료구조로 우선순위 큐(Priority Queue)를 구현하는데 사용됩니다. Heap은 완전 이진 트리로 최대 두 개의 자식 노드를 가질 수 있습니다. [ 완전 이진 트리 ] 완전 이진 트리는 이진 트리의 한 종류로 단말 노드(leaf node)를 제외한 모든 노드는 2개의 자식을 가지거나 왼쪽 자식만을 가져야만 합니다. 예로 값 40, 50, 30을 가지는 단말 노드 (leaf node)를 제외한 모든 노드는 2개의 자식 노드를 가지고 있으므로 위 트리는 완전 이진 트리 입니다. 반면에 위와 같은 트리에서 값 30을 가지는 노드는 오른쪽 자식 노드 밖에 없으므로 위 트리는 완전 이진 트리가 아닙니다. 힙에는 두 가지 종류가 있습니다. 1. Min..