Lesson 7 of 20

집합 — 순서도 중복도 없는 자루

무엇이 들었는지만 중요합니다

집합(set)은 서로 다른 것들의 모임입니다. 자루에 물건을 넣는다고 생각하세요. 자루를 흔들어도 내용물은 그대로고, 같은 사과를 두 번 넣어도 사과는 하나입니다.

🎒

순서 없음

{1,2,3} = {3,1,2}

1️⃣

중복 없음

{1,1,2} = {1,2}

❓

소속만 물음

있다 / 없다, 둘 중 하나

이 세 가지가 리스트와의 결정적 차이입니다. 리스트는 순서가 있고 중복도 되지만, 집합은 "이게 들어 있나?"라는 단 하나의 질문에 특화되어 있어요.

기호도 알아 둡시다. 3 ∈ A 는 "3은 A의 원소이다", 3 ∉ A 는 "원소가 아니다"라고 읽습니다.

High school순서도 중복도 없는 자루

집합은 무엇이 들었는지만 중요합니다.

{1, 2, 3} = {3, 1, 2} = {1, 1, 2, 3}

이 단순함이 힘입니다

버린 것	얻은 것
순서	비교가 쉬워진다
중복	"있다/없다" 만 따진다

따질 것이 줄어들면 다루기 쉬워진다

두 집합이 같다는 것

A = B ⟺ 서로가 서로의 부분집합

이게 실제 증명 방법입니다. "같다" 를 보이려면 양쪽 포함을 보이면 돼요.

보일 것	—
A ⊆ B	A 의 원소가 전부 B 에
B ⊆ A	반대로

"같다" 를 두 개의 쉬운 문제로 나눈다

비유 — 장바구니

물음	집합에서
"우유가 있나"	답한다 ✔
"우유가 몇 번째?"	뜻이 없다
"우유가 두 개?"	뜻이 없다

개수나 순서가 필요하면 다른 그릇을 써야 한다 — 다중집합·수열

집합은 '무엇이 들었는가'만 기억합니다.

Python Runs in your browser

# 파이썬의 집합은 중괄호 { } 로 씁니다
A = {3, 1, 2, 3, 1}         # 중복해서 써 봐도…
print("A =", A, "← 중복이 사라졌습니다")
print("{1,2,3} == {3,2,1} ?", {1, 2, 3} == {3, 2, 1}, "← 순서는 무시됩니다")
print()
print("3 ∈ A ?", 3 in A)
print("9 ∈ A ?", 9 in A)
print("원소 개수 |A| =", len(A))

🎮 자루에 직접 넣어 보세요

같은 원소를 두 번 넣어 보고, 순서를 바꿔 넣어 보세요. 몇 번을 넣어도 자루 안은 그대로라는 것이 집합의 성격입니다.

High school부분집합의 개수가 2ⁿ 인 이유

원소 n 개짜리 집합의 부분집합은 몇 개일까요?

답은 2ⁿ — 그리고 이유가 아름답다

이렇게 생각하면 됩니다

부분집합을 만들 때 원소마다 결정합니다.

각 원소	선택지
1번	넣는다 / 뺀다 — 2가지
2번	2가지
…	—

2 × 2 × … × 2 = 2ⁿ — 13강 곱의 법칙이다

비트로 보면 더 명확합니다

부분집합	비트
{}	000
{a}	001
{a,b}	011
{a,b,c}	111

부분집합과 n비트 수가 일대일 대응한다 — 10강의 전단사

n비트로 나타낼 수 있는 수가 2ⁿ 개니까 부분집합도 2ⁿ 개죠.

이 대응이 실용적입니다

쓰임	설명
비트마스크	집합을 정수 하나로 표현
부분집합 순회	`for i in range(1<<n)`
집합 연산	비트 연산으로 — 빠르다

추상적 개념이 효율적인 코드가 된다

15강에서 다시 만납니다

C(n,0) + C(n,1) + … + C(n,n) = 2ⁿ

"크기별로 세어 더한 것" 과 "전부 센 것" 이 같으니까요. 같은 것을 두 가지로 세는 것이 조합론의 기본 기술입니다.

집합을 적는 두 가지 방법

원소나열법 — A = {2, 4, 6, 8}. 원소가 적을 때.
조건제시법 — A = {x | x는 10 미만의 짝수}. | 는 "단, 이런 조건"이라고 읽습니다. 원소가 많거나 무한할 때.

조건제시법은 파이썬의 내포(comprehension) 문법과 모양이 똑같습니다. {x for x in range(10) if x % 2 == 0} — 수학 기호를 그대로 옮겨 놓았어요.

수학의 { x | 조건 } 이 파이썬에서는 { x for x in ... if 조건 } 입니다.

Python Runs in your browser

# 조건제시법 = 파이썬 집합 내포
짝수 = {x for x in range(1, 21) if x % 2 == 0}
세배수 = {x for x in range(1, 21) if x % 3 == 0}

print("짝수  =", sorted(짝수))
print("3의 배수 =", sorted(세배수))
print()
# 자주 쓰는 수의 집합들
print("공집합 ∅ =", set(), "· 원소 개수", len(set()))
print("|짝수| =", len(짝수), "  |3의 배수| =", len(세배수))

High school특별한 집합들

note 가 든 집합들을 왜 특별한지와 함께.

집합	기호	특별한 점
공집합	∅	모든 집합의 부분집합
전체집합	U	여집합의 기준
멱집합	P(A)	부분집합 전부의 집합

공집합이 모든 집합의 부분집합인 이유 — 3강의 공허한 참

왜 그런가

∅ ⊆ A 는 ∀x (x ∈ ∅ → x ∈ A) 입니다.

확인	—
∅ 에 원소가 없다	조건이 항상 거짓
3강	거짓 → 무엇 = 참 ✔

확인할 것이 없으므로 참이다 — 이상하지만 일관적이다

공집합과 {∅} 은 다릅니다

집합	원소 수
∅	0
{∅}	1 — 공집합이 하나 들었다

빈 상자와 빈 상자가 든 상자는 다르다

멱집합의 크기

\|A\|	\|P(A)\|
0	1 (∅ 하나)
3	8
n	2ⁿ

멱집합은 항상 원래보다 크다 — 무한집합에서도 그렇다

이 사실이 무한에도 크기가 여럿이라는 칸토어의 발견으로 이어집니다.

단순한 관찰에서 깊은 결론이 나온다

부분집합 — 통째로 들어 있나

A ⊆ B 는 "A의 모든 원소가 B에도 있다"는 뜻입니다. 5강의 기호로 쓰면 ∀x (x ∈ A → x ∈ B) 예요 — 한정기호와 조건명제가 여기서 만납니다.

재미있는 사실 둘.

공집합은 모든 집합의 부분집합입니다. 어길 원소가 없으니까요 (공허한 참!).
원소가 n개인 집합의 부분집합 개수는 2ⁿ개입니다. 각 원소마다 "넣는다/뺀다" 두 가지를 고르니까요 — 2강의 진리표와 똑같은 계산이에요.

부분집합 전체를 모은 것을 멱집합(power set)이라 합니다.

Python Runs in your browser

from itertools import combinations

A = {"사과", "바나나", "포도"}

# 모든 부분집합 (멱집합) 을 만들어 봅니다
부분집합들 = []
for k in range(len(A) + 1):
    for 조합 in combinations(sorted(A), k):
        부분집합들.append(set(조합))

for s in 부분집합들:
    print("  ", s if s else "∅")
print()
print(f"원소 {len(A)}개 → 부분집합 {len(부분집합들)}개 = 2^{len(A)} = {2**len(A)}")
print("{'사과'} ⊆ A ?", {"사과"} <= A)
print("∅ ⊆ A ?", set() <= A, "← 공집합은 언제나 부분집합")

High school꼭 기억하세요

7강의 정리와 실전 연결입니다.

집합은 "있다/없다" 만 따지는 그릇이다

기호 정리

기호	뜻	양쪽
∈	원소이다	원소 ∈ 집합
⊆	부분집합이다	집합 ⊆ 집합

헷갈리면 양쪽이 무엇인지 를 본다

a ∈ {a, b} 는 참이고 {a} ⊆ {a, b} 도 참인데 a ⊆ {a,b} 는 말이 안 됩니다.

5강과 만나는 곳

A ⊆ B 는 ∀x (x ∈ A → x ∈ B)

부품	어디서
∀	5강
→	3강
∈	7강

배운 것들이 한 식에서 만난다 — 이 강의가 쌓이는 방식이다

코드에서

a = {1, 2, 3}
b = {1, 2}
b <= a        # 부분집합? True
1 in a        # 원소? True

연산	속도
`in` (집합)	O(1) ✔
`in` (리스트)	O(n)

"있다/없다" 만 따지니 해시로 즉시 답한다 — /ds 13강

🤔 Check yourself

{1, 2, 2, 3, 1} 의 원소 개수는?

🤔 Check yourself

원소가 4개인 집합의 부분집합은 모두 몇 개일까요?

Answer 각 원소마다 넣는다/뺀다 두 가지를 고르므로 2⁴ = 16개입니다. 공집합과 자기 자신도 부분집합에 포함돼요. 진리표의 줄 수와 정확히 같은 계산입니다.

🤔 Check yourself

공집합 ∅ 에 대해 옳은 것은?

Answer "∅의 모든 원소가 A에 있다"는 어길 원소가 없으므로 언제나 참입니다 (공허한 참). 참고로 {∅}는 원소가 1개인 집합이라 ∅와 다릅니다.