본 프로젝트는 여러분들이 고등학교 수학에서 가장 먼저 배우는 집합에 관한 것이다. 집합에 대한 정보는 구글 이나 네이버의 검색을 통해 충분을 얻을 수 있다. Wikipedia에도 자세한 설명이 있다. 우리가 작성하길 원하는 프로그램은 정수형 집합 두 개를 입력 받고 입력 받은 두 개의 집합을 이용하여 합집합, 교집합, 차집합 연산을 수행하고 그 결과를 출력하는 것이다. 이 때 중요한 것은 집합의 원소는 중복될 수 없다 는 것이다. 여러분은 전체 프로그램 코드를 작성하지 않고, 주어진 프로그램을 완성한다. 가정 먼저 알아야할 것은 집합을 위한 변수에 관한 것이다. 집합의 최대 크기는 MAX_SET_SIZE로 정의되고, 입력받을 집합 두 개를 각각 setA, setB라 하자. 그리고 합집합, 교집합, 차집합의 결과를 저장하기 위한 변수를 setC로 정의한다. 그리고 sizeA, sizeB, sizeC는 각 집합의 크기이다.
#define MAX_SET_SIZE 10
#define HAVE_ELEMENT 1
#define DO_NOT_HAVE_ELEMENT 0
int setA[MAX_SET_SIZE];
int setB[MAX_SET_SIZE];
int setC[MAX_SET_SIZE*2];
int sizeA;
int sizeB;
int sizeC;
그리고 필요한 함수와 각각의 기능에 대한 설명은 아래와 같다. 다음의 단계로 프로젝트를 수행한다.
단계1: hasElement는 이미 주어졌고 printSet, addOneElement는 이전의 문제에서 정의한 함수를 그대로 사용한다. printSet, addOneElement를 사용하여 프로그램을 실행시켜보자.
int hasElement(int set[], int size, int element); - 이 함수는 집합 set에 정수 원소 element가 포함되어 있는지 여부를 검사하는 함수이다. 만약 set에 element가 포함되어 있으면HAVE_ELEMENT를 리턴하고, 포함되어 있지 않으면 DO_NOT_HAVE_ELEMENT를 리턴한다. DO_NOT_HAVE_ELEMENT와 HAVE_ELEMENT는 위에 정의되어 있다.
void printSet(int set[], int size); - 이 함수는 주어진 집합을 집합의 형식에 맞게 출력하는 함수이다. 집합의 원소가 1,2,3 이라면 출력은 {1, 2, 3}으로 한다.
int addOneElement(int set[], int size, int element); - set에 element가 없으면 이를 추가하고, 이미 있으면 redundant(혹은 중복입력)라는 메시지를 출력한다. 증가된 혹은 유지된 set의 크기를 반환한다.
단계2: 이 프로젝트의 과제는 setUnion, setIntersection, setComplement를 작성하는 것이다.
int setUnion(int set1[], int size1, int set2[], int size2, int setResult[]); - 이 함수는 주어진 집합 set1과 set2의 합집합을 구하는 것이고, 결과는 setResult이라는 배열에 저장된 다. 그리고 합집합의 크기가 리턴된다. size1과 size2는 각각 set1과 set2 집합의 크기를 의미한다.
int setIntersecton(int set1[], int size1, int set2[], int size2, int setResult[]); - 이 함수는 주어진 집합 set1과 set2의 교집합을 구하는 것이고, 결과는 setResult이라는 배열에 저장된 다. 그리고 교집합의 크기가 리턴된다. size1과 size2는 각각 set1과 set2 집합의 크기를 의미한다.
int setComplements(int set1[], int size1, int set2[], int size2, int setResult[]); - 이 함수는 주어진 집합 set1과 set2의 차집합을 (set1-set2) 구하는 것이고, 결과는 setResult이라는 배 열에 저장된다. 그리고 차집합의 크기가 리턴된다. size1과 size2는 각각 set1과 set2 집합의 크기를 의 미한다.
main 함수와 hasElement, printSet 함수는 이미 주어진다. 합/교/차집합 연산을 구현하라.
뼈대코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
#include <stdio.h>
#include <stdlib.h>
#define MAX_SET_SIZE 10
#define HAVE_ELEMENT 1
#define DO_NOT_HAVE_ELEMENT 0
int hasElement(int set[], int size, int element);
int setUnion(int set1[], int size1, int set2[], int size2, int setResult[]);
int setIntersecton(int set1[], int size1, int set2[], int size2, int setResult[]);
int setComplements(int set1[], int size1, int set2[], int size2, int setResult[]);
void printSet(int set[], int size);
int addOneElement(int set[], int size, int element);
int main(int argc, char *argv[])
{
int i;
int setA[MAX_SET_SIZE];
int setB[MAX_SET_SIZE];
int setC[MAX_SET_SIZE*2];
int sizeA;
int sizeB;
int sizeC;
printf("Enter the size of Set A:");
scanf("%d",&sizeA);
i = 0;
while( i < sizeA )
{
printf("Enter the number for Set A (%d/%d):", i+1,sizeA );
scanf( "%d", &setA[i] );
i = addOneElement(setA, i, setA[i]);
}
printf("Enter the size of Set B:");
scanf("%d",&sizeB);
i=0;
while( i < sizeB )
{
printf("Enter the number for Set B (%d/%d):", i+1, sizeB );
scanf( "%d", &setB[i] );
i = addOneElement(setB, i, setB[i]);
}
printf("Set A: ");
printSet( setA, sizeA );
printf("Set B: ");
printSet( setB, sizeB );
sizeC = setUnion( setA, sizeA, setB, sizeB, setC ); // Union, setC is the result set
printf("Union of setA and setB: ");
printSet( setC, sizeC );
sizeC = setIntersecton( setA, sizeA, setB, sizeB, setC ); //Intersection, setC is the result set
printf("Intersection of setA and setB: ");
printSet( setC, sizeC );
sizeC = setComplements( setA, sizeA, setB, sizeB, setC ); //Complements, setC is the result set
printf("Set-theoretic difference of setA and setB (setA - setB): ");
printSet( setC, sizeC );
return 0;
}
// If the set has the element, returns 1;
// else return 0;
int hasElement(int set[], int size, int element)
{
int i = 0;
for( i = 0; i < size; i++ )
if( set[i] == element )
return HAVE_ELEMENT; // we found it!
return DO_NOT_HAVE_ELEMENT;
}
// 원소를 집합에 추가. 이미 존재하면 추가하지 않고 redundant라고 출력한다. 현재의 집합 크기를 반환한다.
int addOneElement(int set[], int size, int element)
{
}
void printSet(int set[], int size)
{
}
int setUnion(int set1[], int size1, int set2[], int size2, int setResult[])
{
// 구현 필요
}
int setIntersecton(int set1[], int size1, int set2[], int size2, int setResult[])
{
// 구현 필요
}
int setComplements(int set1[], int size1, int set2[], int size2, int setResult[])
{
// 구현 필요
}
|
cs |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
#include <stdio.h>
#include <stdlib.h>
#define _CRT_SECURE_NO_WARNINGS
#define MAX_SET_SIZE 10
#define HAVE_ELEMENT 1
#define DO_NOT_HAVE_ELEMENT 0
int hasElement(int set[], int size, int element);
int setUnion(int set1[], int size1, int set2[], int size2, int setResult[]);
int setIntersecton(int set1[], int size1, int set2[], int size2, int setResult[]);
int setComplements(int set1[], int size1, int set2[], int size2, int setResult[]);
void printSet(int set[], int size);
int addOneElement(int set[], int size, int element);
int main(int argc, char* argv[])
{
int i;
int setA[MAX_SET_SIZE];
int setB[MAX_SET_SIZE];
int setC[MAX_SET_SIZE * 2];
int sizeA;
int sizeB;
int sizeC;
printf("Enter the size of Set A:");
scanf_s("%d", &sizeA);
i = 0;
while (i < sizeA)
{
printf("Enter the number for Set A (%d/%d):", i + 1, sizeA);
scanf_s("%d", &setA[i]);
i = addOneElement(setA, i, setA[i]);
}
printf("Enter the size of Set B:");
scanf_s("%d", &sizeB);
i = 0;
while (i < sizeB)
{
printf("Enter the number for Set B (%d/%d):", i + 1, sizeB);
scanf_s("%d", &setB[i]);
i = addOneElement(setB, i, setB[i]);
}
printf("Set A: ");
printSet(setA, sizeA);
printf("Set B: ");
printSet(setB, sizeB);
sizeC = setUnion(setA, sizeA, setB, sizeB, setC); // Union, setC is the result set
printf("Union of setA and setB: ");
printSet(setC, sizeC);
sizeC = setIntersecton(setA, sizeA, setB, sizeB, setC); //Intersection, setC is the result set
printf("Intersection of setA and setB: ");
printSet(setC, sizeC);
sizeC = setComplements(setA, sizeA, setB, sizeB, setC); //Complements, setC is the result set
printf("Set-theoretic difference of setA and setB (setA - setB): ");
printSet(setC, sizeC);
return 0;
}
// If the set has the element, returns 1;
// else return 0;
int hasElement(int set[], int size, int element)
{
int i;
for (i = 0; i < size; i++)
if (set[i] == element)//element==set[i]
return HAVE_ELEMENT; // we found it!
return DO_NOT_HAVE_ELEMENT;
}
// 원소를 집합에 추가. 이미 존재하면 추가하지 않고 redundant라고 출력한다. 현재의 집합 크기를 반환한다.
int addOneElement(int set[], int size, int element)
{
if (hasElement(set, size, element) == HAVE_ELEMENT) {
printf("It is redundant.Please retry.\n");
}
else {
set[size] = element;
size++;
}
return size;
}
void printSet(int set[], int size)
{
printf("{");
for (int i = 0; i < size; i++) {
printf("%d", set[i]);
if (i != size - 1)
printf(",");
}
printf("}\n");
}
int setUnion(int set1[], int size1, int set2[], int size2, int setResult[])
{
int j = 0;
for (int i = 0; i < size1; i++) {
setResult[j] = set1[i];
j++;
}
for (int i = 0; i < size2; i++)
if (hasElement(set1, size1, set2[i]) == DO_NOT_HAVE_ELEMENT) {
setResult[j] = set2[i];
j++;
}
return j;
}
int setIntersecton(int set1[], int size1, int set2[], int size2, int setResult[])
{
int j = 0;
for (int i = 0; i < size2; i++)
if (hasElement(set1, size1, set2[i]) == HAVE_ELEMENT) {
setResult[j]=set2[i];
j++;
}
return j;
}
int setComplements(int set1[], int size1, int set2[], int size2, int setResult[])
{
int j = 0;
for (int i = 0; i < size1; i++)
if (hasElement(set2, size2, set1[i]) == DO_NOT_HAVE_ELEMENT) {
setResult[j] = set1[i];
j++;
}
return j;
}
|
cs |
우선 이 문제가 어려워서 구글링으로 집합 코드를 찾아보다가 이 문제에 대해 다룬 블로그를 찾았다.
[C] 합집합, 교집합, 차집합 (tistory.com)
[C] 합집합, 교집합, 차집합
#include #include #define MAX_SET_SIZE 10 #define HAVE_ELEMENT 1 #define DO_NOT_HAVE_ELEMENT 0 int hasElement(int set[], int size, int element); int setUnion(int set1[], int size1, int set2[], int size2, int setResult[]); int setIntersecton(int set1[], int
devyul.tistory.com
여길 참고해도 좋고
<풀이>
먼저 addOneElement와 printSet은 지난 시간에 썻던 함수를 사용한다
다만 지난번엔 4를 무조건적으로 추가했는데 이제는 입력값을 추가하므로 기존 코드 set[size] = 4;에서 set[size] = element;로 고쳐준다.
|
1
2
3
4
5
6
7
8
9
10
11
|
int addOneElement(int set[], int size, int element)
{
if (hasElement(set, size, element) == HAVE_ELEMENT) {
printf("It is redundant.Please retry.\n");
}
else {
set[size] = element;
size++;
}
return size;
}
|
cs |
교수님은 별 말 없으셨지만 깐깐한 교수님은 백퍼 교집합,차집합,합집합 함수를 hasElement를 사용하여 나타내라 할것이 분명하니 최대한 사용해주자
다음으로 가서,교집합 먼저 완성해줄것이다.그 이유는 그게 제일 쉬우니까.
교집합은 a집합과 b집합의 공통된 것만 집합c에 넣어주면 된다(편의상 main의 변수명으로 작성)
지난시간의 isSetEqual 집합의 같고다름 판별 함수를 참고해주자
집합 a와 집합 b의 [0]에서부터 [size-1]까지를 비교해준다 반복문을 사용하면 편하다.
매개변수에 유의하자.set1이랑 set2가 햇갈린다. 이런건 그림그려보며 실행해보면 쉽게 답나온다.
대충 집합b의 [0]이랑 집합 a[0]부터 a[size-1]까지 비교해주고 집합b의 [1]이랑 집합 a[0]부터 a[size-1]까지 비교해주고
대충 b가 0일때 a 0부터 끝까지+b가 1일때 a 0부터 끝까지+....+ b가 끝일때 a 0부터 끝까지 이런 느낌이다
그럼 hasElement는 a[0]일때 b[0]이랑 같은가? a[1]일때 b[0]이랑 같은가? a[2]일때 b[0]이랑 같은가? a[3]일때 b[0]이랑 같은가? 라는 느낌의 함수가 되겠지
둘이 같지않으면 DO_NOT_HAVE_ELEMENT를 반환하고 같으면 HAVE_ELEMENT를 반환하겠지
만약에 hasElement를 실행하다 a[3]일때 b[0]이 같아서 HAVE_ELEMENT를 반환한다 해보자.
그 같은 값이 교집합의 원소 중 하나가 되겠으니 그 값(b[0]을) 집합 c에 넣어주면 된다.그리고 인덱스를 계산해주고 인덱스를 리턴해준다.
다음이 차집합이다.
차집합은 처음에 접근을 잘못했다.
hasElement함수로 집합 a와 교집합을 비교해서 공통된 원소가 없다고 뜨는(반환값이 DO_NOT_HAVE_ELEMENT인) 아이들을 집합 c에 넣으면 될거라고 생각했는데 생각해보니 교집합의 원소를 특정 배열에 넣을 수가 없어서 (배열(집합) c는 함수마다 바뀌므로) 고민을 참 많이 했다. 스스로 생각을 해보고 싶은데 답이 안나오니 힌트라도 얻으려고 구글링을 해보고 있었다. 그러던 도중에 영감을 받았다.
나는 차집합=집합a-교집합 이라 생각했는데 집합 a-집합 b도 차집합이 될수 있었다.
그렇게 교집합 함수를 좀 변형해서 작성해줬다
이번에도 인덱스가 했갈렸다. 그래서 a와 b에 대충 값을 넣고 써봤다.
hasElement로 집합b와 집합 a의 원소를 비교해줬다. b[0]이랑 a[0], b[0]이랑 a[1], b[0]이랑 a[2]....
둘이 같지않으면 DO_NOT_HAVE_ELEMENT를 반환하고 같으면 HAVE_ELEMENT를 반환하겠지
정확히 말하자면 같으면 HAVE_ELEMENT를 반환하고 뒤에건 실행이 안된다.
무튼 그래가지고 사진처럼 같지않다 반환하면 집합 c에 넣어주면 된다.
드디어 마지막으로 합집합이다
합집합을 어떻게 표현할지 고민을 참 많이 했다.
a 차집합+교집합+b 차집합=a 차집합+b=a+b 차집합=a+b-교집합
근데 a+b차집합으로 하기로 했다
먼저 a의 원소들을 전부다 c에 넣어준다 그리고 setComplements을 이용하여 b차집합을 구해서 넣어준다
교집합과 차집합을 하면 쉽다
이거 고민하는데 거의 4시간 쓴듯