솔

이번에는 c++ 표준 라이브러리인 std::map, std::unordered_map 에 대해 알아보겠습니다. 라이브러리의 이름이 map 이라고 지어진 이유는 mapping 과 관련이 있기 때문입니다.  std::map (Ordered Map)map 은 BST (이진탐색트리) , RedBlackTree(레드블랙트리) 로 구현되어 있어서키의 순서가 자동으로 정렬되고O(log N) 을 기대할 수 있습니다. 또, 트리의 형태를 유지하기 위해 추가적인 메모리를 사용하지만 Unordered_mapd 에 비하면 적고,중복된 값은 허용하지 않습니다. ( 덮어쓰기 ) std::unordered_map (Unordered Map)unordered_map 은 해시테이블로 구현되어 있어서키의 순서가 정렬되지 않고평균적으로 ..

문제가 굉장히 깁니다. 해시 함수) 해시 함수란, 임의의 길이의 데이터를 고정된 길이의 데이터로 출력하는 함수입니다. 자료구조에서도 사용되고, 암호용으로 사용되기도 하죠. 이 문제에서는 알파벳(a~z) 에 1~26까지 순서대로 고유 번호를 부여하여 해시 값을 계산합니다. 하지만, 이렇게만 하면 비둘기 집의 원리* 에 의해 중복되는 해시 값을 가질 수 있습니다. (문자열은 다르지만 구성하는 알파벳이 같다면 해시 값이 동일하게 나옵니다.) 따라서, 충돌(중복)이 최대한 적게 일어나게 하기 위해 각 항에도 고유 번호(항의 번호에 해당되는 만큼 특정 숫자를 거듭제곱해 곱해주기)를 부여합니다. 최종적으로 이 함수가 문제에서 말하는 해시 함수입니다. 이 함수는 자주 쓰인다고 하니 꼭 기억해두는게 좋을 것 같습니다...