Map, Set

map과 set은 어떤 값을 빠르게 저장하고 불러오기 위해 사용하는 자료구조입니다. map은 key-value pair구조로 되어 있어서 특정한 key에 대해 하나의 value가 있습니다. 파이썬에서는 딕셔너리라고도 부릅니다. set은 수학의 집합처럼 여러 데이터를 저장하지만 key없이 value만 있습니다. 당연히 map의 key는 중복될 수 없고 set의 value도 중복될 수 없습니다.

map과 set의 중요한 특징 중 하나는 값을 찾는 과정이 \( O(1) \)에 이루어진다는 것입니다. 예를 들어, 어떤 배열이 있고 그 배열에 어떤 값이 있는지 확인하려면 하나씩 순회하면서 \( O(N) \) 시간을 사용해야만 합니다. 하지만 set 안에 어떤 값이 들어있는지 확인하려면 \( O(1) \) 시간에 할 수 있습니다. 이것이 가능한 이유는 hash를 기반으로 작동하기 때문입니다.

Hash

해시는 어떤 입력에 대해 특정한 문자열(또는 숫자)를 반환하는 함수입니다. 해시 함수의 특징은 다음과 같습니다.

입력값에 상관없이 고정된 길이의 출력 생성
빠르게 계산됨
결정적 (deterministic)
1. 같은 입력이라면 항상 같은 출력을 만들어야 함
충돌 회피 (collision resistance)
1. 서로 다른 두 입력에서 같은 출력이 나올 가능성이 매우 낮거나 불가능해야 함
역산 불가능 (one-way)
1. 해시를 보고 원래 값을 유추하기 매우 어렵거나 불가능해야 함
입력 변화에 민감
1. 입력이 조금만 바뀌더라도 해시 함수의 출력은 매우 크게 바뀌어야 함

해시 함수 그 자체에 대해서는 깊게 다루진 않겠지만 저런 특징이 있다는 것은 알아두면 좋습니다. 해시 함수의 입력은 꼭 정수가 아닐 수 있고 문자열이나 객체일 수도 있습니다. 마찬가지로 출력도 문자열이나 숫자일 수 있고 길이도 각 알고리즘마다 상이합니다. 아래는 간단한 해시 함수의 예시입니다.

unsigned int hash(int x, int M = 1000) {
    const unsigned int A = 2654435761u;  // Knuth 상수
    const unsigned int P = 4294967291u;  // 2^31에 가까운 소수
    return ((x * A) % P) % M;
}

참고로 int는 그 자체로 유일하기 때문에 해싱을 하지 않기도 합니다. 당연히 실제로 사용할 해시 함수는 이거보다 복잡하고 범용적입니다. C++에서는 std::hash\<T>가 있고 파이썬에서는 hash 함수가 있어서 해시 함수 자체를 직접 구현할 일은 많지 않습니다.

Tree vs Hash

파이썬의 딕셔너리는 hash map입니다. 그러니까 key에 해싱을 적용해서 사용합니다. 이런 경우 key로 값을 읽고 쓰는게 \( O(1) \)시간에 처리됩니다. 반면 C++의 map\<K, V>는 tree map입니다. 트리맵은 데이터를 이진 검색 트리 구조(BST)로 저장하는데, 트리에 대해서는 나중에 자세히 알아보겠지만, 전체 데이터를 반씩 줄여가면서 탐색합니다. 그래서 시간복잡도가 \( O(\log n) \)에 처리됩니다. 트리맵은 해시맵보다 느리지만 트리에 저장할 때 정렬된 상태로 유지하기 때문에 데이터가 정렬된 상태로 꺼내지게 됩니다. 그래서 정렬된 상태가 필요하지 않다면 더 빠른 해시맵을 사용하는게 좋습니다. C++에서는 unordered\_map\<K, V>으로 구현되어 있습니다.

10815번: 숫자 카드

10815번: 숫자 카드. 최대 50만개의 카드가 주어지고 최대 50만번 특정 숫자가 적힌 카드를 가지고 있는지 확인해야 합니다. 만약 50만개의 수를 저장하는 배열을 만들고 일일히 탐색한다면 \( O(NM) \)의 시간복잡도를 가지게 되어 2초 안에 작동하지 않습니다. 그럼 다른 방법으로 배열을 사용하는 방법이 있습니다. has\[100] 처럼 사용해서 true라면 100이 있는 방식입니다. 하지만, 수의 범위가 \( \pm \)천만 이기 때문에 2천만 크기의 배열을 만든다면 \( 4 \times 10^8 \approx 3.7 \,\, \text{GB} \)로 어마어마한 양의 메모리를 사용해 버리기 때문에 MLE(메모리 초과)를 받습니다. 그래서 이때 필요한 것이 해시입니다. 해시 맵과 셋 중 아무거나 사용해도 상관은 없는데, 맵에 저장되는 값이 필요가 없고 존재하는지 여부만 확인하면 되기 때문에 셋을 사용해서 하도록 하겠습니다.

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n;
    cin >> n;
    unordered_set<int> s;
    while (n--) {
        int x;
        cin >> x;
        s.insert(x);
    }

    int m;
    cin >> m;
    while (m--) {
        int x; cin >> x;
        if (s.find(x) != s.end()) {
            cout << "1 ";
        } else {
            cout << "0 ";
        }
    }
}

확실히 파이썬이 간결하네요. 참고로 파이썬은 줄 단위로 읽어서 입력을 4번으로 처리하지만 C++에서는 100만번 이상의 입력이 필요하기 때문에 FastIO를 적용하지 않으면 시간초과를 받습니다. 파이썬에서는 in 연산자를 통해 등록되어 있는지 확인할 수 있고 C++에서는 find가 end와 같지 않은지 확인해서 찾을 수 있습니다. 또는, count(x)를 통해 x의 개수를 세서 존재하는지 확인할 수도 있습니다.

보충 : 해시 테이블

해시에 대해서 언급하지 않고 넘어갔던 부분이 있는데, 바로 어떻게 해시를 가지고 \( O(1) \)만에 원하는 데이터를 찾는지 입니다. 그건 HashTable이라는 자료구조 덕분에 가능합니다. 해시 테이블은 각각의 key에 해시 함수를 적용해 고유한 index를 만들어 배열처럼 관리합니다. 여기서 실제 값이 저장되는 장소를 버킷(bucket)또는 슬롯(slot)이라고 합니다. 예를 들어, 인덱스를 아래처럼 구한다고 생각해봅시다.

int index = hash(key) % table_size

해시 함수 한 번만 실행하면 되기 때문에 \( O(1) \)에 처리할 수 있게 됩니다. 여기서 중요한 것은 고유한 index 값을 찾는 것입니다. 이론상 아무 해시도 충돌하지 않는다면 \( O(1) \)에 모두 처리할 수 있겠지만 종종 충돌하기도 합니다. 이럴 때 충돌을 처리하기 위해 Chaining, Open Addressing 등 여러 기법을 사용하게 됩니다. 해시 충돌이 어마어마하게 자주 일어나는 최악의 경우에는 시간복잡도가 \( O(n) \)까지 느려지기도 하지만, 내장 라이브러리에서 제공되는 해시 map, set은 굉장히 잘 만들어져서 거의 \( O(1) \)에 작동하기 때문에 대부분 신경쓰지 않아도 괜찮습니다.

Map, Set

Map, Set

Hash

Tree vs Hash

10815번: 숫자 카드

보충 : 해시 테이블

연습문제