셋(set)과 frozenset — 집합 연산과 중복 제거

🎯 이 강의에서 배우는 것

셋(set)은 해시 테이블 기반의 순서 없는 유일한 원소 모음입니다. 딕셔너리에서 값을 제거한 구조라고 생각할 수 있습니다. 핵심 강점은 두 가지: O(1) 멤버십 테스트와 수학적 집합 연산. 중복 제거와 공통 원소 찾기에서 리스트보다 압도적으로 효율적입니다.

🧱 셋 생성과 내부 구조

import sys

# 셋 생성
s1 = {1, 2, 3, 4, 5}         # 리터럴
s2 = set([1, 2, 2, 3, 3, 4]) # 이터러블 변환 — 중복 자동 제거
s3 = set("hello")             # {'h', 'e', 'l', 'o'} — 문자 셋

print(s2)   # {1, 2, 3, 4} (순서 비결정적)
print(s3)   # {'h', 'e', 'l', 'o'} (순서 비결정적)

# 빈 셋: {} 가 아닌 set() 사용!
empty_dict = {}    # 딕셔너리!
empty_set = set()  # 셋!
print(type(empty_dict))   # <class 'dict'>
print(type(empty_set))    # <class 'set'>

# 내부 구조: 딕셔너리에서 값 부분을 제거한 해시 테이블
# 원소 = 키. 값 없음.
# 따라서 원소는 해시 가능해야 함

print(sys.getsizeof(set()))         # 216 bytes (기본 용량)
print(sys.getsizeof({1, 2, 3}))    # 216 bytes (8개까지 같은 크기)
print(sys.getsizeof({1,2,3,4,5,6,7,8,9}))  # 480 bytes (리사이징)

# 순서 없음 — 인덱싱 불가
try:
    s1[0]   # TypeError!
except TypeError as e:
    print(e)

⚡ O(1) 멤버십 테스트 — 리스트 vs 셋

import timeit

# 대용량 데이터에서의 멤버십 테스트 성능 비교
data = list(range(1_000_000))
large_list = data
large_set = set(data)

# 리스트: O(n) — 처음부터 끝까지 선형 탐색
t_list = timeit.timeit(
    lambda: 999999 in large_list,
    number=1000
)

# 셋: O(1) — 해시 → 버킷 직접 접근
t_set = timeit.timeit(
    lambda: 999999 in large_set,
    number=1000
)

print(f"리스트 in: {t_list:.4f}초")
print(f"셋 in:     {t_set:.4f}초")
print(f"셋이 {t_list/t_set:.0f}배 빠름")

# 실전 활용: 자주 조회하는 데이터는 셋으로 변환
banned_users = ["user1", "user2", "user3"]  # 나쁜 예: 매번 O(n) 탐색
banned_set = set(banned_users)              # 좋은 예: O(1) 탐색

def is_banned(username):
    return username in banned_set   # O(1)

print(is_banned("user2"))   # True
print(is_banned("user4"))   # False

➕➖ 집합 연산 완전 정복

A = {1, 2, 3, 4, 5}
B = {3, 4, 5, 6, 7}

# 합집합 (union): A ∪ B
print(A | B)          # {1, 2, 3, 4, 5, 6, 7}
print(A.union(B))     # 동일

# 교집합 (intersection): A ∩ B
print(A & B)              # {3, 4, 5}
print(A.intersection(B))  # 동일

# 차집합 (difference): A - B = A에는 있지만 B에 없는 것
print(A - B)             # {1, 2}
print(A.difference(B))   # 동일
print(B - A)             # {6, 7}

# 대칭 차집합 (symmetric difference): A △ B = 한쪽에만 있는 것
print(A ^ B)                          # {1, 2, 6, 7}
print(A.symmetric_difference(B))      # 동일

# 부분집합 / 상위집합
C = {3, 4, 5}
print(C <= A)            # True (C는 A의 부분집합)
print(C.issubset(A))     # True
print(A >= C)            # True (A는 C의 상위집합)
print(A.issuperset(C))   # True
print(C < A)             # True (진부분집합 — C != A)
print(C <= C)            # True (자기 자신의 부분집합)
print(C < C)             # False (진부분집합 아님)

# 서로소 여부
D = {10, 20}
print(A.isdisjoint(D))   # True (공통 원소 없음)
print(A.isdisjoint(B))   # False (3,4,5 공통)

# 여러 집합 연산
S1, S2, S3 = {1,2,3}, {2,3,4}, {3,4,5}
print(S1 & S2 & S3)   # {3} — 세 집합의 교집합
print(S1 | S2 | S3)   # {1,2,3,4,5} — 세 집합의 합집합

🔧 셋 메서드와 인플레이스 연산

s = {1, 2, 3}

# 원소 추가
s.add(4)           # 원소 하나 추가
s.update([5, 6])   # 이터러블의 원소들 추가
print(s)   # {1, 2, 3, 4, 5, 6}

# 원소 제거
s.remove(6)         # 제거. 없으면 KeyError!
s.discard(99)       # 제거. 없어도 에러 없음 (더 안전)
popped = s.pop()    # 임의 원소 꺼내기 (순서 없으므로 어떤 것인지 보장 안 됨)

# 인플레이스 연산
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

A |= B    # A = A | B (합집합, 인플레이스)
print(A)  # {1, 2, 3, 4, 5, 6}

A = {1, 2, 3, 4}
A &= B    # A = A & B (교집합, 인플레이스)
print(A)  # {3, 4}

A = {1, 2, 3, 4}
A -= B    # A = A - B (차집합, 인플레이스)
print(A)  # {1, 2}

A = {1, 2, 3, 4}
A ^= B    # A = A ^ B (대칭 차집합, 인플레이스)
print(A)  # {1, 2, 5, 6}

🧊 frozenset — 불변 셋

# frozenset: 불변 → 해시 가능 → 딕셔너리 키, 셋 원소로 사용 가능
fs = frozenset([1, 2, 3, 4, 5])
print(type(fs))       # <class 'frozenset'>
print(hash(fs))       # 해시 가능!

try:
    fs.add(6)   # AttributeError! — frozenset은 수정 불가
except AttributeError as e:
    print(e)

# frozenset을 딕셔너리 키로 사용
graph = {
    frozenset({"A", "B"}): 1.5,    # A-B 간선, 가중치 1.5
    frozenset({"B", "C"}): 2.0,
    frozenset({"A", "C"}): 3.0,
}
print(graph[frozenset({"A", "B"})])   # 1.5

# 셋의 셋 (frozenset으로만 가능)
set_of_sets = {frozenset({1, 2}), frozenset({3, 4}), frozenset({1, 2})}
print(set_of_sets)   # {frozenset({1, 2}), frozenset({3, 4})} — 중복 제거

🛠️ 실전 패턴 — 중복 제거와 집합 연산

# 패턴 1: 단순 중복 제거 (순서 무관)
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
unique = list(set(data))
print(sorted(unique))   # [1, 2, 3, 4, 5, 6, 9]

# 패턴 2: 순서 보존 중복 제거
def unique_ordered(lst):
    return list(dict.fromkeys(lst))   # dict 키는 삽입 순서 유지

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(unique_ordered(data))   # [3, 1, 4, 5, 9, 2, 6]

# 패턴 3: 두 리스트의 공통 원소 (교집합)
list_a = ["Python", "Java", "Go"]
list_b = ["Python", "Rust", "Go"]
common = set(list_a) & set(list_b)
print(common)   # {'Python', 'Go'}

# 패턴 4: 한쪽에만 있는 것 (대칭 차집합)
yesterday = {"user1", "user2", "user3"}
today = {"user2", "user3", "user4"}
changed = yesterday ^ today
print(f"어제는 있었지만 오늘 없음: {yesterday - today}")
print(f"오늘 새로 나타남: {today - yesterday}")
print(f"변화 전체: {changed}")

# 패턴 5: 빠른 필터링 (대용량 데이터)
valid_codes = set(["CODE001", "CODE002", "CODE003", "CODE004"])

orders = [
    {"code": "CODE001", "amount": 50000},
    {"code": "INVALID", "amount": 30000},
    {"code": "CODE003", "amount": 20000},
]

valid_orders = [o for o in orders if o["code"] in valid_codes]  # O(1) per check
print(valid_orders)

⚠️ 자주 하는 실수

• 빈 셋을 {} 로 생성: {}는 빈 딕셔너리입니다. 빈 셋은 반드시 set()을 사용하세요.
• 셋 인덱싱 시도: 셋은 순서가 없어 s[0]이 불가능합니다. 특정 원소를 꺼내려면 리스트로 변환하거나 for 루프를 사용하세요.
• 리스트를 자주 조회하는 경우 set으로 전환 안 함: if x in my_list를 루프에서 반복하면 O(n²)가 됩니다. 한 번 my_set = set(my_list)로 변환하면 O(n)으로 줄어듭니다.

📝 정리 및 다음 강의 예고

• 셋은 해시 테이블 기반 — 중복 없음, 순서 없음, O(1) 멤버십 테스트.
• 집합 연산: | 합집합, & 교집합, - 차집합, ^ 대칭 차집합.
• frozenset: 불변 셋 — 해시 가능하여 딕셔너리 키, 셋의 원소로 사용 가능.
• 순서 보존 중복 제거는 dict.fromkeys(lst)가 파이썬다운 방법.

다음 강의: collections 모듈 — deque, Counter, defaultdict, OrderedDict, ChainMap의 원리와 언제 어떤 고급 자료구조를 쓸지 배웁니다.