키에 대응되는 값을 저장하는 자료구조이다.
insert, erase, find, update 모두 O(1)에 할 수 있다.
해시 자료구조에서는 해시 함수라는게 쓰인다.
*해시 함수 : 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수
unordered_multimap은 자주 쓰이지 않는다.
*충돌 : 서로 다른 키가 같은 해시 값을 가지게 될 경우 발생한다.
충돌이 발생하는 것 자체는 달리 막을 방법이 없다. 하지만 충돌이 발생했을 때 회피하는 방법이 존재한다.
크게 Chaining과 Open Addressing으로 나뉜다.
Chaining
각 인덱스마다 연결 리스트를 둬서 충돌 회피를 하는 방법. STL의 해시 자료구조는 Chaining을 이용한다.
이상적인 상황에서는 O(1)이지만 충돌이 빈번하게 일어날수록 성능이 저하되고 최악의 상황에는 O(N)이다.
Open Addressing
해시 충돌 발생시 다음 인덱스들 중에 비어있는 인덱스를 이용한다.
find는 해당 값의 인덱스부터 비어있는 칸을 만날때까지 탐색을 한다.
erase의 경우 그냥 값을 지워버리면 find시 문제가 발생하기 때문에 삭제시 더미데이터로 교체한다.
insert는 빈칸 혹은 더미데이터가 있는 칸에 삽입할 수 있다.
*Linear Probing
장점 : Cache hit rate가 높다
단점 : Clustering이 생겨서 성능에 안좋은 영향을 준다
*Quadratic Probing
장점 : Cache hit rate가 나쁘지 않다. Clustering을 어느정도 회피할 수 있다.
단점 : 해시 값이 같을 경우 여전히 Clustering이 발생한다.
*Double Hashing : 충돌 발생 시 이동할 칸의 수를 새로운 해시 함수로 계산하는 방식
장점 : Clustering을 효과적으로 회피할 수 있다.
단점 : Cache hit rate가 낮다.
구현
Load factor = 원소의 개수 / 테이블의 크기
삽입의 최대 횟수가 곧 해시 테이블에 들어있는 원소의 최대 개수가 된다.
Chaining의 경우 어느정도의 충돌을 감수하고 Load factor를 1 이하가 되게끔 한다.
Open Addressing의 경우 Load factor를 0.75 이하로 둔다. (1.33배 정도)
테이블의 크기를 M이라고 하면 정수에 대한 해시 함수는 M으로 나눈 나머지로 정할 수 있다.
문자열에 대한 해시 함수는 롤링 해시를 사용하면 된다.
const int M = 1000003;
const int a = 1000;
int my_hash(string& s)
{
int h = 0;
for (auto x : s)
h = (h * a + x) % M;
return h;
}
my_hash("abc") = ('a'×1000²+'b'×1000¹+'c'×1)%M
추후 추가로 작성예정
연습 문제
7785: 회사에 있는 사람
#include <bits/stdc++.h>
using namespace std;
int n;
unordered_set<string> h;
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
while (n--)
{
string name, s;
cin >> name >> s;
if (s == "enter")
h.insert(name);
else
h.erase(name);
}
vector<string> ans(h.begin(), h.end());
sort(ans.begin(), ans.end(), greater<>());
for (auto& a : ans)
cout << a << '\n';
return 0;
}
해시를 이용해 편하게 푼 코드. sort의 greater<>() 는 내림차순 정렬을 위한 임시 객체이다.
기본적으로 오름차순 정렬인데, 명시적으로 써줄 경우 less<>()로 명시할 수 있다.
1620: 나는야 포켓몬 마스터 이다솜
#include <bits/stdc++.h>
using namespace std;
int n, m;
unordered_map<string, int> h1;
unordered_map<int, string> h2;
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i)
{
string s;
cin >> s;
h1.insert({ s, i });
h2.insert({ i, s });
}
while (m--)
{
string s;
cin >> s;
if (isdigit(s[0])) cout << h2[stoi(s)] << '\n';
else cout << h1[s] << '\n';
}
return 0;
}
h2를 쓰지 않고 string배열을 하나 더 만들어서 사용해도 된다.
기본 문제
13414: 수강 신청
#include <bits/stdc++.h>
using namespace std;
unordered_map<string, int> h;
int k, l;
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> k >> l;
for (int i = 0; i < l; ++i)
{
string s;
cin >> s;
h[s] = i;
}
vector<pair<string, int>> v(h.begin(), h.end());
sort(v.begin(), v.end(), [](auto& a, auto& b) { return a.second < b.second; });
for (int i = 0; i < k; ++i)
{
if (i >= v.size()) break;
cout << v[i].first << '\n';
}
return 0;
}
17219: 비밀번호 찾기
#include <bits/stdc++.h>
using namespace std;
unordered_map<string, string> h;
int n, m;
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; ++i)
{
string s1, s2;
cin >> s1 >> s2;
h.insert({ s1, s2 });
}
for (int i = 0; i < m; ++i)
{
string s;
cin >> s;
cout << h[s] << '\n';
}
return 0;
}
9375: 패션왕 신해빈
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tc;
cin >> tc;
while (tc--)
{
unordered_map<string, int> h;
int n, answer = 1;
cin >> n;
for (int i = 0; i < n; ++i)
{
string s1, s2;
cin >> s1 >> s2;
h[s2]++;
}
for (auto& elem : h)
answer *= elem.second + 1; // 단독인 경우도 포함돼서 +1
cout << answer - 1 << '\n'; // 알몸인 경우 제외
}
return 0;
}
30분정도 삽질하다가 도저히 답이 안나와서 정답코드 보고 조금 이해함
16165: 걸그룹 마스터 준석이
#include <bits/stdc++.h>
using namespace std;
int n, m;
unordered_map<string, string> h1;
unordered_map<string, vector<string>> h2; // multimap보다 훨씬 간결하게 구현 가능
int main(void)
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m;
while (n--)
{
string a;
int b;
cin >> a >> b;
while (b--)
{
string st;
cin >> st;
h1[st] = a;
h2[a].push_back(st);
}
sort(h2[a].begin(), h2[a].end());
}
while (m--)
{
string a;
int b;
cin >> a >> b;
if (b)
cout << h1[a] << '\n';
else
for (auto& elem : h2[a]) cout << elem << '\n';
}
return 0;
}
11478: 서로 다른 부분 문자열의 개수
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
string str;
set<string> answer;
cin >> str;
for (int i = 0; i < str.length(); ++i)
{
for (int j = 1; j <= str.length() - i; ++j)
answer.insert(str.substr(i, j));
}
cout << answer.size();
return 0;
}
19583: 사이버 개강총회
#include <bits/stdc++.h>
using namespace std;
string s, e, q;
unordered_set<string> a;
unordered_set<string> b;
int answer = 0;
int main(void)
{
ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cin >> s >> e >> q;
while (true)
{
string s1, s2;
cin >> s1 >> s2;
if (s1 == "" && s2 == "") break;
if (s1 <= s) a.insert(s2);
else if (s1 >= e && s1 <= q) b.insert(s2);
}
for (auto& i : a)
if (b.find(i) != b.end()) answer++;
cout << answer;
return 0;
}
30분정도 떠올려도 도무지 떠오르지 않아서 구글링으로 해답을 찾아봤음. 사고가 유연하지 않다는걸 또 한번 깨달음. 나는 빡대가리다..
범위와 형식이 00:00:00~23:59:59이기 때문에 따로 문자열 parsing을 하지 않고 바로 비교를 해도 문제가 없다.
개강총회 시작전에 포함된 인원과 종료시간 사이에 포함된 인원이 겹치면 출석 인정.
'알고리즘 > 바킹독의 실전 알고리즘' 카테고리의 다른 글
| [0x17] 우선순위 큐 (0) | 2022.08.07 |
|---|---|
| [0x16] 이진 검색 트리 (0) | 2022.08.06 |
| [0x14] 투 포인터 (0) | 2022.08.05 |
| [0x13] 이분탐색 (0) | 2022.08.05 |
| [0x12] 수학 (0) | 2022.08.05 |