07. 집합

07-1 집합

 

집합 (set)

• 명확한 조건을 만족하는 자료의 모임
• 집합 구성요소 : 원소 (element)
• 원소에는 순서가 없다.  
• 집합에 포함되는 원소는 서로 달라야 한다. (중복 X)   
• 집합은 집합을 원소로 가질 수 있다.  
• 원소 개수가 1개이거나 원소가 없어도 집합이다. 

집합 X의 원소가 1, 5이다. X = {1, 5}

자연수의 집합을 표현할 때 > N 사용  N = {1, 2, 3, 4...}

정수의 집합을 표현할 때 > Z 사용

a가 집합 X의 원소일 때 = a는 X에 포함된다.  = a는 X에 들어 있다.  = a는 X에 속한다.  a ∈ X 또는 X ∋ a

b가 집합 X의 원소가 아닐 때  = b는 X에 포함되지 않는다. b ∉ X 또는 X∌ b

두 집합 X, Y가 같은 원소로 구성될 때 = X와 Y는 서로 같다.  X = Y 또는 Y = X

같은 원소로 구성되지 않은 경우 = X와 Y는 서로 같지 않다.  X ≠ Y 또는 Y ≠ X

무한집합 Y : 원소의 개수가 무한한 집합                         n(Y) = ∞ 유한집합 X (원소 개수 n) : 원소의 개수가 유한한 집합   n(X) = n

공집합 (empty set) ∅ : 원소가 하나도 없는 집합

 

부분집합, 진부분집합

부분집합

• 집합 A의 모든 원소가 집합 B의 원소이면, A는 B의 부분집합(subset)이고, 'A는 B에 포함된다.'라고 말한다.  
• A와 B가 서로 같은 경우에도 A와 B는 서로 부분집합 관계가 된다. 

A는 B에 포함된다. A ⊂ B 또는 B ⊃ A

진부분집합 (proper subset)

• 집합 A의 모든 원소가 집합 B의 원소이면서 집합 A와 집합 B가 같지 않을 때 (A⊂B이고 A≠B), 
  'A는 B의 진부분집합이다' 라고 말한다. 

A는 B의 진부분집합이다.  A ⊊ B 또는 B ⊋ A

ex) A = {1, 3}, B = {1, 3, 5}인 경우 'A는 B의 부분집합이면서 진부분집합이다'라고 할 수 있지만,
A = {1, 3, 5}, B = {1, 3, 5}인 경우는 'A는 B의 부분집합이지만 진부분집합은 아니다'라고 한다. 

 

집합의 연산

1) 합집합

• 집합 A와 집합 B 가운데 적어도 한쪽에 속하는 원소의 집합
• A ∪ B

 

 

2) 교집합

• 집합 A, B 양쪽 모두에 속하는 원소의 집합 
• A ∩ B

 

 

3) 차집합

• 집합 A의 원소 가운데 집합 B의 원소를 제외한 원소의 집합 
• A-B

 

 

 

 

07-2 배열로 집합 만들기 

 

배열로 집합 만들기

• 모든 원소가 같은 자료형으로 구성된 집합은 배열로 표현할 수 있다. 
• 집합의 원소 개수 = 배열 요소 개수가 항상 같아야 한다. 
• 집합의 상태를 표현할 데이터 필요
• 집합을 표현하는 배열과 이 배열의 정보(집합 최대 크기, 집합의 원소 개수)를 담은 구조체를 함께 사용해야 한다. 

//int형 집합 IntSet(헤더)
#ifndef ___IntSet
#define ___IntSet

//int형 집합을 관리하는 구조체 
typedef struct {
  int max;  //집합 최대 크기
  int num;  //집합 원소 개수 : 0 ~ num-1
  int *set; //집합을 넣는 배열 포인터 (배열의 첫번째 요소에 대한 포인터)
} IntSet;

//집합 초기화
int Initialize(IntSet *s, int max);

//집합 s에 n이 들어 있는지 확인
int IsMember(const IntSet *s, int n);

//집합 s에 n 추가
void Add(IntSet *s, int n);

//집합 s에서 n 삭제
void Remove(IntSet *s, int n);

//집합 s에 넣을 수 있는 최대 원소 개수 반환
int Capacity(const IntSet *s);

//집합 s의 원소 개수
int Size(const IntSet *s);

//집합 s2를 s1에 대입
void Assign(IntSet *s1, const IntSet *2);

//집합 s1과 s2가 같은지 확인
int Equal(const IntSet *s1, const IntSet *s2);

//집합 s2와 s3의 합집합을 s1에 대입
IntSet *Union(IntSet *s1, const IntSet *s2, const IntSet *s3);

//집합 s2와 s3의 교집합을 s1에 대입
IntSet *Intersection(IntSet *s1, const IntSet *s2, const IntSet *s3);

//집합 s2에서 s3을 뺀 차집합을 s1에 대입
IntSet *Difference(IntSet *s1, const IntSet *s2, const IntSet *s3);

//집합 s의 모든 원소 출력
void Print(const IntSet *s);

//집합 s의 모든 원소 출력 (줄 바꿈 문자 포함)
void PrintLn(const IntSet *s);

//집합 종료
void Terminate(IntSet *s);

#endif

//Int형 집합 IntSet(소스)

#include <stdio.h>
#include <stdlib.h>
#include "IntSet.h"

//집합 초기화
int Initialize(IntSet *s, int max) {
    s->num = 0;
    if((s->set = calloc(max, sizeof(int))) == NULL) {
       s->max = 0; //배열 생성 실패
       return -1;
    }
    s->max = max;  //요소 최대 개수가 max개인 배열 본체 만들고 매개변수 max를 멤버 max에 복사 
    return 0;
}

//집합 s에 n이 들어 있는지 확인
int IsMember(const IntSet *s, int n) {
   int i;
   for(i=0; i<s->num; i++) 
      if(s->set[i] == n)
         return i;  //들어있음 (인덱스 반환)
   return -1;       //들어 있지 않음
}

//집합 s에 n 추가
void Add(IntSet *s, int n) {
   if(s->num < s->max && IsMember(s, n) == -1) //배열이 비어 있고 n이 들어 있지 않으면
      s->set[s->num++] = n;  //배열 끝에 n 추가
}

//집합 s에서 n 삭제 
void Remove(IntSet *s, int n) {
   int idx;
   if((idx = IsMember(s, n)) != -1) {  //집합에 n이 들어 있다면, IsMember 함수로 조사하고 반환값을 idx에 넣는다. 
      //num(요소 개수)을 1 감소하고 마지막에 있는 값을 비어있는 곳에 넣는다. 
      s->set[idx] = s->set[--s->num];  
   }
}

//집합 s에 넣을 수 있는 최대 원소 개수 반환
int Capacity(const IntSet *s) {
  return s->max;  //멤버 max 값을 반환한다. 
}

//집합 s의 원소 개수 반환
int Size(const IntSet *s) {
  return s->num;  //멤버 num 값을 반환한다. 
}

//집합 s2를 s1에 대입 (한 집합을 다른 집합으로 복사)
void Assign(IntSet *s1, const IntSet *s2) {  //복사원본 > s2, 복사할 대상 > s1
    int i;
    //복사 원본(s2)의 원소 개수(s2->num)가 복사할 대상의 집합 크기(s1->max)보다 큰 경우
    //복사할 대상의 집합 크기(s1->max)에 대한 원소만큼만 복사한다. 
    int n = (s->max < s->num) ? s1->max : s->num; //복사하는 원소의 개수
    for(i=0; i<n; i++) 
       s1->set[i] = s2->set[i];
    s1->num = n;
}

//집합 s1과 s2가 같은지 확인
int Equal(const IntSet *s1, const IntSet *s2) {
  int i, j;
  if(Size(s1 != Size(s2))  //같지 않을 때 
     return 0;
  //같을 때 
  for(i=0; i<s1->num; i++) {  //i 1씩 증가 
    for(j=0; j<s2->num; j++) 
       if(s1->set[i] == s2->set[j])  //같은 요소 찾으면 break로 빠져나온다. 
          break;
     if(j == s2->num) //만약 j가 s2요소의 개수와 같아지면 찾지 못했다는 뜻이므로 0을 리턴한다.
       return 0;
   }
   return 1;
}

//집합 s2와 s3의 합집합을 s1에 대입 (합집합) 
IntSet *Union(IntSet *s1, const IntSet *s2, const IntSet *s3) {
    int i;
    Assign(s1, s2); //s2를 s1에 복사
    for(i=0; i<s3->num; i++)  //s3의 모든 원소를 하나씩 s1에 추가한다. 
       Add(s1, s3->set[i]);
    return s1;  
}

//집합 s2와 s3의 교집합을 s1에 대입
IntSet *Intersection(IntSet *s1, const IntSet *s2, const IntSet *s3) {
  int i, j;
  s1->num = 0; //s1을 공집합으로 만든다.
  for(i=0; i<s2->num; i++)  //s2요소를 스캔하면서 s2의 원소가 s3에 있다면 
    for(j=0; j<s3->num; j++) //s1에 추가한다. (교집합 원소)
      if(s2->set[i] == s3->set[j])
         Add(s1, s2->set[i]);
  return s1;
}

//집합 s2에서 s3를 뺀 차집합을 s1에 대입한다.
IntSet *Difference(IntSet *s1, const IntSet *s2, const IntSet *s3) {
  int i, j;
  s1->num = 0; //s1을 공집합으로 만든다.
  for(i=0; i<s2->num; i++) {
    for(j=0; j<s3->num; j++) 
       if(s2->set[i] == s3->set[i]) 
          break;
    if(j == s3->num)
       Add(s1, s2->set[i]);
  }
  return s1;
}

//집합 s의 모든 원소 출력
void Print(const IntSet *s) {
   int i;
   printf("{ ");
   for(i=0; i<s->num; i++)
      printf("%d ", s->set[i]);
   printf("}");
}

//집합 s의 모든 원소 출력 (줄 바꿈 문자 포함) 
void PrintLn (const IntSet *s) {
   Print(s);
   putchar('\n');
}

//집합 종료
void Terminate(IntSet *s) {
  if(s->set != NULL) {
     free(s->set);  //배열 해제
     s->max = s->num = 0;
  }
}

* 복사할 원소 개수 구하기

int n = (Capacity(s1) < size(s2)) ? Capacity(s1) : Size(s2);

IntSet 사용하는 프로그램

//사용 예(1)
#include <stdio.h>
#include "IntSet.h"

int main(void) {
   IntSet s1, s2, s3;
   Initialize(&s1, 24);
   Initialize(&s2, 24);
   Initialize(&s3, 24);
   
   Add(&s1, 10);
   Add(&s1, 15);
   Add(&s1, 20);
   Add(&s1, 25); //s1 = {10, 15, 20, 25}
   
   Assign(&s2, &s1);  //s2 = {10, 15, 20, 25}
   Add(&s2, 12);      //s2 = {10, 15, 20, 25, 12}
   Remove(&s2, 20);   //s2 = {10, 15, 12, 25}
   Assign(&s3, &s2);  //s3 = {10, 15, 12, 25}
   
   printf("s1 = "); PrintLn(&s1);
   printf("s2 = "); PrintLn(&s2);
   printf("s3 = "); PrintLn(&s3);
   
   printf("집합 s1에 15가 들어있%s.\n", IsMember(&s1,15) > 0 ? "습니다." : "지 않습니다.");
   printf("집합 s1에 25가 들어있%s.\n", IsMember(&s2, 25) > 0 ? "습니다." : "지 않습니다.");
   printf("집합 s1과 s2는 서로 같%s.\n", Equal(&s1, &s2) > 0 ? "습니다." : "지 않습니다.");
   printf("집합 s2와 s3은 서로 같%s.\n", Equal(&s2, &s3) > 0 ? "습니다." : "지 않습니다.");
   
   Terminate(&s1);
   Terminate(&s2);
   Terminate(&s3);
   
   return 0;
}

//사용 예(2)
#include <stdio.h>
#include "IntSet.h"

enum {ADD, RMV, SCH};

//데이터 입력
int scan_data(int sw) {
  int data;
  switch(sw) {
     case ADD : printf("추가할 데이터 : "); break;
     case RMV : printf("삭제할 데이터 : "); break;
     case SCH : printf("검색할 데이터 : "); break;
  }
  scanf("%d", &data);
  
  return data;
}

int main(void) {
  IntSet s1, s2, temp;
  Initialize(&s1, 512); Initialize(&s2, 512); Initialize(&temp, 512);
  
  while(1) {
    int m, x, idx;
    
    printf("s1 = "); PrintLn(&s1);
    printf("s2 = "); PrintLn(&s2);
    printf("(1)s1에 추가 (2)s1에서 삭제 (3)s1에서 검색 (4)s1<-s2 (5) 여러 연산\n"
           "(6)s2에 추가 (7)s2에서 삭제 (8)s2에서 검색 (9)s2<-s1 (0) 종료 : ");
    
    scanf("%d", &m);
    if(m == 0) break;
    switch(m) {
       case 1 : x = scan_data(ADD); Add(&s1, x); break;
       case 2 : x = scan_data(RMV); Remove(&s1, x); break;
       case 3 : x = scan_data(SCH); idx = IsMember(&s1, x);
          printf("s1에 들어있%s.\n", idx >= 0 ? "습니다" : "지 않습니다"); break;
       case 4 : Assign(&s1, &s2); break;
       case 5 : printf("s1 == s2 = %s\n", Equal(&s1, &s2) ? "true" : "false");
          printf("s1 & s2 = "); Intersection(&temp, &s1, &s2;
          PrintLn(&temp);
          printf("s1 | s2 = "); Union(&temp, &s1, &s2);
          Println(&temp);
          printf("s1 - s2 = "); Difference(&temp, &s1, &s2);
          Println(&temp);
          break;
       case 6 : x = scan_data(ADD); Add(&s2, x); break;
       case 7 : x = scan_data(RMV); Remove(&s2, x); break;
       case 8 : x = scan_data(SCH); idx = IsMember(&s2, x);
          printf("s2에 들어 있%s.\n", idx >= 0 ? "습니다" : "지 않습니다."); break;
       case 9 : Assign(&s2, &s1); break;
    }
  }

  Terminate(&s1); Terminate(&s2); Terminate(&s3);
  
  return 0;
}

 

07-3 비트 벡터로 집합 만들기 

 

비트 벡터로 집합 만들기

• 집합의 최대 요소 개수인 max의 값이 작을 경우 집합을 하나의 정수로 표현할 수 있다. 

ex) unsigned long형이 32비트라고 가정할 때, 이때 정수를 구성하는 비트의 나열을 비트 벡터(bit vector)라고 한다. 
비트 벡터 안의 값은 각 원소의 유무에 따라 1, 0을 대입한다. (집합에 들어 있으면 1, 들어있지 않으면 0)
32비트의 부호가 없는 정수로 {0, 1, ... 31}을 전체 집합(universal set)으로 표현할 수 있다. 

//비트 벡터 집합 BitSet(헤더)
#ifndef ___BitSet
#define ___BitSet

typedef unsigned long BitSet; //비트 벡터 집합을 나타내는 자료형

//객체형 매크로 BitSetNull은 공집합의 비트 벡터를 나타내는 정수이다. 
//모든 비트가 0(unsigned long형)이다.
#define BitSetNull (BitSet)0         //공집합
//객체형 매크로 BitSetBits는 비트 벡터에서 유효한 비트 수를 나타내는 정수이다. 
//unsigned long형 비트의 아래쪽 32비트만 사용하므로 값을 32로 정의한다.
#define BitSetBits 32                //유효 비트 수
//함수 형식의 매크로 SetOf는 유일한 원소가 no인 집합({no})을 표현하는 비트 벡터를 만든다. 
//집합{원소}에서 비트를 왼쪽으로 no만큼 시프트해 집합{no}를 만든다. 
#define SetOf(no)  ((BitSet1 <<(no)) //집합 {no}

//집합 s에 n이 있는지 확인
int IsMember(BitSet s, int n);

//집합 s에 n 추가
void Add(BitSet *s, int n);

//집합 s에서 n 삭제 
void Remove(BitSet *s, int n);

//집합 s의 원소 개수 반환
int Size(BitSet s);

//집합 s의 모든 원소 출력
void Print(BitSet s);

//집합 s의 모든 원소 출력(줄바꿈 문자 포함)
void PrintLn(BitSet s);

#endif

//비트 벡터에 의한 정수 집합 연산
#include <stdio.h>
#include "BitSet.h"

//집합 s에 n이 들어 있는지 확인
int IsMember(BitSet s, int n) {
   //집합 s 비트 벡터와 {n} 비트 벡터를 논리곱(&) 연산한다. 
   //집합에 n이 들어 있는 경우 비트 벡터 s와 n으로 논리곱 연산을 하면 {n}이 나온다. 
   //집합에 n이 들어 있지 않은 경우 논리곱 연산을 하면 공집합이 나온다. 
   //> 집합 s에 n값이 없다면 모든 비트가 0인 배열이 나온다. 
   //if(IsMembe(&s, n));  으로 사용도 가능
   return s & SetOf(n);
}

//집합 s에 n 추가
void Add(BitSet *s, int n) {
  //집합 s 비트 벡터와 SetOf(n)으로 얻은 비트 벡터를 논리합(OR) 연산한다. 
  //집합에 n이 이미 들어 있다면, 논리합 연산을 해도 집합 s는 수정되지 않는다. 
  //집합에 n이 없다면, 논리합 연산에 의해 n에 대응하는 비트가 0에서 1로 수정된다. (원소 추가)
  *s |= SetOf(n);
}

//집합 s에서 n 삭제
void Remove(BitSet *s, int n) {
   //집합 s의 비트 벡터와 SetOf(n)으로 얻은 비트 벡터의 보수로 논리곱 연산을 하면 n이 삭제된다.
   *s &= ~SetOf(n);
}

//집합 s의 원소 개수 반환
int Size(BitSet s) {
   int n = 0;
   //집합 원소 개수 > 비트 벡터 안에 '1' 비트가 몇 개인지 알아내면 된다. 
   //s에서 1을 뺀 s-1과 논리곱 연산을 하면 s에서 가장 아래쪽 비트가 0으로 바뀐다. 
   //다시 s에 대해 같은 연산을 수행한다. 가장 아래쪽 비트가 1 > 0으로 바뀐다. 
   //그러면 모든 비트가 0이 된다. 가장 아래쪽 비트를 삭제하는 연산을 수행하면 집합 원소가 1개씩 삭제되는데, 이 연산 횟수가 곧 집합 원소 개수가 된다.
   for(; s!=BitSetNull; n++)
      s &= s - 1;
   return n;
}

//집합 s의 모든 원소 출력
void Print(BitSet s) { 
  int i;
  printf("{ ");
  for(i=0; i<BitSetBits; i++)
     if(IsMember(s, i))
        printf("%d ", i);
  printf("}");
}

//집합 s의 모든 원소 출력
void PrintLn(BitSet s) {
   Print(s);
   putchar( '\n');
}

 

비트 벡터로 집합을 표현하는 프로그램

• '집합 연산'을 위한 함수의 개수는 배열로 집합을 표현하는 프로그램보다 '집합 연산'을 위한 함수의 개수가 적다. 
• 배열로 집합을 표현하는 프로그램보다 적은 개수의 함수로 다양한 연산을 수행할 수 있기 때문이다. 

두 집합이 같은지 확인하기 > 등가 연산자 ==, != 사용  두 집합이 같을 경우 정수 값이 같기 때문이다.

교집합 구하기 > 비트 단위의 논리곱 연산자 &를 사용한다.  s1 & s2

합집합 구하기 > 비트 단위의 논리합 연산자 | 를 사용한다. s1 | s2

차집합 구하기 > 보수 연산자 ~와 비트 단위의 논리곱 연산자 &를 조합해 구한다.  s1 & ~s2

//집합 연산을 사용하는 프로그램 
#include <stdio.h>
#include "BitSet.h"

enum {ADD, RMV, SCH};

//데이터 입력
int scan_data(int sw) {
  int data;
  switch(sw) {
     case ADD : printf("추가할 데이터 : "); break;
     case RMV : printf("삭제할 데이터 : "); break;
     case SCH : printf("검색할 데이터 : "); break;
  }
  scanf("%d", &data);
  
  return data;
}

int main(void) {
  BitSet s1 = BitSetNull;
  BitSet s2 = BitSetNull;
  
  while(1) {
    int m, x, idx;
    
    printf("s1 = "); PrintLn(&s1);
    printf("s2 = "); PrintLn(&s2);
    printf("(1)s1에 추가 (2)s1에서 삭제 (3)s1에서 검색 (4)s1<-s2 (5) 여러 연산\n"
           "(6)s2에 추가 (7)s2에서 삭제 (8)s2에서 검색 (9)s2<-s1 (0) 종료 : ");
    
    scanf("%d", &m);
    if(m == 0) break;
    switch(m) {
       case 1 : x = scan_data(ADD); Add(&s1, x); break;
       case 2 : x = scan_data(RMV); Remove(&s1, x); break;
       case 3 : x = scan_data(SCH); idx = IsMember(&s1, x);
          printf("s1에 들어있%s.\n", idx != 0 ? "습니다" : "지 않습니다"); break;
       case 4 : s1 = s2; break;
       case 5 : printf("s1 == s2 = %s\n", s1 == s2 ? "true" : "false");
          printf("s1 & s2 = "); PrintLn(s1 & s2);
          printf("s1 | s2 = "); Println(s1 | s2);
          printf("s1 - s2 = "); Println(s1 & ~s2);
          break;
       case 6 : x = scan_data(ADD); Add(&s2, x); break;
       case 7 : x = scan_data(RMV); Remove(&s2, x); break;
       case 8 : x = scan_data(SCH); idx = IsMember(&s2, x);
          printf("s2에 들어 있%s.\n", idx != 0 ? "습니다" : "지 않습니다."); break;
       case 9 : s2 = s1; break;
    }
  }

  return 0;
}