Crat

5-4. 해시 테이블(Hash Table)

0. map vs hash_map (std::unordered_map) (1) map ( C#의 dictionary와는 다름 ) - 균형 이진 트리의 트리 구조, 레드-블랙 트리로 구성되어 있음 - 키를 기준으로 자동으로 정렬해서 저장 - 시간 복잡도 : O( log N ) (2) hash_map (std::unordered_map, C#의 dictionary) - 메모리를 대가로 속도를 이점으로 가져감 - 삽입 순서에 따라서 저장 - 해시 충돌이 없으면 속도가 map에 비해 굉장히 빠름 - 시간 복잡도 : 데이터의 추가, 탐색, 삭제가 상수의 시간 복잡도를 가짐 => O(1) 1. 해시 테이블 ; unordered_map 키-값 쌍으로 이루어져 있으므로 특정 값에 접근하려면 키만 알면 됨. 그러나 키-..

5-3. 퀵 정렬(Quick Sort)

1. 퀵 정렬(Quick Sort)의 원리 (1) 인덱스 지정 - 배열의 첫 값을 pivot(피벗)으로 지정 - 그 다음 값을 시작위치인 low로 지정 - 배열의 마지막 값을 high로 지정 (2) 인덱스 이동 - pivot >= arr[low] 일 때까지 low 인덱스를 1씩 증가시킴 - pivot low보다 커질 때 알고리즘을 종료 - arr[pivot] 과 arr[high] 교체 위의 알고리즘을 통해 피벗을 기준으로 좌측은 피벗 값보다 작게, 피벗을 기준으로 우측은 피벗 값보다 크게 정렬된다. 2. 퀵 정렬 구현 int Partition(vector& v, int left, int right) { int pivot = v[left]; int low = left + 1; int high = right..

5-2. 힙 정렬, 병합 정렬

1. 힙 정렬(Heap Sort) 힙의 특성을 이용한 정렬. void HeapSort(vector& v) { priority_queue pq; // 우선순위 큐를 내림차순으로 정렬 for (int num : v) // 벡터 v의 모든 값을 우선순위 큐에 대입 pq.push(num); v.clear();// 벡터 v를 비움 while (pq.empty() == false) // 우선순위 큐가 빌 때 까지 { v.push_back(pq.top()); // 벡터 v에 우선순위 큐의 값을 작은 순서대로 집어넣음 pq.pop();// 우선순위 큐의 맨 위 데이터 제거 } } 우선순위 큐는 힙 구조로 되어있다. 우선순위 큐를 내림차순으로 정렬되어 있기 때문에 가장 작은 값이 우선순위 큐의 Top에 위치한다. 우선순..

5-1. 버블 정렬, 선택 정렬, 삽입 정렬

상대적으로 비효율적으로 동작하는 기본 정렬들이다. 1. 버블 정렬(Bubble Sort) 바로 옆의 원소와 비교하며 큰 수를 마지막에 오게 한다. 루프 한 번마다 큰 수를 하나씩 정렬한다. void BubbleSort(vector& v) { for (int i = 0; i v[j + 1]) { temp = v[j]; v[j] = v[j + 1]; v[j + 1] = temp; } } } } 인덱스는 0부터 시작하기 때문에, 인덱스 4번까지 정렬을 하겠다면 벡터의 사이즈보다 1 작은 만큼 정렬해야 한다. 또..