본문 바로가기
Datastructure/[5] 집합

[5] 집합 ① 배열을 이용한 집합 구현

old-cast1e 2024. 4. 6.
728x90
반응형

1. 집합과 원소

집합이란 명확한 조건을 만족하는 자료의 모임을 의미한다. 즉, 집합도 자료구조로 표현할 수 있다.

이번 포스팅에서는 집합의 기본 개념에 대해 알고 집합을 다양한 방법으로 구현해 본다. 

집합과 원소

집합이란 객관적으로 범위를 규정한 '어떤 것'의 모임이며, 그. 집합 안에서 각각의 '어떤 것'을 원소라고 한다.

집합은 유한 집합과 무한 집합으로 나뉘며 원소가 없는 집합을 '공집합'이라고 한다.

부분집합과 진부분집합

· 부분 집합

- 집합 A와 B에서 집합 A의 모든 원소가 집합 B의 원소라면, A는 B의 부분집합이고 'A는 B에 포한된다'라고 한다.

· 진부분집합

- 집합 A의 모든 원소가 집합 B의 원소이면서 집합 A와 집합 B가 같지 않을 때  'A는 B의 진부분집합'이라고 한다.

집합의 연산

집합 연산의 이름과 기호표현, 의미는 아래 이미지와 같다.

 

집합의 연산

2. 배열로 집합 만들기

배열로 집합 만들기

모든 원소가 같은 자료형으로 구성된 집합은 배열로 표현할 수 있다.

 

그런데 배열을 사용하여 집합을 표현하기 위해서는 집합의 원소 개수와 배열의 요소 개수는 같거나 배열의 요소 개수가 커야 한다. 즉, 집합을 표현하는 배열과 이 배열의 정보(배열의 크기: max, 집합 우너소의 개수: num)를 담은 구조체를 함께 사용해야 한다.

typedef struct {
	int max;	/* 집합의 크기 */
	int num;	/* 집합의 원소 개수 */
	int *set;	/* 집합 본체의 배열(의 첫 번째 요소에 대한 포인터) */
} IntSet;

코드의 변수 설명은 아래와 같다.

 

·  max :  집합의 최대 크기를 나타내는 멤버.

·  num : 집합의 원소의 개수

·  set :  집합을 넣는 배열의 포인터

 

위 구조체를 이용하는 int형 집합 프로그램 헤더는 아래 [더보기]란의 코드를 이용한다.

더보기 
/* int형 집합 IntSet(헤더 부분) */
#ifndef ___IntSet
#define ___IntSet

/*--- int형 집합을 관리하는 구조체 ---*/
typedef struct {
	int max;	/* 집합의 크기 */
	int num;	/* 집합의 원소 개수 */
	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 *s2);

/*--- 집합 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

🔼 🔼 🔼 

위 코드는 헤더 파일을 선언한 것으로. h로서 확장자를 지정해야 하며,

위 헤더를 사용할 경우 include를 이용한다.

배열을 이용한 집합 알고리즘

·  구조체를 이용한 헤더를 기반으로 하는 배열형 집합 알고리즘은 아래 [더보기]의 코드와 같다.

더보기 
/* 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;
	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){
	/* 들어있지 않으면 배열 끝에 n을 추가*/
	if (s->num < s->max && IsMember(s, n) == -1) 	
		s->set[s->num++] = n; 					
}

/*--- 집합 s에서 n을 삭제 ---*/
void Remove(IntSet *s, int n){
	int idx; /* 마지막 요소를 삭제 위치로 옮김 */
	if ((idx = IsMember(s, n)) != -1) {s->set[idx] = s->set[--s->num];}
}

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

/*--- 집합 s의 원소 개수를 반환 ---*/
int Size(const IntSet *s){return s->num;}

/*--- 집합 s2를 s1에 대입 ---*/
void Assign(IntSet *s1, const IntSet *s2){
	int i;
	int n = (s1->max < s2->num) ? s1->max : s2->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++) {
		for (j = 0; j < s2->num; j++)
			if (s1->set[i] == s2->set[j])
				break;
		if (j == s2->num)
			return 0;
	}
	return 1;
}

/*--- 집합 s2와 s3의 합집합을 s1에 대입 ---*/
IntSet *Union(IntSet *s1, const IntSet *s2, const IntSet *s3){
	int i;
	Assign(s1, s2);
	for (i = 0; i < s3->num; i++)
		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++)
		for (j = 0; j < s3->num; j++)
			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[j])
				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;
	}
}

배열을 이용한 집합 알고리즘 코드 설명

Initialize : 배열을 초기화하는 함수

Initialize 함수는 집합을 표현할 배열을 만드는 준비를 수행하는 함수이다. 초기 상태의 집합은 공집합이므로 num의 값을 0으로 선언한다. 이후 인자로 받은 max(배열의 크기)의 값에 따라 배열을 동적할당한다.

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;
    return 0;
}

동적할당 후에 배열의 크기를 저장한다.

IsMember : 원소가 들어 있는지 확인하는 함수

IsMember 함수는 배열 set에 n이라는 값을 가진 원소가 있는지 확인한다.

배열을 순환하여 스캔에 성공하면 찾은 요소의 인덱스를 반환하고 실패하면 -1을 반환한다.

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;          /* 들어있지 않음 */
}

Add: 원소를 추가하는 함수

Add 함수는 집합에 원소 n을 추가하는 함수이다. 

배열이 비어 있고 집합에 같은 원소 n이 들어 있지 않은 경우만 원소를 추가한다.

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

Remove : 원소를 삭제하는 함수

Remove 함수는 집합에서 원소 n을 삭제하는 함수이다. 이때 집합에서 n이 들어 있는 경우에만 수행한다.

n이 들어 있는 요소의 인덱스를 IsMember 함수를 통해 조사하고 반환값을 idx에 저장한다. 이후 num의 개수를 감소하고 뒤의 값을 복사 및 저장하면 된다.

void Remove(IntSet *s, int n){
    int idx; /* 마지막 요소를 삭제 위치로 옮김 */
    if ((idx = IsMember(s, n)) != -1) {s->set[idx] = s->set[--s->num];}
}

Capacity, Size : 원소의 개수를 관리하는 함수

· Capacity :집합 s에 넣을 수 있는 최대 원소 개수를 반환

· Size : 집합 s의 원소 개수를 반환

int Capacity(const IntSet *s){return s->max;} /*--- 집합 s에 넣을 수 있는 최대 원소 개수를 반환 ---*/
int Size(const IntSet *s){return s->num;} /*--- 집합 s의 원소 개수를 반환 ---*/

Assign : 집합을 대입하는 함수

Assign 함수는 한 집합을 다른 집합으로 복사하는 함수이다. 복사 원본은 S2가 가리키는 집합이고 복사할 대상은 S1이 가리키는 집합이다.

void Assign(IntSet *s1, const IntSet *s2){
    int i;
    int n = (s1->max < s2->num) ? s1->max : s2->num;    
    /* 복사하는 원소의 개수 */
    for (i = 0; i < n; i++) s1->set[i] = s2->set[i];
    s1->num = n;
}

 

복사 원본(32)의 원소 개수(s2 -> num)가 복사할 대상의 집합 크기(s1-> max) 보다 큰 경우에는 복사할 대상의 집합 크기(51-〉)(aN)에 대한 원소만큼만 복사한다. 실제로 복사할 원소의 개수는 다음과 같이 구할 수 있다.

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

 Equal : 두 집합이 같은지 조사하는 함수

Equal 함수는 S1과 S2가 같은지 판단하는 함수이다. 두 배열이 같으면 1을 반환하고 갈지 않으면 -0을 반환한다.

 

Equal 함수는 다음과 같이 구현한다.

  1. 원소 개수가 같지 않은 경우 두 집합은 같지 않은 것으로 판단하고 0을 반환한다.
  2. 원소 개수가 같은 경우,
    i가 1 씩 증가하여 집합 S1의 원소(S1->set [i])가 집합 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++) {
        for (j = 0; j < s2->num; j++)
            if (s1->set[i] == s2->set[j])
                break;
        if (j == s2->num)
            return 0;
    }
    return 1;
}

Union : 두 집합의 합집합을 구하는 함수

Union 함수는 집합 S2, S3의 합집합을 구해 S1에 대입하는 함수이다.

먼저 Assign 함수로 집합 S2를 S1에 복사한 다음 S3의 모든 원소를 하나씩 S1에 추가하면 S1에 S2,S3의 합집합이 대입된다. Union 함수는 s1의 포인터를 반환합니다.

 

다시 말해, Union 함수는 S1과 S2,S3의 3개의 배열 포인터를 인자로 받고 S2,S3의 합집합을 S1에 저장한 후 S1의 포인터를 반환한다.

 

위 코드에서 필자는 중복되는 배열의 값을 제외한 나머지를 합집합으로 Add 하도록 위 전체 코드를 조금 수정했다. 입력값이 정렬되어 있다면, 혹은 출력에서 중복을 제외하는 알고리즘을 사용한다면 위 코드에서 IsMember 함수 실행은 빼도 무방하다.

IntSet *Union(IntSet *s1, const IntSet *s2, const IntSet *s3){
    int i;
    Assign(s1, s2);
    for (i = 0; i < s3->num; i++){
        if(IsMember(s1,s3->set[i])!=-1)
            Add(s1, s3->set[i]);
    }
    return s1;
}

Intersection : 두 집합의 교집합을 구하는 함수

교집합의 의미는 다음과 같다.

집합 A, B에 대하여, A, B의 양쪽에 속하는 요소 전체로 이루어지는 집합.

 

Intersection 함수는 집한 s2, s3의 교집합을 s1에 대입하는 함수이다. Equal 함수는 다음과 같이 구현한다.

 

    1. 먼저 s1을 공집합으로 초기화한다. 

    2 집합 s2의 모든 원소를 스캔하면서 s2의 원소가 s3에 포함된다면 s1에 추가한다.

    3. 스캔이 끝나면 s1에는 교집합의 원소가 포함되고, 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++)
        for (j = 0; j < s3->num; j++)
            if (s2->set[i] == s3->set[j])
                Add(s1, s2->set[i]);
    return s1;
}

Difference : 두 집합의 차집합을 구하는 함수

차집합의 의미는 아래와 같다.

두 집합 A, B에서 집합 A에는 속하지만 집합 B에는 속하지 않는 모든 원소로 이루어진 집합을 A에 대한 B의 차집합이라고 하며, 이 것을 기호로 B A-B A-B와 같이 나타낸다.

 

Difference 함수는 집합 s2과 s3의 차집합을 s1에 대입하는 함수이다. Difference 함수는 다음과 같이 구현한다.

 

    1. 먼저 s1을 공집합으로 초기화합니다.

    2. 집합 s2의 모든 원소를 스캔하면서 s2의 원소가 s3에 있다면 s1에 추가한다.

    3. 스캔이 끝나면 s1에는 차집합의 원소가 포함되고, 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[j])
                break;
        if (j == s3->num)
            Add(s1, s2->set[i]);
    }
    return s1;
}

Print / PrintLn : 집합의 모든 원소를 출력하는 함수

Print Pintin 함수는 집합의 모든 원소를 출력하는 함수이다. 두 함수의 차이는 줄 바꿈 문자의 포함 여부이다.

void Print(const IntSet *s){
    printf("{ ");
    for (int i = 0; i < s->num; i++)  printf("%d ", s->set[i]);
    printf("}");
}

void PrintLn(const IntSet *s){Print(s);putchar('\n');}

Terminate : 메모리를 정리하고 종료하는 함수

Teminate 함수는 모든 과정을 정리하는 함수이다.

void Terminate(IntSet *s){
    if (s->set != NULL) {
        free(s->set);   /* 배열 해제 */
        s->max = s->num = 0;
    }
}
728x90
반응형
저작자표시

'Datastructure > [5] 집합' 카테고리의 다른 글

[5] 집합 ② 연결리스트를 이용한 집합 구현  (0) 2024.05.09

'Datastructure/[5] 집합' 관련글

댓글

티스토리툴바