[자료구조 09] 집합(set), 중복 없는 모음

집합(set, 중복 없는 모음)은 같은 값을 두 번 담지 않는 자료구조입니다. 순서가 없는 대신, 어떤 값이 그 안에 들어 있는지를 평균 O(1)로 매우 빠르게 확인합니다. 딕셔너리에서 값을 떼어 내고 키만 남긴 형태라고 생각하면 이해가 쉽습니다. 중복을 없애거나, 두 모음의 공통과 전체와 차이를 구하거나, 어떤 값이 있는지를 빠르게 물어야 할 때 집합이 가장 알맞은 그릇입니다. 이번 편에서는 집합을 만들고, 연산하고, 검사하는 방법을 하나씩 손으로 확인해 보겠습니다.

09.1 중복을 자동으로 없애는 집합

집합은 중괄호 { } 안에 값을 콤마로 나열해 만듭니다. 리스트와 달리 같은 값을 여러 번 넣어도 하나만 남습니다. 중복이 섞인 목록에서 유일한 값만 추리고 싶을 때 이 성질이 특히 유용합니다. 예를 들어 방문자 기록에서 서로 다른 사람이 몇 명인지 셀 때, 리스트를 집합으로 바꾸기만 하면 됩니다.

nums = [1, 2, 2, 3, 3, 3, 4]
print(sorted(set(nums)))

[1, 2, 3, 4]

set()에 리스트를 넣기만 하면 겹치는 값이 저절로 사라집니다. 다만 집합은 순서를 지키지 않으므로, 보기 좋게 늘어놓으려면 sorted()로 정렬해서 확인합니다. 여기서는 sorted()가 정렬된 리스트를 돌려주기 때문에 대괄호로 출력되었습니다. 값을 하나씩 담는 수고가 개수에 비례하므로, 목록 전체를 집합으로 만드는 일은 O(n)입니다.

09.2 교집합, 합집합, 차집합

집합끼리는 수학 시간에 배운 집합 연산을 기호 하나로 바로 할 수 있습니다. &(앰퍼샌드)는 교집합으로 둘 다에 있는 값, |(막대)는 합집합으로 하나라도 있는 값, -(빼기)는 차집합으로 앞 집합에만 있는 값을 구합니다.

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print(sorted(A & B)) # 교집합: 둘 다에 있는 것
print(sorted(A | B)) # 합집합: 하나라도 있는 것
print(sorted(A - B)) # 차집합: A에만 있는 것

[3, 4]
[1, 2, 3, 4, 5, 6]
[1, 2]

세 연산이 각각 한 줄에 끝났습니다. 교집합은 A와 B에 공통으로 든 3과 4, 합집합은 두 집합의 모든 값을 겹침 없이 모은 1부터 6, 차집합은 A에는 있지만 B에는 없는 1과 2입니다. 만약 이 작업을 리스트로 하려면 이중 반복문을 돌며 하나하나 비교해야 하지만, 집합은 기호 하나로 해결합니다. 각 연산은 대략 두 집합 중 작은 쪽 크기에 비례하는 수고가 듭니다.

09.3 있는지 빠르게 확인하고 공통 친구 찾기

집합의 진짜 강점은 멤버십 검사, 즉 어떤 값이 들어 있는지를 in으로 묻는 일이 평균 O(1)로 매우 빠르다는 점입니다. 리스트에서 in은 앞에서부터 하나씩 비교해 O(n)이 걸리지만, 집합은 해시로 자리를 바로 계산하므로 개수와 거의 무관하게 즉시 답합니다. 여기에 교집합까지 더하면 공통 친구 찾기 같은 문제가 한 줄로 풀립니다.

me = {"철수", "영희", "민수"}
you = {"영희", "민수", "지훈"}
print(sorted(me & you))
print("지훈" in you)

['민수', '영희']
True

두 사람의 친구 목록을 집합으로 만들고 교집합을 구하니 공통 친구 민수와 영희가 바로 나왔습니다. 팔로우가 겹치는 사람, 두 부서에 모두 속한 직원처럼 공통을 찾는 문제는 대부분 교집합 한 번이면 됩니다. 그리고 "지훈"이 you에 있는지 묻자 참(True)이 나왔는데, 이 확인이 회원 수가 백만 명이어도 거의 일정한 속도로 끝납니다.

09.4 리스트보다 수천 배 빠른 이유

말로만 빠르다고 하면 와닿지 않으니, 시간을 직접 재어 보겠습니다. 10만 개의 값을 리스트와 집합에 똑같이 담아 두고, 맨 끝에 있는 값을 1000번씩 찾아 걸린 시간을 비교합니다. 맨 끝 값은 리스트에게 가장 불리한, 끝까지 다 뒤져야 하는 경우입니다.

import timeit
N = 100000
big_list = list(range(N))
big_set = set(range(N))
target = N - 1 # 최악: 맨 끝에 있는 값
t1 = timeit.timeit(lambda: target in big_list, number=1000)
t2 = timeit.timeit(lambda: target in big_set, number=1000)
print(round(t1, 4), "초 (리스트)")
print(round(t2, 6), "초 (집합)")

0.8743 초 (리스트)
0.000083 초 (집합)

초 단위 수치는 컴퓨터 성능에 따라 달라지므로 위 값은 한 예시일 뿐이지만, 두 자료구조의 차이는 분명합니다. 이 실행에서는 집합이 리스트보다 약 1만 배 빨랐습니다. 리스트는 값을 앞에서부터 하나씩 다 비교하느라 O(n)이 걸리고, 집합은 해시로 자리를 바로 계산해 한 번에 찾으므로 평균 O(1)이기 때문입니다. "이 값이 있나?"를 자주 물어야 하는 프로그램이라면, 데이터를 리스트가 아니라 집합에 담는 것만으로 속도가 이렇게 달라집니다.

09.5 집합에는 순서가 없습니다

초보가 자주 놀라는 부분입니다. 딕셔너리는 파이썬 3.7 버전부터 값을 넣은 순서를 그대로 지키지만, 집합은 순서를 보장하지 않습니다. 그래서 집합을 그냥 출력하면 넣은 순서와 다르게 나올 수 있습니다.

dd = {}
dd["c"] = 1; dd["a"] = 2; dd["b"] = 3
print(list(dd.keys())) # 넣은 순서 유지
print({3, 1, 2}) # 순서 보장 안 됨

['c', 'a', 'b']
{1, 2, 3}

딕셔너리는 c, a, b를 넣은 순서 그대로 돌려주었지만, 집합 {3, 1, 2}는 출력하니 {1, 2, 3}으로 바뀌어 나왔습니다. 이것은 집합이 값을 해시로 흩어 담기 때문이며, 잘못된 것이 아닙니다. 그러므로 집합을 다룰 때는 순서에 기대지 말고, 순서가 필요하면 앞의 예제들처럼 sorted()로 정렬해서 쓰는 것이 안전합니다. 값의 순서 자체가 중요한 데이터라면 애초에 집합이 아니라 리스트에 담아야 합니다.

09.6 정리

집합은 중복 없는 값들의 모음이며, 멤버십 검사가 평균 O(1)로 빠릅니다. set()으로 리스트의 중복을 없애고, &와 |와 -로 교집합과 합집합과 차집합을 한 줄에 구하며, in으로 값의 존재를 즉시 확인합니다. 순서가 없다는 점만 기억하면, "겹치는 것 빼기", "공통 찾기", "빠르게 있는지 묻기"가 필요한 순간마다 집합이 가장 간결하고 빠른 선택이 됩니다. 정리하면, 중복을 없앨 때는 set(), 두 모음을 견줄 때는 집합 연산, 빠른 확인이 필요할 때는 in을 떠올리면 됩니다. 오늘 본 예제들을 직접 쳐 보며 리스트로 같은 일을 할 때와 얼마나 코드가 짧고 빨라지는지 비교해 보시기 바랍니다.