늘 겸손하게

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

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

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

[ 1. Stack ] 선형 자료 구조이며 후입선출(Last-In-First-Out: LIFO)을 따른다. 가장 나중에 저장된 데이터가 가장 먼저 나온다. = 후입 선출 큐 와는 다르게 데이터 저장, 제거가 한 부분에서 이루어진다. (큐는 front, rear) 스택의 가장 위 요소를 가리키는 top pointer 한 개를 가진다. 스택의 top이라는 부분 한 곳에서만 데이터가 삽입되고 제거되는 컨테이너라고 볼 수 있다. 활용 웹 브라우저 뒤로가기 문서작업에서 Ctrl + Z 역순 문자열 만들기 후위 표기법 계산 재귀적 알고리즘 [ 2. Queue ] 선형 자료 구조이며 데이터를 한쪽에서만 삽입하고 한쪽에서만 제거할 수 있는 자료구조 먼저 들어간 데이터가 먼저 제거되는 선입선출(First-In-First..