집합과 맵 (Set and Map)

정의

집합 (Set) 은 고유한 원소들의 모임을 나타내는 추상 자료구조로, 멤버십 검사, 삽입, 삭제를 지원한다. 맵 (Map, Dictionary) 은 키-값 쌍을 저장하며, 키로 값을 빠르게 조회할 수 있다. 집합과 맵은 수학적 집합 개념을 프로그래밍에서 구현한 것으로, 중복 없는 데이터 관리와 빠른 검색이 핵심이다.

구현 방식에 따라 해시 기반 (평균 O(1)) 또는 트리 기반 (O(log N)) 으로 나뉜다.

문제 상황과 동기

다음과 같은 상황에서 집합/맵이 필요하다:

• 멤버십 검사: “이 원소가 집합에 있는가?” 를 빠르게 확인
• 중복 제거: N개 원소에서 고유한 값만 남기기
• 키-값 조회: 학번 → 이름, 단어 → 빈도 같은 매핑
• 동적 삽입/삭제: 원소가 실시간으로 추가/제거되는 환경

naive 접근: 배열 순차 탐색 O(N), 매번 삽입 시 중복 검사 O(N). N=10^5, Q=10^5 이면 10^10 연산.

집합/맵: 삽입/조회/삭제를 평균 O(1) (해시) 또는 O(log N) (트리) 에 처리.

핵심 통찰: 원소의 존재 여부만 중요할 때 순서를 버리고 빠른 접근을 택한다.

시각화

핵심 아이디어

추상 자료형 (ADT)

집합과 맵은 다음 연산을 제공한다:

set:
  insert(x)       // x 추가 (중복 무시)
  erase(x)        // x 제거
  contains(x)     // x 존재 여부

map:
  insert(k, v)    // 키 k 에 값 v 매핑
  erase(k)        // 키 k 제거
  get(k)          // 키 k 의 값 반환
  contains(k)     // 키 k 존재 여부

구현 방식

• 해시: 키를 해시 함수로 변환해 버킷에 저장. 충돌 시 체이닝/개방 주소법.
• 트리: 균형 이진 탐색 트리 (BST) 사용. STL은 Red-Black Tree, Java는 Red-Black Tree.

알고리즘

집합의 기본 연산

insert(x):
    if x not in set:
        add x to set

contains(x):
    return x in set

erase(x):
    if x in set:
        remove x from set

맵의 기본 연산

insert(k, v):
    map[k] = v

get(k):
    if k in map:
        return map[k]
    else:
        return null/error

erase(k):
    if k in map:
        remove k from map

구현

// unordered_set (해시), set (트리) 비교
#include <bits/stdc++.h>
using namespace std;
int main() {
  unordered_set<int> hs = {5, 3, 7, 1};
  set<int> ts = {5, 3, 7, 1};
  
  hs.insert(9); ts.insert(9);
  
  cout << "hash_set contains 3? " << (hs.count(3) ? "YES" : "NO") << "\n";
  cout << "tree_set contains 8? " << (ts.count(8) ? "YES" : "NO") << "\n";
  
  cout << "hash_set: ";
  for (auto x : hs) cout << x << " ";
  cout << "\n";
  
  cout << "tree_set (sorted): ";
  for (auto x : ts) cout << x << " ";
  cout << "\n";
}

# set (해시 기반), dict 는 키-값 매핑
hs = {5, 3, 7, 1}
d = {"apple": 10, "banana": 20}
​
hs.add(9)
d["cherry"] = 30
​
print("set contains 3?", 3 in hs)
print("dict key 'apple':", d.get("apple"))
​
print("set:", sorted(hs))  # set 은 순서 없음, sorted 로 정렬
print("dict keys:", list(d.keys()))

// HashSet (해시), TreeSet (트리), HashMap (해시맵)
import java.util.*;
public class Main {
  public static void main(String[] args) {
      HashSet<Integer> hs = new HashSet<>(Arrays.asList(5, 3, 7, 1));
      TreeSet<Integer> ts = new TreeSet<>(Arrays.asList(5, 3, 7, 1));
      HashMap<String, Integer> hm = new HashMap<>();
      
      hs.add(9); ts.add(9);
      hm.put("apple", 10);
      hm.put("banana", 20);
      
      System.out.println("HashSet contains 3? " + hs.contains(3));
      System.out.println("TreeSet contains 8? " + ts.contains(8));
      System.out.println("HashMap get apple: " + hm.get("apple"));
      
      System.out.println("TreeSet (sorted): " + ts);
  }
}

hash_set contains 3? YES
tree_set contains 8? NO
hash_set: 9 1 7 3 5 
tree_set (sorted): 1 3 5 7 9

복잡도

해시 기반 (unordered_set, dict, HashMap)

트리 기반 (set, TreeSet)

변형 및 활용

1. Multiset / Multimap

중복 허용 버전. C++ std::multiset, std::multimap, Java TreeMultiset (Guava).

multiset<int> ms = {3, 3, 5, 5, 5};
cout << ms.count(5);  // 3
ms.erase(ms.find(5)); // 하나만 제거

2. Ordered Map

키를 정렬된 순서로 유지. C++ std::map, Java TreeMap.

map<int, string> m;
m[3] = "three";
m[1] = "one";
for (auto [k, v] : m) cout << k << ": " << v << "\n"; // 1: one, 3: three

3. 빈도 세기 (Frequency Map)

from collections import Counter
words = ["apple", "banana", "apple"]
freq = Counter(words)
print(freq["apple"])  # 2

4. 집합 연산

a = {1, 2, 3}
b = {2, 3, 4}
print(a & b)  # {2, 3} (교집합)
print(a | b)  # {1, 2, 3, 4} (합집합)
print(a - b)  # {1} (차집합)

함정

1. 해시 충돌

해시 함수가 나쁘면 모든 원소가 한 버킷에 몰려 O(N) 성능 저하. 좋은 해시 함수와 적절한 load factor 관리 필요.

2. 순서 가정

unordered_set 은 순서 보장 안 함. 순회 순서가 삽입 순서와 다를 수 있다. 정렬 필요시 set 또는 sorted() 사용.

3. 키 불변성

맵의 키는 불변이어야 한다. C++ 에서 set<vector<int>> 는 가능하나 원소 수정 후 정렬 깨짐 위험.

4. NULL 키/값

Java HashMap 은 null 키 1개 허용, null 값 여러 개 허용. C++ unordered_map 은 null 개념 없음 (포인터는 nullptr 가능).

BOJ 연습 문제

참고

• 해시 집합과 맵
• 트리 집합과 맵