BBTY의 공부 기록 BBTY의 공부 기록

백준 단계별로 풀어보기에서 집합과 맵 부분의 14425번을 풀다가 처음으로 손도 못대고 막혔다. 맵을 쓰지 않으니 시간 초과가 나고.. 맵을 쓰자니 C++에서 어떻게 구현을 하는지도 모르겠고 STL도 어떻게 쓰는지도 모르겠고.. 옛날에 자바할 때 한 번 써본 기억이 있는데 너무 오래 전이라 지금은 개념정도밖에 기억나지 않는다. 그래서 이왕 이렇게 된 김에 정리도 하고 STL도 암기하자는 생각으로 글을 쓴다. 문제 링크: https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검..

C++의 map 자료구조에 대해 공부하다 원리가 Hash임을 알게 되었고, 원리를 정확히 알고 쓰자는 생각으로 짧게 정리해보려 한다. 원소의 값에 의해 원소가 저장되는 위치가 결정되는 자료구조. 검색, 삽입, 삭제 등의 연산을 평균적으로 상수 시간에 할 수 있음. O(1) 해싱(Hashing) - 매핑의 전체 과정 키(Key) - 매핑 전 원래 데이터의 값 해시함수(Hash Function) - 임의의 길이의 데이터를 특정 길이의 데이터로 변환하는 함수 해시값(Hash Value) - 매핑 후 데이터의 값 해시함수를 통해 해시값을 할당할 때, 중복되는 인덱스값을 사용하게 되면 해시충돌이 일어남. 해결 방법 1 - 체이닝(Chaining) 같은 인덱스로 해싱되는 노드..