알고리즘
-
알고리즘...98일지 2022. 1. 5. 15:48
해시 테이블 이차원 조사 구현 기존 구현에 추가로 충돌 해결용 함수만 구현한다. 이번에는 i를 순서대로 더하는 대신 i의 제곱값을 더하는 방식으로 빠르게 군집을 벗어나도록 만든다. int HashTable_OpenAddressing_QuadraticProbing::GetProperHashIndex(int idx, int data) { int properIdx{ idx }; int i{ 1 }; while (m_table[properIdx] != Empty && m_table[properIdx] != data) { properIdx = (idx + (i * i)) % Size(); i++; } return properIdx; } main.cpp #include "Common.h" #include "해시테이..
-
알고리즘...97일지 2022. 1. 4. 14:55
선형 조사 알고리즘 구현 먼저, 개방 주소 방법에서는 개수가 무한히 증가될 수 없으므로 일정 수준보다 값이 많이 들어가면 개수를 늘리는 처리를 추가한다. int LimitCount() { return Size() * 3 / 4; } bool HashTable_OpenAddressing::NeedToResize() { return m_usedCount >= LimitCount(); } 이후 테이블의 Resize를 처리하는 함수를 추가한다. void HashTable_OpenAddressing::Resize() { vector oldData; oldData.reserve(Size()); for (int i = 0; i < Size(); i++) { if (m_table[i] != Empty && m_tabl..
-
알고리즘...96일지 2021. 12. 30. 18:42
해시 테이블 충돌 처리 구현 진행 개방주소 방법 구현을 위한 베이스 클래스 제작 HashTable_OpenAddressing.h #pragma once #include "../Common.h" #include "HashTable.h" #include #include using std::vector; using std::list; /// /// 충돌 해결 방법 중 체이닝을 구현한 해시 테이블 /// class HashTable_OpenAddressing : public HashTable { public: HashTable_OpenAddressing(HashFunction hashFunction = HashFunction::Division) : HashTable(hashFunction) {} virtual ..
-
알고리즘...95일지 2021. 12. 29. 17:35
해시 테이블, 체이닝 처리 구현 HashTable_Chaining.h #pragma once #include "../Common.h" #include "HashTable.h" #include #include using std::vector; using std::list; /// /// 충돌 해결 방법 중 체이닝을 구현한 해시 테이블 /// class HashTable_Chaining : public HashTable { public: HashTable_Chaining(HashFunction hashFunction = HashFunction::Division); virtual void Add(int data) override; virtual void Remove(int data) override; virt..
-
해시 테이블 알고리즘프로그래밍 기초/알고리즘 2021. 12. 22. 14:42
해시 테이블 해시 테이블은 원소의 위치가 값에 의해 계산되어 결정되는 자료구조로 해시 테이블의 값을 정하는 건 해시 함수인데, 이 함수를 통해 각각의 원소의 자리를 상수 시간에 계산할 수 있다. 해시 테이블에 원소가 차 있는 비율을 적재율이라 하며, 테이블의 크기가 m이고 테이블에 저장된 원소의 개수가 n이면 적재율은 n/m이 된다. ※ 테이블의 모든 영역에 값을 적절하게 분배하지 못하는 경우 성능이 떨어질 수 있다. 해시 함수 해시 함수는 해시 테이블에서 키 값을 테이블의 인덱스로 만들어 주는 함수로 다음의 성질을 가진다. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다. 계산이 간단해야 한다. 만약 데이터가 어느 한 인덱스에 몰려서 저장되게 된다면 충돌이 자주 발생하여 성능에 악영향을 미치기 때..
-
알고리즘...94일지 2021. 12. 20. 15:11
해시 테이블 충돌 해결 원소를 저장하려고 할 때 이미 다른 원소가 저장되어 있는 경우 충돌이 발생하게 된다. 이를 해결하는 방법으로 다음과 같은 방법들을 사용한다. 체이닝 같은 주소로 해싱되는 원소를 연결 리스트로 관리, 적재율이 1을 넘을 수 있음 검색, 추가, 삭제 시 해싱 후 연결 리스트를 통한 연산이 추가된다. 개방 주소 방법 어떻게든 주어진 해시 테이블 내에서 충돌을 관리, 적재율이 1을 넘을 수 없음 선형 조사 충돌이 일어난 바로 직후를 확인하여 처리를 진행하는 방식 특정 영역에 원소가 몰리는 경우 성능이 떨어진다. 이차원 조사 충돌 직후의 위치를 보는 대신 이차 함수에 따라 검색 폭을 넓히면서 확인하는 방식 여러 원소가 동일한 초기 해시 함숫값을 가지면 동일한 폭으로 검색하게 되므로 성능이 ..
-
알고리즘...93일지 2021. 12. 15. 08:20
해시 함수 해시 함수는 해시 테이블에서 키 값을 테이블의 인덱스로 만들어 주는 함수로 다음의 성질을 가진다. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다. 계산이 간단해야 한다. 만약 데이터가 어느 한 인덱스에 몰려서 저장되게 된다면 충돌이 자주 발생하여 성능에 악영향을 미치기 때문에 입력된 데이터가 해시 테이블 전체에 골고루 나누어 저장되는 것이 상당히 중요하다. 해시 함수는 대표적으로 두 가지 방법이 존재한다. 나누기 방법 주어진 데이터를 해시 테이블의 크기로 나눈 나머지를 인덱스로 사용하는 방법 해시 테이블의 크기는 2의 멱수(2ⁿ)에 가깝지 않은 소수(prime number)를 택하는 것이 좋다. h(x) = x mod m 곱하기 방법 주어진 데이터를 0과 1 사이의 소수(decimal)..
-
알고리즘...92일지 2021. 12. 14. 13:56
해시 테이블 개요 해시 테이블은 원소의 위치가 값에 의해 계산되어 결정되는 자료구조이다. 해시 테이블의 값을 정하는 건 해시 함수인데, 이 함수를 통해 각각의 원소의 자리를 상수 시간에 계산할 수 있다. 단, 테이블의 모든 영역에 값을 적절하게 분배하도록 만들지 못하는 경우 인덱싱이 필요하게 되어 성능이 떨어질 수 있게 된다. 따라서 해시 함수의 성능이 중요하게 된다. 이때 해시 테이블에 원소가 차 있는 비율을 적재율이라 하며, 테이블의 크기가 m 이고 테이블에 저장된 원소의 개수가 n이면 적재율은 n/m이 된다. 더보기 참고문헌 한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘