SET 집합을 표현한 자료구조로 Key를 저장하는데 Key에 대해서 중복을 허용하지 않는다 정렬되어 있다 를 만족하는 형태를 유지한다. STL set 컨테이너는 균형 이진트리로 구현되어 있지만 여기선 단순한 배열의 형태로 구현했다. MakeSet function 배열을 입력받아서 정렬을 한뒤 array의 원소를 set에 마지막으로 삽입된 원소와 비교하면서 중복이 아닐 때만 삽입한다. 정렬된 순서로 삽입되기 때문에 set의 마지막 원소만 비교해도 된다. 시간 복잡도는 정렬 시 O(nlogn) , 삽입 시 O(n) 이므로 O(nlogn) vector MakeSet(vector array) { vector set; if (array.empty()) return set; sort(array.begin(), ar..
Chaining Hash Table 구현하기
Hash Table Hash Table 이란 Key에 Value를 저장하는 자료구조 Hash Function으로 Key를 index 값으로 바꾸어 사용 Key 값으로 바로 Value에 접근이 가능하므로 탐색 시간이 O(1)으로 매우 빠름 Value가 저장되는 장소를 Bucket이라 함 Chaining 이란? Hash Function의 값이 중복이 될 때 충돌이 발생하는데, 이를 해결하기 위해 Linked List를 활용하는 방식을 Chaining 기법이라 한다. Hash Function string 타입의 key를 입력받아서 hash table의 index를 반환해준다. int hash(string key) { int hash = HASH_VALUE; auto key_it = key.begin(); wh..