개발일지

문제설명 입출력 예제 개념 다양한 수를 처리하는 문제다. 산술 평균, 중앙값, 범위는 간단하게 해결할 수 있지만, 최빈값을 처리하는 과정이 까다롭고, 시간 초과에 자주 걸리므로 알고리즘 최적화를 잘해야 한다. 풀이 #include #include #include #include #include using namespace std; int main() { int N, sum = 0; cin >> N; vector v(N); unordered_map freq; 수의 개수 N, 산술 평균을 계산하기 위한 sum, 중앙값과 범위를 계산하기 위한 벡터 v, 최빈값을 계산하기 위한 해시맵 freq를 초기화한다. for (int i = 0; i > v[i]; sum += v[i]; fr..

"; Insert(oldkey, count + 1, 2); } } else { int value = hash2(key); if (_table2[value] == -1) { std::cout

충돌 해결체이닝(Chaining)　해시 충돌 문제를 해결하는 첫 번째 방법인 체이닝 기법에서는 충돌이 발생한 지점에서 연결 리스트를 만든다. 즉, 이 방법은 해시 테이블의 특정 위치에서 하나의 연결 리스트를 저장하여, 충돌이 발생하면 리스트의 맨 뒤에 새로운 키를 추가하는 방식이다.  　연결 리스트는 포인터를 이용하여 다음 노드를 가리키기 때문에, 메모리를 재사용하지 않아 중간에 요소를 삽입하거나 삭제하는 경우에도 O(1) 시간에 수행할 수 있다는 장점이 있다. 그리고 배열과 다르게 데이터가 흩어져 있지 않고 연속된 메모리 공간을 차지하지 않으므로, 캐시 효율성이 높다. 　이러한 체이닝 기법을 이용하여 이전 충돌 문제를 해결해 보자. #include #include #include #include cla..

해시 테이블(Hash Table)개요　해시 테이블은 키(key)와 값(value)을 이용해 데이터를 저장하는 자료구조로서, 키를 주어진 데이터로부터 고유한 숫자 값을 계산하는 해시 함수(hash function)를 이용해 해시 값으로 변환한 후, 해당 해시 값에 해당하는 위치에 값을 저장한다. 여기서 해시 값(hash value)이란 해시 함수에 의해 반환되는 숫자를 의미한다. 　키와 값을 이용한 자료구조라는 점에서 std::map 자료구조와 비슷하다고 생각할 수 있다. 실제로 두 컨테이너는 유사하지만, 내부 구조와 동작 방식, 그리고 성능 특성 등에서 차이가 있다.   hash tablemap탐색이진 탐색해싱정렬XO속도O(1)O(logN)해싱과 충돌　해시 테이블의 핵심은 해싱이다. 해싱(hashing)..