잡동사니

안녕하세요. yeTi입니다. 오늘은 알고리즘 공부 중 해싱(hashing)에 대해 학습한 내용을 공유하려고 합니다. 강의 : 권오흠 교수님의 2015 봄학기 알고리즘 개요 해쉬 테이블(hash table)은 트리(tree)와 같이 dynamic set을 구현하는 효과적인 방법 중 하나입니다. 적절한 가정하에 Insert, Delete, Search 연산의 시간복잡도는 O(1)을 가지지만 최악의 경우에는 O(n)을 가집니다. Hash Table 해시 테이블은 일반적으로 일차원 배열을 활용하여 데이터를 관리합니다. 이 때, 배열의 인덱스가 특정 데이터의 키를 해시한 값을 활용하여 키를 해시하는 연산 시간만 주어지면 데이터에 바로 접근할 수 있는 특징을 가지고 있습니다. 하지만, 데이터의 크기가 해시 테이블의..

안녕하세요. yeTi입니다. 오늘은 알고리즘 공부 중 트리(tree)에 대해 학습한 내용을 공유하려고 합니다. 강의 : 권오흠 교수님의 2015 봄학기 알고리즘 트리 (Tree) 트리는 계층 구조를 표현하는 자료구조입니다. 트리에서 사용하는 용어는 다음과 같습니다. 노드 (node) 링크 (link) 루트 (root) 부모 (parent) 자식 (child) 형제 (sibling) 리프 (leaf) 조상 (ancestor) 자손 (descendant) 부트리 (subtree) 레벨 (level) 높이 (height) 이진트리 (Binary Tree) 이진트리는 자식 노드가 최대 2개인 트리를 말합니다. 이진트리의 종류에는 full binary tree 와 complete binary tree가 있습니다...