bdfgdfg

해시 테이블 탐색에 있어 매우 빠른 결과를 보여주는 자료구조이다. -> 탐색의 시간 복잡도는 O(1). 즉 내가 찾고자 하는 대상을 한번에 찾아내는 방식. C++에서도 STL 컨테이너에서 제공하는 해시테이블이 존재한다. -> std::unordered_map(Key-Value), std::unordered_set(Key) 참고로 앞서 배운 이진 탐색 트리의 컨테이너는 std::map(Key-Value) 테이블(Table) 위 그림이 테이블. 자료구조 관점에서 위 그림 처럼 저장되는 데이터가 키(key)와 값(value)이 하나의 쌍을 이뤄야 테이블이라 한다. 그렇기에 테이블에 저장되는 모든 데이터들은 이를 구분하는 '키'가 있어야 데이터를 구분하는 기준이 된다. 그렇기에 테이블은 키와 관련해 다음과 같은..

이진 탐색 트리의 문제점과 AVL트리 이진 탐색 트리의 탐색 연산은 O(logN)의 시간 복잡도를 가진다. 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하므로. 그런데 이전 장의 이진 탐색 트리는 문제점이 있는데 예로들어 10,20,30,40,50의 Key가 저장된 이진 탐색 트리를 보자. 이렇듯 노드가 한 쪽으로 쏠리게 된다. 만약 1부터 100까지의 Key값이 들어있는 노드들을 이진 탐색 트리에 넣을 시 내가 100이라는 값을 찾기 위해선 100번의 연산. 즉 O(N) 시간 복잡도를 가진다. 그렇다면 저장 순서를 바꾸면 어떨까? 똑같이 1 ~ 5까지의 Key값이 들어간 노드들이지만 위와 비교해서 제법 균형이 잡혀있고 트리의 높이도 줄어들었다. 이렇듯 앞서 구현한 이진 탐색..

본문은 오름차순을 기준으로 정렬을 설명합니다. 힙 정렬 힙 정렬은 앞서 구현한 자료구조인 '힙(heap)' 자료구조를 이용한 정렬 알고리즘이다. 정렬은 특성은 힙의 다음 특성을 활용하여 정렬하는 알고리즘이다. "힙의 루트 노드에 저장된 값이 가장 커야 한다." - 최대 힙의 특징. 즉 이 특성을 이용해 힙의 루트 노드에 저장된 값이 정렬순서상 가장 앞선다. 앞서 힙을 제대로 공부했다면 바로 이해가 가능하니 코드를 통해 확인해본다. template void Sort::HeapSort(T* ptr, int len) { Heap hp(Sort::PriComp); int i; for (i = 0; i < len; ++i) hp.Insert(ptr[i]); for (i = 0; i < len; ++i) ptr[i..

자료구조란? "어떻게 데이터를 표현하느냐"이다. 위에서 말하는 데이터의 표현은 데이터의 저장을 포함하는 개념이다. 이렇듯 '데이터의 저장'을 담당하는 것이 바로 자료구조. 그렇기에 우리가 언어를 공부하면서 배운 기본 자료형 int형, 구조체 혹은 배열등도 자료구조에 속한다. 하지만 흔히 자료구조라함은 이렇게 간단한 구조를 지칭하는것이 아닌 좀 더 복잡한 형태의 자료구조를 이야기한다. 자료구조의 분류 주로 공부할 내용은 선형구조(리스트,스택,큐등)와 비선형구조(트리,그래프). 자료구조와 알고리즘 자료구조가 '데이터의 표현 및 저장방법'을 뜻한다면 알고리즘은 그 자료구조의 데이터를 대상으로 하는 문제 해결방법을 뜻한다. 예를 들어보자. int arr[10] = {1,2,3,4,5,6,7,8,9,10}; 위의..