프로그래밍

집합

같은 값을 두 번 저장하지 않는 자료형입니다.
교집합과 합집합을 연산자 하나로 구합니다.

학습 목표

  1. 집합을 만들고, 리스트에서 중복된 값을 제거할 수 있다.
  2. 리스트 · 딕셔너리 · 집합을 값을 꺼내는 방법으로 구별할 수 있다.
  3. 교집합 · 합집합 · 차집합을 연산자로 구할 수 있다.
  4. 집합에 순서가 없다는 것을 알고, 필요할 때 정렬해 순회할 수 있다.
  5. 「값이 있는지 묻는 일」에 집합이 유리한 이유와 그 대가를 설명할 수 있다.

중복된 값 제거하기

리스트로도 됩니다. 손이 많이 갈 뿐입니다.

투표 결과에서 어떤 것이 나왔는지만 알고 싶습니다. 몇 표인지는 지금 필요하지 않습니다.

votes = ["사과", "포도", "사과", "바나나", "사과", "포도"]

# 리스트로 「어떤 것이 나왔나」를 구하려면 순회하며 이미 추가했는지 직접 확인해야 한다
kinds = []
for fruit in votes:
    if fruit not in kinds:
        kinds.append(fruit)

print(kinds)        # ['사과', '포도', '바나나']
print(len(kinds))   # 3

if fruit not in kinds로 이미 추가했는지 매번 확인해야 합니다. 이 조건을 빠뜨리면 같은 값이 나올 때마다 다시 추가됩니다.

중복된 값은 「자동으로」 하나만 남는다 사과 포도 사과 바나나 사과 포도 리스트 — 나온 순서 그대로 요소 여섯 개 set() 사과 포도 바나나 집합 — 중복 없이 남은 요소 세 개 
votes = ["사과", "포도", "사과", "바나나", "사과", "포도"]

kinds = set(votes)      # 중복된 값은 자동으로 하나만 남는다
print(len(kinds))       # 3

fruits = {"사과", "포도", "바나나"}     # 중괄호로 직접 만들 수도 있다
print("사과" in fruits)                 # True

empty = set()           # 빈 「집합」은 set()이다
print(type(empty))      # <class 'set'>
print(type({}))         # <class 'dict'>   빈 중괄호는 「딕셔너리」다

집합(set)

같은 값을 두 번 저장하지 않고, 인덱스도 없는 자료형입니다. 리스트가 「무엇이 몇 번째에 몇 개 있는가」를 저장한다면, 집합은 「무엇이 들어 있는가」만 저장합니다.

빈 중괄호는 집합이 아닙니다

{}는 빈 딕셔너리입니다. 빈 집합은 set()으로 만들어야 합니다. 집합과 딕셔너리가 같은 중괄호를 쓰는데, 빈 중괄호는 딕셔너리로 정해져 있기 때문입니다.

스스로 확인

set("바나나")는 무엇이 될까요? 문자열의 글자 하나하나가 요소가 된다는 점에 주의해 보세요.

셋을 나란히 놓으면

무엇으로 꺼내는가가 셋을 구분합니다.

리스트 · 딕셔너리 · 집합은 여러 값을 저장한다는 점이 같습니다. 다른 것은 값을 꺼내는 방법입니다.

무엇으로 꺼내는가가 셋을 구분한다 리스트 인덱스로 [0] 90 [1] 85 [2] 72 순서가 의미를 갖는다 딕셔너리 키로 A 90 B 85 C 72 키가 값에 붙는다 집합 꺼낼 기준이 없다 90 85 72 있는지만 묻는다
리스트 딕셔너리 집합
만드는 법 [90, 85] {"A": 90} {90, 85}
하나 골라 꺼내기 a[0] d["A"] 없다(인덱스 · 키가 없다)
중복된 값 된다 키는 안 된다 안 된다
순서 인덱스 순서 넣은 순서(파이썬 3.7부터) 없다
잘하는 것 순서대로 다루기 키로 찾기 중복 제거 · 있는지 묻기 
fruits = {"사과", "포도", "바나나"}

# print(fruits[0])      # TypeError. 인덱스가 없다
fruits.add("귤")         # 추가하고
fruits.discard("포도")   # 삭제한다. 없는 값을 삭제해도 오류가 나지 않는다
print(len(fruits))      # 3

for f in sorted(fruits):    # 순서가 필요하면 정렬해서 순회한다
    print(f)                # 귤 / 바나나 / 사과

순서가 없다는 것

집합에는 인덱스가 없습니다. s[0]은 오류입니다. 순회할 수는 있지만 요소가 나오는 순서에 기대면 안 됩니다. 순서가 필요하면 sorted로 정렬해서 순회합니다.

스스로 확인

「학생마다 좋아하는 과일」을 저장한다면 셋 중 무엇이 알맞을까요? 「반에서 나온 과일 종류」라면요?

교집합 · 합집합 · 차집합

리스트에는 없는, 집합끼리의 연산입니다.

집합끼리는 연산자 하나로 교집합 · 합집합 · 차집합을 구할 수 있습니다.

교집합 · 합집합 · 차집합 a & b a b 양쪽에 다 있는 것 [3, 4] a | b a b 어느 쪽에든 있는 것 [1, 2, 3, 4, 5] a - b a b a에만 있는 것 [1, 2] b - a a b b에만 있는 것 [5] 
a = {1, 2, 3, 4}
b = {3, 4, 5}

print(sorted(a & b))    # [3, 4]           양쪽에 다 있는 것
print(sorted(a | b))    # [1, 2, 3, 4, 5]  어느 쪽에든 있는 것
print(sorted(a - b))    # [1, 2]           a에만 있는 것
print(sorted(b - a))    # [5]              b에만 있는 것
연산자 이름 구하는 것
a & b 교집합 양쪽에 다 있는 것
a | b 합집합 어느 쪽에든 있는 것
a - b 차집합 a에는 있고 b에는 없는 것

빼기는 방향이 있습니다

a - b와 b - a는 다릅니다. &와 |는 양쪽을 바꿔도 같지만 -는 어느 쪽에서 빼는지가 결과를 바꿉니다.

두 반의 명단으로 해 보면 뜻이 분명해집니다.

두 모임을 겹쳐 보면 답이 나온다 수학 미술 학생 A 학생 B 학생 C 학생 D 학생 E C·D가 &, 다섯 모두가 |, A·B가 - 
math_class = {"학생 A", "학생 B", "학생 C", "학생 D"}
art_class = {"학생 C", "학생 D", "학생 E"}

print(sorted(math_class & art_class))    # ['학생 C', '학생 D']   둘 다 듣는다
print(sorted(math_class - art_class))    # ['학생 A', '학생 B']   수학만 듣는다
print(len(math_class | art_class))       # 5                     모두 몇 명인가

「둘 다 듣는 학생」은 &, 「수학만 듣는 학생」은 -, 「모두 몇 명인가」는 |로 구한 합집합의 요소 개수입니다. 리스트로 구하려면 셋 모두 반복문을 따로 작성해야 합니다.

스스로 확인

「미술만 듣는 학생」은 어떻게 구할까요? math_class - art_class와 무엇이 다를까요?

있는지 묻는 일

집합을 고르는 또 하나의 이유입니다.

in은 리스트에도 쓸 수 있습니다. 다만 값을 찾는 방식이 다릅니다.

「있느냐」를 묻는 방법이 다르다 리스트 0 아니다 1 아니다 2 아니다 3 아니다 4 아니다 5 아니다 6 찾았다 앞에서부터 「하나씩」 비교한다 집합 6 값으로 계산 여기 있다 요소가 많아져도 「비교 횟수」가 거의 늘지 않는다 
# 값이 있는지 「묻기만」 한다면 집합이 훨씬 빠르다
numbers = list(range(1000000))
checked = set(numbers)

print(999999 in numbers)    # True   리스트는 앞에서부터 하나씩 비교한다
print(999999 in checked)    # True   집합은 저장 위치를 계산해 곧바로 찾아간다

요소가 많아져도 거의 느려지지 않습니다

리스트의 in은 앞에서부터 하나씩 비교합니다. 값이 백만 개면 최악의 경우 백만 번 비교합니다. 집합은 값으로 저장 위치를 계산해 곧바로 찾아갑니다. 그래서 요소가 많아져도 비교 횟수가 거의 늘지 않습니다.

더 알아보기

값으로 저장 위치를 계산하는 이런 구조를 해시 테이블(hash table)이라고 하고, 파이썬의 집합도 안에서 이 방식을 씁니다. 탐색 시뮬레이터의 「해시 테이블」 탭에서 값을 삽입하고 탐색해 보면, 값의 일의 자리로 칸 번호를 계산해 그 칸으로 곧바로 가는 모습과 두 값의 칸이 겹칠 때 벌어지는 일을 볼 수 있습니다.

그렇다고 늘 집합이 나은 것은 아닙니다

집합에는 순서가 없고 같은 값을 두 번 저장하지 않습니다. 인덱스로 꺼내야 하거나 같은 값을 여러 번 저장해야 한다면 리스트를 써야 합니다. 「값이 있는지 묻는 일」이 많다면 집합을 고를 이유가 됩니다.

이 강의노트에서 본 것을 모으면 두 줄을 입력받아 교집합과 합집합을 출력하는 프로그램이 됩니다.

# 두 줄을 입력받아 각각 집합으로 저장한다
a = set(map(int, input().split()))
b = set(map(int, input().split()))

print(*sorted(a & b))       # 교집합
print(*sorted(a | b))       # 합집합

# 입력
# 1 2 3 4 3
# 3 4 5
# 출력
# 3 4
# 1 2 3 4 5

print(*sorted(...))의 *는 리스트를 풀어 요소를 하나씩 인자로 전달하라는 뜻입니다. 덕분에 [3, 4]가 아니라 3 4로 출력됩니다.

스스로 확인

값 백만 개에서 「있는지」를 천 번 물어야 합니다. 리스트와 집합 중 무엇을 고르고, 그 이유는 무엇일까요?

핵심 정리

저장하는 것은 「무엇이 들어 있는가」뿐

집합은 같은 값을 두 번 저장하지 않고 인덱스도 없다. set(리스트) 한 줄이면 중복된 값이 자동으로 제거된다.

빈 중괄호는 딕셔너리다

{}는 빈 딕셔너리이고 빈 집합은 set()이다. 집합과 딕셔너리가 중괄호를 함께 쓰는데, 빈 중괄호는 딕셔너리로 정해져 있다.

순서가 없다

s[0]은 오류다. 순회할 수는 있지만 요소가 나오는 순서에 기대면 안 된다. 순서가 필요하면 sorted로 정렬해 순회한다.

연산자 셋이 반복문을 대신한다

&는 양쪽에 다 있는 것, |는 어느 쪽에든 있는 것, -는 앞쪽에만 있는 것. -는 방향이 있다.

값이 있는지 묻는 일에 유리하다

리스트의 in은 하나씩 비교하지만 집합은 값으로 저장 위치를 계산해 곧바로 찾아간다. 다만 집합에는 순서가 없으므로, 인덱스로 꺼내야 하면 리스트를 쓴다.

확인 퀴즈

배운 내용을 확인해 봅시다.

1. type({})의 결과는?

2. a = {1, 2, 3}, b = {3, 4}일 때 a - b는?

3. 다음 중 집합을 고를 이유가 되지 않는 것은?