set이란 무엇이며, 어떤 문제를 해결하나요?

Question

Accepted Answer

**set(집합)**은 **고유한(unique)** 원소들의 순서 없는 컬렉션입니다. 그 핵심 능력은 "X가 여기 있는가?"를 **평균 O(1)**에 답하는 것이며, 중복을 자동으로 거부합니다.

## 예시

```python
seen = set()
seen.add('a')
seen.add('a')          # 무시됨 — 이미 존재함
print(len(seen))       # 1
'a' in seen            # 평균 O(1) 멤버십 테스트

# 집합 대수
a = {1, 2, 3}
b = {2, 3, 4}
a & b                  # 교집합 -> {2, 3}
a | b                  # 합집합 -> {1, 2, 3, 4}
a - b                  # 차집합 -> {1}
```

대부분의 set은 **hash set**(key만 저장하는 hash table)으로 구현되므로:

| 연산 | 평균 |
|---|---|
| add | O(1) |
| remove | O(1) |
| 멤버십 (`in`) | O(1) |

## 일반적인 용도

- **중복 제거** — 리스트에서 반복을 한 줄로 제거함.
- **빠른 멤버십** — "이전에 본 적 있는가?"
- **관계** — 그룹 간 교집합/합집합/차집합.

## 왜 중요한가

set은 "고유성"과 "멤버십"을 간단하고 빠르게 만들어, 리스트에 대한 느린 중첩 루프를 대체합니다.

중복이나 방문한 노드를 탐지하는 흔한 면접 기법은 몇 개의 set 연산으로 압축됩니다.