IT_Study/C++
[C++] Bit operation, 구조체를 활용한 Map 사용법 정리
__Vivacé__
2023. 2. 23. 10:18
Bit Operation(비트 연산)
컴퓨터에서 데이터를 비트(0 또는 1) 단위로 조작하는 연산
주로 컴퓨터에서 비트맵, 마스크(mask), 효율적인 데이터 압축, 암호화 등에 사용
*비트(Bit) : "binary digit"의 줄임말로, 0 또는 1의 값을 가지는 이진수(binary number)의 한 자릿수를 나타냄.
비트 연산자(Bit operator)
1. AND 연산(&)
두 비트가 모두 1인 경우에만 1을 반환
#include <iostream>
using namespace std;
int main() {
int a = 10; // 1010
int b = 12; // 1100
// AND 연산
int c = a & b; // 1000
cout << "a & b = " << c << endl; // a & b = 8
}
2. OR 연산(|)
두 비트 중 하나라도 1인 경우에 1을 반환
#include <iostream>
using namespace std;
int main() {
int a = 10; // 1010
int b = 12; // 1100
// OR 연산
int d = a | b; // 1110
cout << "a | b = " << d << endl; // a | b = 14
}
3. XOR 연산(^)
두 비트가 서로 다른 경우에만 1을 반환
#include <iostream>
using namespace std;
int main() {
int a = 10; // 1010
int b = 12; // 1100
// XOR 연산
int e1 = a ^ b; // 0110
cout << "a ^ b = " << e1 << endl; // a ^ b = 6
int e2 = a ^ b ^ a ^ b ^ a;
cout << "a ^ b ^ a ^ b ^ a = " << e2 << endl;
// a ^ b ^ a ^ b ^ a = 10;
// a로 돌아온다는 사실을 알 수 있음 -> 암호화에 많이 쓰임
}
4. NOT 연산(~)
비트를 모두 반대로 뒤집음
#include <iostream>
using namespace std;
int main() {
int a = 10; // 1010
// NOT 연산
int f = ~a; // 0101
cout << "~a = " << f << endl; // ~a = -11
// 10진수 : -a - 1;
}
5. 왼쪽 시프트 연산(<<)
비트를 왼쪽으로 이동
#include <iostream>
using namespace std;
int main() {
int a = 10; // 1010
// 왼쪽 시프트 연산
int g = a << 1; // 10100
cout << "a << 1 = " << g << endl; // a << 1 = 20
}
6. 오른쪽 시프트 연산(>>)
비트를 오른쪽으로 이동
#include <iostream>
using namespace std;
int main() {
int b = 12; // 1100
// 오른쪽 시프트 연산
int h = b >> 1; // 0110
cout << "b >> 1 = " << h << endl; // b >> 1 = 6
}
Hash (해시 함수; hash function)
- 임의의 크기의 데이터를 고정된 크기의 데이터로 매핑하는 함수
- 특정 값들을 찾아줄수 있는 Key로 변환해주는 함수
*해시 값(hash value) : 해시 함수를 통해 입력 데이터를 고정된 크기의 값으로 변환한 결과값을 의미
*버킷(bucket) : 실제 데이터가 저장되는 공간, 슬롯(slot)이라고도 함
Hash Collision(해시 충돌)
서로 다른 데이터를 입력해도, 해시 함수를 통해 생성된 해시 밸류가 중복되어 문제가 발생한 경우
#include <iostream>
#include <unordered_map>
using namespace std;
int hF(int key){
return key%10;
}
int main() {
unordered_map<int, string> myMap;
myMap[hF(1)] = "apple";
myMap[hF(2)] = "banana";
// key 1과 key 11이 같은 해시값을 가지는 충돌이 발생한다.
myMap[hF(11)] = "strawberry";
cout << "myMap[1] = " << myMap[hF(1)] << endl; // "strawberry" 출력
cout << "myMap[2] = " << myMap[hF(2)] << endl; // "banana" 출력
}
Hash collision의 원인
- 해시 함수의 크기 제한
- 입력 데이터의 크기가 클 때
- 해시 함수를 통해 생성된 해시 밸류가 고르게 분포하지 않을 가능성이 높아짐
- 해시값의 크기가 매우 작을 때
- 서로 다른 입력 데이터에 대해 중복될 가능성이 높아짐
- 입력 데이터의 크기가 클 때
- 입력 데이터의 분포
- 입력 데이터가 균등하게 분포된 경우에는, 해시 함수를 통해 생성된 해시 밸류들도 균등하게 분포될 가능성이 높아져, 해시 충돌이 발생할 확률이 줄어듦
- 입력 데이터가 균등하게 분포되지 않은 경우에는 해시 밸류도 균등하게 분포되지 않을 가능성이 있으며, 이로 인해 해시 충돌이 발생할 확률이 높아짐
- 해시 함수의 설계
- 해시 함수의 설계가 충분히 좋지 않은 경우, 일부 입력 데이터에 대해 해시 충돌이 발생할 가능성이 높아짐
Hash collision이 발생할 시 대표적인 해결 방법
- Separate Chaining (체이닝) : 충돌이 발생한 버킷에 연결 리스트를 사용하여 데이터를 삽입하는 방법
- 장점
- 한정된 메모리를 효율적으로 사용 가능
- 해시 함수 선정의 중요성이 상대적으로 작음
- 단점
- 특정 해시 값이 가리키는 bucket에 데이터가 계속 추가된다면, 검색 효율이 떨어질 수 있음
- 외부 저장 공간을 사용하기 때문에, 추가적인 공간이 필요
- 장점
- Open addressing (개방 주소법) : 비어있는 버킷(bucket)을 찾아 데이터를 저장하는 기법
- 장점
- 해시테이블 내에서 데이터 저장 및 처리가 가능
- 단점
- 해시 함수의 성능에 전체 해시테이블의 성능이 달라짐
- 데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해야 함
- 방식
- 선형 탐색(Linear Probing): 다음 해시(+1)나 n개(+n)를 건너뛰어 비어있는 해시에 데이터를 저장
- 제곱 탐색(Quadratic Probing): 충돌이 일어난 해시의 제곱을 한 해시에 데이터를 저장
- 이중 해시(Double Hashing): 다른 해시함수를 한 번 더 적용한 해시에 데이터를 저장
- 장점
C++ 에서의 Map 활용
1. Unordered map
Hast table 구조를 이용하여 구현
- 장점
- 시간 복잡도
- 데이터 삽입, 제거, 탐색 : O(1) ~ O(logN)
- Hash function도 시간 복잡도에 영향을 미침
- 시간 복잡도
- 단점
- 데이터를 정렬하지 않음 → 범위 검색(~이상 ~이하인 값을 찾아보자 등)에는 부적합
- Hash collision 발생 확률이 있음
메서드 사용법
#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<int, int>info;
int main() {
// 1. insert() 메서드를 이용한 데이터 추가 - info.insert({ key, value })
info.insert({ 1, 1 });
cout << info[1]; // 1
// 1-1. 기존에 key에 값이 있다면 덮어씌워지는 게 아니라 무시됨
info.insert({ 1, 2 });
cout << info[1]; // 1
// 2. [] 연산자를 이용한 데이터 추가 - info[key] = value;
info[2] = 2;
cout << info[2]; // 2
// 2-1. 이 방식은, 기존에 key 값이 존재하더라도 덮어씌워짐
info[2] = 3;
cout << info[2]; // 3
// 2-2. 호출만 되어도 값이 알아서 저장이 됨 - 유의할 것
if (info[4] != 1)
cout << info[4]; // 0 <- value가 int type이면 호출되면 알아서 0 저장
// 2-2. find() 메서드를 이용한 key 탐색
if (info.find(2) == info.end())
cout << "입력한 key가 존재하지 않음";
else
cout << "입력한 key가 존재함";
// 3. at() : 주어진 key에 해당하는 value를 반환
// at() 메서드는 key가 존재하지 않을 경우 예외를 발생 - 예외 처리 필요
// 4. count() : 주어진 key가 map에 존재하는 지 여부를 반환 - 있으면 1 없으면 0
// count() 메서드는 예외를 발생시키지 않음
cout << endl;
// 5. traversal / iteration - 시간이 많이 걸림
// first : key, second : value
for (auto it = info.begin(); it != info.end(); it++) {
cout << it->first << " " << it->second << '\\n';
}
}2. Map
Red-Black Tree(레드-블랙 트리)를 이용하여 구현
- 장점
- 데이터를 정렬된 상태로 유지 → 범위 검색에 용이
- Binary Search Tree이기 때문에, Hash collision이 일어나지 않음
- 단점
- 생성, 제거, 탐색이 O(logN)으로, Unordered map보다 느림
- 데이터 양이 많은 경우 불리
메서드 사용법
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, string> m;
// insert() 메서드를 이용한 데이터 추가
m.insert(make_pair(1, "John"));
m.insert(make_pair(2, "Jane"));
m.insert(make_pair(3, "Tom"));
// [] 연산자를 이용한 데이터 추가
m[4] = "Alice";
m[5] = "Bob";
m[6] = "Charlie";
// find() 메서드를 이용한 key 탐색
if (m.find(3) != m.end()) {
cout << "key 3 is found" << endl;
}
if (m.find(7) == m.end()) {
cout << "key 7 is not found" << endl;
}
// 데이터 순회
for (auto iter = m.begin(); iter != m.end(); iter++) {
cout << "key: " << iter->first << ", value: " << iter->second << endl;
}
// lower_bound()와 upper_bound() 메서드 사용 예시
// lower_bound() : 특정 key 값 '이상'인 첫 번째 iterator(key, value 쌍) 반환
// upper_bound() : 특정 key 값 '초과'인 첫 번째 iterator(key, value 쌍) 반환
auto it1 = m.lower_bound(6); // key: 6, value: Charlie
auto it2 = m.upper_bound(6); // key-value pair not found
if (it1 != m.end()) { // 반복자가 end()를 가리키는지 확인
cout << "key: " << it1->first << ", value: " << it1->second << endl;
}
else {
cout << "key-value pair not found" << endl;
}
// equal_range() 메서드 사용 예시
// lower_bound()와 upper_bound()를 동시 실행 - 조건에 맞는 모든 key-value 쌍을 반환
// 보통 중복된 key 값을 가질 수 있는 multimap에서 사용
auto range = m.equal_range(5);
for (auto it = range.first; it != range.second; it++) {
cout << "key: " << it->first << ", value: " << it->second << endl;
}
// rbegin()와 rend() 메서드 사용 예시
// 역방향 반복자를 반환하는 메서드 : rbegin = reverse begin
for (auto it = m.rbegin(); it != m.rend(); it++) {
cout << "key: " << it->first << ", value: " << it->second << endl;
}
// size()와 max_size() 메서드 사용 예시
// size() : map 컨테이너에 저장된 key-value 쌍의 수를 반환
// max_size() : map 컨테이너가 저장할 수 있는 최대 key-value 쌍의 개수를 반환
cout << "size: " << m.size() << endl;
cout << "max_size: " << m.max_size() << endl;
return 0;
}
Struct를 이용한 map 구현
#include <iostream>
#include <unordered_map>
using namespace std;
struct Node {
int y, x;
// == : Node 탐색에 대한 연산자 Overriding
// map은 항상 hash function을 통해 변환된 bucket 안에
// (1) 실제 값 (hash function을 통해 변환되기 전의 original 값)
// (2) value (key : value pair에서의 value)를 저장하고 있다.
// 즉, chaining이 된 상태에서, 지금 내 값과 동일한 Node가 존재하는지를 확인해야
// 할때 사용하는 == operator를 overriding 한다
bool operator == (Node next) const {
// 만약 나랑 값이 같다면
if (y == next.y && x == next.x)
return true; // bucket -> chaining 된 hash function으로 변환 된 값들 중 나를 return 해라
return false;
}
};
struct HashFunc {
// size_t : 운영 체제에 따라 만들 수 있는 가장 큰 "고정된" bit size
// -> 32bit 운영체제에서는 32bit (unsigned int)
// -> 64bit 운영체제에서는 64bit (long long)
// (x * y) % 10 = key
size_t operator()(Node node) const {
return node.y * node.x % 10;
}
};
int main() {
Node nodes[] = { {2, 2}, {2, 3}, {1, 1}, {2, 3}, {4, 5} };
unordered_map<Node, int, HashFunc>um;
// 5개의 노드에 대한 개수 저장
// map에서, 당연히 key가 되는 Node는 고유(unique) 값이여야 한다.
for (int i = 0; i < 5; i++) {
if (um.find(nodes[i]) == um.end())
um[nodes[i]] = 1;
else
um[nodes[i]]++;
}
// um 내에 존재하는 iterator(it) 반환
for (auto it = um.begin(); it != um.end(); it++) {
cout << "(" << it->first.y << "," << it->first.x << ")" << " : " << it->second << '\\n';
}
}