C++ : 해쉬를 통해 좌표가 있는지 판단할 때., set과 unordered_set자료구조에 대한 이해의 필요성
1. 해쉬를 통해 좌표가 있는지 판단할 때
해쉬를 통해서 해당 좌표가 있는지 판단하기 위해, set<pair<int,int>>를 통해 판단할 수 있습니다. 하지만, set은 사실 해쉬를 통한 도구가 아니고 정렬 도구입니다. 따라서 해당 좌표가 있는지 판단하는데 O(logn)이 걸립니다. 그와 반대로, unordered_set은 해쉬를 이용한 도구이기 때문에 해당 좌표가 있는지 평균O(1)이 걸립니다. 해당 좌표가 있는지 판단하는데 가장 최적화된 방법을 사용하기 위해선 다음의 글을 이해할 필요가 있습니다.
2. set과 unordered_set의 차이점
set
- 내부 구현: std::set은 균형 이진 탐색 트리 (예: 레드-블랙 트리)를 사용합니다.
- 정렬: 요소들은 자동으로 정렬된 상태로 유지됩니다.
- 시간 복잡도: 삽입, 삭제, 탐색 연산이 O(log n)의 시간 복잡도를 가집니다.
- 특징: 요소가 정렬된 상태로 유지되기 때문에 범위 기반 쿼리와 같은 작업에 적합합니다.
unordered_set
- 내부 구현: std::unordered_set은 해시 테이블을 사용합니다.
- 정렬: 요소들은 해시 값을 기반으로 저장되므로, 정렬되지 않습니다.
- 시간 복잡도: 평균적으로 삽입, 삭제, 탐색 연산이 O(1)의 시간 복잡도를 가집니다.
- 특징: 빠른 삽입과 탐색이 필요하지만 요소의 순서는 중요하지 않을 때 적합합니다.
3. 왜 set<pair<int,int>>는 가능하고 unordered_set<pair<int,int>>는 불가능한가?
set<pair<int,int>> 가능 이유
std::set은 내부적으로 균형 이진 탐색 트리를 사용하므로 요소 간의 비교를 위해 < 연산자를 사용합니다. std::pair<int, int>는 < 연산자를 제공하므로 std::set에서 별도의 설정 없이 사용할 수 있습니다.
#include <iostream>
#include <set>
using namespace std;
int main() {
set<pair<int, int>> s;
s.insert({1, 2});
s.insert({2, 3});
s.insert({1, 4});
s.insert({2, 1});
for (auto p : s) {
cout << "(" << p.first << ", " << p.second << ")" << endl;
}
return 0;
}
unordered_set<pair<int,int>> 불가능 이유
std::unordered_set은 해시 테이블을 사용하여 요소를 저장합니다. 따라서 저장하려는 요소 타입에 대한 해시 함수가 필요합니다. std::pair<int, int>에 대해 기본적으로 제공되는 해시 함수가 없기 때문에, 이를 사용하려면 사용자 정의 해시 함수를 제공해야 합니다.
#include <iostream>
#include <unordered_set>
#include <utility>
#include <functional>
using namespace std;
// 사용자 정의 해시 함수
struct pair_hash {
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const {
auto h1 = hash<T1>{}(p.first);
auto h2 = hash<T2>{}(p.second);
return h1 ^ h2;
}
};
int main() {
unordered_set<pair<int, int>, pair_hash> us;
us.insert({1, 2});
us.insert({2, 3});
us.insert({1, 4});
us.insert({2, 1});
for (auto p : us) {
cout << "(" << p.first << ", " << p.second << ")" << endl;
}
return 0;
}
4. map<pair<int,int>,string>과 unordered_map<pair<int,int>,string>의 차이점
map<pair<int,int>,string> 가능 이유
std::map은 std::set과 유사하게 균형 이진 탐색 트리를 사용합니다. std::pair<int, int>는 < 연산자를 제공하므로, std::map에서도 별도의 설정 없이 사용할 수 있습니다.
#include <iostream>
#include <map>
#include <utility>
using namespace std;
int main() {
map<pair<int, int>, string> m;
m[{1, 2}] = "abc";
m[{2, 3}] = "abd";
m[{1, 4}] = "abc";
m[{2, 1}] = "fbf";
for (auto iter : m) {
cout << "(" << iter.first.first << ", " << iter.first.second << ") : " << iter.second << endl;
}
return 0;
}
unordered_map<pair<int,int>,string> 불가능 이유
std::unordered_map도 std::unordered_set과 마찬가지로 해시 테이블을 사용합니다. 따라서 std::pair<int, int>에 대한 해시 함수를 제공해야 합니다.
#include <iostream>
#include <unordered_map>
#include <utility>
#include <functional>
using namespace std;
// 사용자 정의 해시 함수
struct pair_hash {
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const {
auto h1 = hash<T1>{}(p.first);
auto h2 = hash<T2>{}(p.second);
return h1 ^ h2;
}
};
int main() {
unordered_map<pair<int, int>, string, pair_hash> um;
um[{1, 2}] = "abc";
um[{2, 3}] = "abd";
um[{1, 4}] = "abc";
um[{2, 1}] = "fbf";
for (auto iter : um) {
cout << "(" << iter.first.first << ", " << iter.first.second << ") : " << iter.second << endl;
}
return 0;
}
요약
- std::set과 std::map은 균형 이진 탐색 트리를 사용하여 요소를 저장하고 정렬합니다. 이들 컨테이너는 요소 간의 비교를 위해 < 연산자를 사용하며, std::pair는 기본적으로 < 연산자를 제공하므로 별도의 설정 없이 사용할 수 있습니다.
- std::unordered_set과 std::unordered_map은 해시 테이블을 사용하여 요소를 저장합니다. 이들 컨테이너를 사용하려면 저장하려는 요소 타입에 대한 해시 함수를 제공해야 합니다. std::pair에 대해 기본적으로 제공되는 해시 함수가 없기 때문에 사용자 정의 해시 함수를 정의해야 합니다.
- 하지만, 해쉬테이블을 직접 작성하는 것은 번거로운 일이니, 코딩테스트에서나 굳이 데이터가 엄청 들어오지 않는 상황이라면 set을 쓰자