Map, Set

map과 set은 어떤 값을 빠르게 저장하고 불러오기 위해 사용하는 자료구조입니다. map은 key-value pair구조로 되어 있어서 특정한 key에 대해 하나의 value가 있습니다. 파이썬에서는 딕셔너리라고도 부릅니다. key를 통해 value를 빠르게 찾을 수 있습니다.

set은 집합을 구현한 자료구조입니다. 수학에서의 집합과 동일하게 중복된 값을 허용하지 않고, 순서가 없습니다. 마찬가지로 특정한 값이 있는지 빠르게 찾을 수 있습니다.

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

Hash

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

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

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

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

참고로 int는 그 자체로 유일하기 때문에 해싱을 하지 않기도 합니다. 당연히 실제로 사용할 해시 함수는 이거보다 복잡하고 범용적입니다. C++에서는 std::hash<T>가 있고 파이썬에서는 hash 함수가 있어서 간단한 타입에 대해서는 직접 해시 함수를 만들지 않아도 됩니다. C++의 경우 해시가 지원되지 않는 타입을 해시 맵이나 셋의 key로 사용하려면 직접 해시 함수를 만들어서 등록해 주어야 합니다.

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이 있는 방식입니다. 수의 범위가 \( [-10^7, 10^7] \) 이기 때문에 2천만 크기의 배열을 만든다면 \( 2 \times 10^7 \approx 19 \,\, \text{MB} \)로 충분히 만들 수 있기는 합니다. 만약 값의 범위가 더 컸다면 불가능 했을 것입니다. 그래도 수의 개수는 50만인데 배열의 개수는 2천만이기 때문에 버려지는 메모리가 많습니다. 이럴 때 해시 맵이나 셋을 사용하면 메모리를 훨씬 절약할 수 있습니다. 해시 맵과 셋 중 아무거나 사용해도 상관은 없는데, 맵에 저장되는 값이 필요가 없고 존재하는지 여부만 확인하면 되기 때문에 셋을 사용해 보도록 하겠습니다.

#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 ";
        }
    }
}

확실히 파이썬이 간결하네요. 파이썬에서는 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번: 숫자 카드

보충 : 해시 테이블

연습문제