[정보올림피아드 대비]15. 집합의 성질을 이용한 문제

1.집합(Set)이란?

명확한 기준에 의해 분류되어 공통된 성질을 가지며 중복되지 않는 원소(Element,Member)의 모임

2. 집합의 표기 방식

1. 원소나열법 : 집합에 포함되는 원소들을 일일이 나열하는 방법

예) A = {1,2,3,4,5}

2. 조건제시법 : 집합에 포함되는 원소들이 공통적인 성질을 조건식으로 제시하는 방법

예) A = {x | 0< x <6, x는 정수}

3. 벤다이어 그램 : 집합과 원소의 포함관계를 그림으로 보여주는 방법

예)

집합의 개념 - 어떤 주어진 조건에 의해서 그  대상을 분명히 말할 수 있는 것들의 모임을 집합(Set)이라고 하며 집합을 이루는 대상 하나하나를 그 집합의 원소(elemnent)라고 한다.

3. 기수(Cardinality)

집합 A에 포함되는 원소의 개수

예) A = {1,2,3,4,5} 일때 |A| = 5

기수(Cardinality) - 집합 A에 포함되는 원소의 개수를 기수라 하며 원소의 개수에 따라 원소가 유한개인 유한집합(finite set) 과 무한집합(infinite set) 으로 분류할 수 있다. - 기수의 표현은 |A| 또는 n(A) 와 같이 표현한다.

4. 유한집합(Finite Set)

집합에 포함된 원소의 개수가 유한한 집합

예) A = {1,2,3,4,5}

5. 무한 집합(Infinite Set)

집합에 모함된 원소의 개수가 무한한 집합

예) A = {x | 0< x , x는 실수}

6.원소의 집합에 대한 포함관계

원소 a 가 집합 A의 원소이다

원소a 가 집합 A의 원소가 아니다.

7. 전체집합(Universal Set):U

논의 대상이 되는 원소 전체를 포함하는 집합

8. 공집합(Empty Set) : ∅ 또는 {}

원소를 하나도 포함하지 않는 집합으로 기수가 0인 집합

9.상등(Equal) : A = B

두 집합 A,B에 속하는 원소가 모두 동일할 때, " 두 집합 A와 B가 서로 같다" 또는 "두 집합 A와 B가 서로 상등이라" 라고 한다.

10. 부분집합(Subset) : A ⊆ B

집합 A의 모든 원소가 집합 B에 포함되는 경우

11. 진부분집합(Proper Subset) : A ⊂ B

집합 A의 모든 원소가 집합 B에 포함되지만 A와 B가 상등이 아닌 경우

부분집합이란 A의 모든 원소가 B에 포함되는 경우(자기 자신을 포함하는 경우도 포함이 된다.) 진부분집합이란 부분집합 중에서 자기 자신을 포함하지 않는 경우

12. 합집합(Union) : A ∪ B

집합 A,B가 있을 때 집합 A와 B에 모두 속하거나 둘 중 하나의 집합에 속하는 원소들로 만들어진 집합

13. 교집합(Intersection) : A ∩ B

집합 A,B가 있을 때 집합 A와 B에 모두 속한 원소들로 만들어진 집합

14. 서로소(Disjoint)

집합 A,B가 있을 때 집합 A와 B 사이에 공통으로 속하는 원소가 하나도 없는 경우

정수론에서는 1외에 공약수가 없는 수를 서로소라고 하는데

집합론에서는 A와 B 집합 사아에 공통으로 속하는 원소가 하나도 없는 경우를 서로소라고 한다.

 

문제)

A 재단에서는 노인과 장애인을 돌보는 자원봉사자를 모집한다. 이들은 A 재단에 등록되어 있는 노인과 장애인을 1:1로 돌보는 일을 한다. 노인을 담당하는 봉사자 65명,장애인을 담당하는 봉사자 55명을 모집하는데 이중 30명은 장애를 가지고 있는 노인을 돌본다. A 재단에서는 몇 명의 자원봉사자를 모집해야 하는가?

문제풀이)

|노인| = 65

|장애인| = 55

|노인 ∩ 장애인| = 30

|노인 U 장애인| = 65 + 55 - 30 = 90

 

문제)

컴퓨터과학과에서 졸업 프로젝트 수행을 위해 학생 150명을 대상으로 관심 분야 설문조사를 하였다. 설문조사 결과 네트워크 56명,보안 30명,게임 63명,네트워크와 보안 22명,네트워크와 게임 17명,보안과 게임9명,어느분야도 선택하지 않은 사람은 45명이었다. 세분야를 모두 선택한 학생은 몇명인가?

문제풀이)

|네트워크| = 56

|보안| = 30

|게임| = 63

|네트워크 ∩ 보안| = 22

|네트워크 ∩ 게임| = 17

|보안∩ 게임| = 9

|어느분야도 선택하지 않은 학생| = 45

따라서 한가지 이상을 선택한 학생 = 155 - 45 = 110

|네트워크 U 보안 U 게임| = 56 + 30 + 63 - 22 - 17 - 9 + |네트워크 ∩ 보안 ∩게임|=110

|네트워크 ∩ 보안 ∩ 게임| = 4

15. 차집합(Difference) : A - B

집합 A,B가 있을 때 A에는 속하지만 B에는 속하지 않는 원소로 구성되는 집합

16. 대칭차집합 : A ⊕ B

집합 A,B가 있을 때 A - B에 속하거나 B-A에 속하는 원소로 구성되는 집합

17. 여집합(Complement) 

전체집합 U에는 속하지만 집합 A에는 속하지 않는 원소들의 집합

18. 곱집합(Cartesian Product) : A * B

집합 A,B에 대하여 a ∈ A, b ∈ B 일때 순서쌍 (a,b)의 집합

19. 멱집합

• 하나의 집합에서 발생할 수 있는 모든 부분집합을 집합으로 구한것
• 공집합은 모든 집합의 부분집합이므로 멱집합의 원소는 공집합과 자신도 포함됨

집합의 개수 n개인 멱집합의 개수 : 2^n 

 

 

[역대기출문제]

https://docs.google.com/forms/d/e/1FAIpQLSeBrPR_syOkbYGOoir2nCN-r4olqYGPp52hLU8wyyioyAZkrw/viewform

16-1. 집합의 성질을 이용한 문제(초등부)

https://docs.google.com/forms/d/e/1FAIpQLScfvZDvXKLT6_UBFMAAk8Mzj7loHR16v_seNYsYkeeww9VxLw/viewform

16-2. 집합의 성질을 이용한 문제(중고등부)

 

자료 출처]

한빛미디어 - 컴퓨팅 사고력을 키우는 이산수학