코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 열린 주소 지정(Open Addressing) 하나의 테이블에 하나의 원소만을 저장한다. 중복이 발생할 경우 다른 비어 있는 위치를 탐색한다. 이차함수 탐색(Quadratic Probing) 충돌이 발생할 경우 선형 탐색을 진행한다. 1^2, 2^2, 3^2, 4^2, ... 순으로 다음 셀로 이동하여 비어 있는 셀인지 확인한다. 이차함수 탐색을 사용한 해시 테이블의 성능 선형 탐색에 비해 군집화(Clustering)가 발생활 확률은 상대적으로 줄어든다. 체이닝을 통한 해결에서 삽입 시간이 O(1)인데 비해 충돌한 해시 값의 수만큼 선형 시간이 소요된다. #include #include #include using namespace std; usin..

Level 1. 같은 숫자는 싫어 unique() 함수는 양옆의 원소를 비교하여 중복 원소들을 끝으로 몰아 놓는다. #include #include #include using namespace std; vector solution(vector arr) { arr.erase(unique(arr.begin(), arr.end()), arr.end()); return arr; } 스택을 이용해 최초 원소를 삽입하고 중복 원소는 삽입하지 않으며 새로운 원소가 나오면 pop() 후 push()한다. 문제 유형에 라고 나와있어서 스택을 사용해봤는데 사실 사용하지 않아도 된다. #include #include #include using namespace std; vector solution(vector arr) { ..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 열린 주소 지정(Open Addressing) 하나의 테이블에 하나의 원소만을 저장한다. 중복이 발생할 경우 다른 비어 있는 위치를 탐색한다. 선형 탐색(Linear Probing) 충돌이 발생할 경우 선형 탐색을 진행한다. 한 칸씩 다음 셀로 이동하여 비어 있는 셀인지 확인한다. 선형 탐색을 사용한 해시 테이블의 성능 특정 해시 값이 너무 자주 발생하면 원소가 몇 개의 그룹 형태로 뭉치는 군집화(Clustering)가 발생할 수 있다. 해시 충돌이 자주 발생할수록 검색 속도가 급격하게 느려진다. #include #include using namespace std; using uint = unsigned int; class hash_map { //..

Level 1. 문자열 내 p와 y의 개수 count_if() 함수를 활용하면 쉽게 해결할 수 있다. #include #include #include using namespace std; bool solution(string s) { return count_if(s.begin(), s.end(), [](const char c) { return tolower(c) == 'p'; }) == count_if(s.begin(), s.end(), [](const char c) { return tolower(c) == 'y'; }); } 직접 구현하면 2번을 따로 순회할 필요 없이 1번만 순회해도 된다. #include #include using namespace std; bool solution(string s)..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 체이닝(Chaining) 해시 테이블의 특정 키에 값을 저장하는 것이 아니라 값의 리스트를 저장한다. 충돌이 발생할 경우 리스트의 마지막에 원소를 추가한다. 체이닝을 사용한 해시 테이블의 성능 삽입은 O(1) 복잡도를 갖는다. 원소 개수에 비해 테이블의 크기가 작으면 리스트가 평균적으로 길어지므로 검색 속도가 저하된다. 원소 개수에 비해 테이블이 너무 크면 공간이 낭비된다. 체이닝으로 충돌을 해결한 해시 맵 #include #include #include #include using namespace std; using uint = unsigned int; class hash_map { // 값의 리스트를 벡터로 관리한다. vector data; p..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 해시 테이블은 해싱을 통해 빠르게 값을 검색할 수 있지만 해시 값이 겹치는 경우에 주의해야 한다. 부하율(Load factor) 전체 원소 개수 / 해시 테이블의 크기 부하율이 1이면 원소 개수가 테이블의 크기와 같다는 뜻이고 가장 이상적인 상태이다. 모든 연산이 O(1)에 가깝게 작동하고 공간 이용도 효율적이다. 부하율이 1보다 낮아질수록 원소가 하나도 저장되지 않은 리스트가 많다는 뜻이고 공간이 낭비된다. 부하율이 1보다 커질수록 리스트의 크기가 1보다 크다는 것이고 검색 성능이 저하된다. 해시 테이블의 성능을 결정짓는 요소 부하율이 유일한 지표는 아니다. 몇몇 해시 테이블은 부하율이 1에서 너무 멀어지면 해시 함수를 변경하여 1에 가깝게 만드..