HASH

Dictionary (딕셔너리) 딕셔너리는 사실 C++보다는 파이썬에서 더 익숙할 것이라 생각된다. 실제로 딕셔너리라고 아예 명확하게 말을 하기도 하니까... 자료구조에서 딕셔너리는 key와 value를 함께 저장하는 entry 저장 자료구조이다. 대신 key의 중복을 허용한다. 시간 복잡도 딕셔너리의 시간복잡도는 딕셔너리를 리스트 구현을 기준으로 얘기를 해보겠다. 딕셔너리의 ADT는 우선적으로 put, find, erase정도각 대표적이다. put 함수는 리스트에서 바로 맨 뒤나 맨 앞에 저장하는 방식을 활용한다. 당연히 이 함수는 \(O(1)\)의 시간복잡도를 갖는다. 보통 doubly-linked list나 배열로 구현을 한다. find와 erase는 doubly linked list를 기준으로 우..