[알고리즘] Do it 자료구조와 알고리즘 7장 정리

연습문제 Q_1 > 실습 7 - 2 프로그램에 다음 8개의 함수를 추가하세요.

// 집합이 가득 찼다면 1, 아니면 0을 반환
int IsFull(const IntSet *s);

// 집합의 모든 원소를 삭제하는 함수
void Clear(IntSet *s);

// 집합 s2, s3의 대칭 차를 s1에 대입하는 함수
IntSet *symmetricDifference(IntSet *s1, const IntSet *s2, const IntSet *s3);

// 집합 s1에 s2의 모든 원소를 추가하는 함수(s1 포인터 반환)
IntSet *ToUnion(IntSet *s1, const IntSet *s2);

// 집합 s1에서 s2에 들어 있지 않은 모든 원소를 삭제하는 함수(s1 포인터 반환)
IntSet *ToIntersection(IntSet *s1, const IntSet *s2);

// 집합 s1에서 s2에 들어 있는 모든 원소를 삭제하는 함수(s1 포인터 반환)
IntSet *ToDifference(IntSet *s1, const IntSet *s2);

// 집합 s1이 s2의 부분집합이면 1, 아니면 0을 반환
int IsSubset(const IntSet *s1, const IntSet *s2);

// 집합 s1이 s2의 진부분집합이면 1, 아니면 0을 반환
int IsProperSubset(const IntSet *s1, const IntSet *s2);

 

// Q_1 시작
// 집합이 가득 찼다면 1, 아니면 0을 반환
int IsFull(const IntSet *s) {
    
    return (s->max <= s->num);
    
}

// 집합의 모든 원소를 삭제하는 함수
void Clear(IntSet *s) {
    
    s->num = 0;
    
}

// 집합 s2, s3의 대칭 차를 s1에 대입하는 함수. 전체에서, 동시에 존재하는 것을 뺌.
IntSet *symmetricDifference(IntSet *s1, const IntSet *s2, const IntSet *s3) {
    
    int i;
    s1->num = 0; // 일단 공집합으로 초기화했는데 이게맞나
    
    for (i = 0; i < s2->num; i++)
        if (IsMember(s3, s2->set[i]) == -1)
            Add(s1, s2->set[i]);

    for (i = 0; i < s3->num; i++)
        if (IsMember(s2, s3->set[i]) == -1)
            Add(s1, s3->set[i]);
    
    return s1;
}

// 집합 s1에 s2의 모든 원소를 추가하는 함수(s1 포인터 반환)
IntSet *ToUnion(IntSet *s1, const IntSet *s2) {
    
    int i;

    for(i = 0; i < s2->num; i++) {
        Add(s1, s2->set[i]);
    }
    return s1;
}

// 집합 s1에서 s2에 들어 있지 않은 모든 원소를 삭제하는 함수(s1 포인터 반환)
IntSet *ToIntersection(IntSet *s1, const IntSet *s2) {
    
    int i, j;
    
    IntSet temp;
    Initialize(&temp, s1->max);
    
    // 해당 배열의 크기를 조건으로 두는 반복문 안에서, 해당 배열의 원소의 삭제나 추가 등 크기를 바꾸는 행위는 매우 위험한 작업이므로 주의.
    for(i = 0; i < s1->num; i++) {
        for(j = 0; j < s2->num; j++) {
            if(s1->set[i] == s2->set[i]) { // 들어있는 모든 원소를 수집해 변수값을 갈아끼워줄 예정.
                Add(&temp, s1->set[i]);
                break;
            }
        }
    }
    Assign(s1, &temp);
    Terminate(&temp);
    return s1;
    
    // 정답 제공. 직접 뺌. 여기선 반복 횟수와 지우는 대상이 같기에 else에 ++ 구문을 삽입한듯.
    //    int i = 0;
    //
    //    while (i < s1->num) {
    //        if (IsMember(s2, s1->set[i]) == -1)
    //            Remove(s1, s1->set[i]);
    //        else
    //            i++;
    //    }
    //    return s1;

    
}

// 집합 s1에서 s2에 들어 있는 모든 원소를 삭제하는 함수(s1 포인터 반환)
IntSet *ToDifference(IntSet *s1, const IntSet *s2) {
    
    int i, j;
    
    IntSet temp;
    Initialize(&temp, s1->max);
    
    // 해당 배열의 크기를 조건으로 두는 반복문 안에서, 해당 배열의 원소의 삭제나 추가 등 크기를 바꾸는 행위는 매우 위험한 작업이므로 주의.
    for(i = 0; i < s1->num; i++) {
        for(j = 0; j < s2->num; j++) {
            if(s1->set[i] == s2->set[i])
                break;
        }
        if(j == s2->num) { // 들어 있지 않은 모든 원소를 수집해 변수값을 갈아끼워줄 예정.
            Add(&temp, s1->set[i]);
        }
    }
    Assign(s1, &temp);
    Terminate(&temp);
    return s1;
    
    
    //정답 제공. 직접 뺌. 여기선 반복횟수와 지워지는 대상이 다르기에 그대로 진행했네.
    //    int i;
    //
    //    for (i = 0; i < s2->num; i++)
    //        Remove(s1, s2->set[i]);
    //
    //    return s1;

}

// 집합 s1이 s2의 부분집합이면 1, 아니면 0을 반환
int IsSubset(const IntSet *s1, const IntSet *s2) {
    
    int i, j;

    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;

}

// 집합 s1이 s2의 진부분집합이면 1, 아니면 0을 반환
int IsProperSubset(const IntSet *s1, const IntSet *s2) {
    
    // 일단 사이즈가 크거나 같으면 진부분집합일리가 없음.
    if (s1->num >= s2->num)
        return 0;

    return IsSubset(s1, s2);

}

 

 

연습문제 Q_2 > 배열 안의 원소가 항상 오름차순으로 유지하는 집합 프로그램을 작성하세요. 원소의 검색은 이진 검색 알고리즘을 사용합니다.(추가, 삭제도 마찬가지입니다). 또 오름차순을 유지한다는 특징을 이용해 다른 배열과 같은지 확인하는 작업도 좀 더 효율적으로 진행해 보세요. 이 때 집합을 관리하는 구조체의 이름은 SortedIntSet으로 하세요.

 

내 구현이 형편없어서.. 책에서 제공해준 정답으로 대체

근데 아무리봐도 이 소스에서 IsMember의 리턴 구문은 잘못된 것 같다.

/* Q2 배열의 원소가 오름차순을 유지하는 int형 SortedIntSet*/
#include <stdio.h>
#include <stdlib.h>
#include "SortedIntSet.h"

int Initialize(SortedIntSet *s, int max)
{
    s->num = 0;
    if ((s->set = calloc(max, sizeof(int))) == NULL) {
        s->max = 0;
        return -1;
    }
    s->max = max;
    return 0;
}

int _search(const SortedIntSet *s, int n, int *flag)
{
    int pl = 0;
    int pr = s->num - 1;
    int pc;

    *flag = 1;
    if (s->num <= 0) return 0;

    do {
        pc = (pl + pr) / 2;
        if (s->set[pc] == n) {
            *flag = 0;
            return pc;
        }
        else if (s->set[pc] < n)
            pl = pc + 1;
        else
            pr = pc - 1;
    } while (pl <= pr);

    return pl; // 원소를 찾지 못하더라도, 들어가야 할 곳을 미리 얻어낼 수 있다.
}

int IsMember(const SortedIntSet *s, int n)
{
    int flag;
    int idx = _search(s, n, &flag);
    return flag ? idx : -1; //아무리 봐도 이 순서는 바뀌어야 할 것 같다. flag가 0일 때 찾은 건데..
}

int IsFull(const SortedIntSet *s)
{
    return s->num >= s->max;
}

void Add(SortedIntSet *s, int n)
{
    int i, idx, flag;

    if (s->num < s->max) {
        idx = _search(s, n, &flag);
        if (flag == 1) {
            s->num++;
            // idx 자리까지만 단순삽입정렬을 시행해서, 이미 정렬되어 있다고 전제되는 부분의 불필요한 정렬을 시행하진 않음.
            for (i = s->num - 1; i > idx; i--)
                s->set[i] = s->set[i - 1];
            s->set[idx] = n;
        }
    }
}

void Remove(SortedIntSet *s, int n)
{
    int i, idx, flag;

    if (s->num > 0) {
        idx = _search(s, n, &flag);
        if (flag == 0) {
            --s->num;
            // idx 자리까지만 단순삽입정렬을 시행해서, 이미 정렬되어 있다고 전제되는 부분의 불필요한 정렬을 시행하진 않음.
            for (i = idx; i < s->num; i++)
                s->set[i] = s->set[i + 1];
        }
    }
}

int Capacity(const SortedIntSet *s)
{
    return s->max;
}

int Size(const SortedIntSet *s)
{
    return s->num;
}

void Assign(SortedIntSet *s1, const SortedIntSet *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;
}

int Equal(const SortedIntSet *s1, const SortedIntSet *s2)
{
    int i;

    if (Size(s1) != Size(s2))
        return 0;

    for (i = 0; i < s1->num; i++)
        if (s1->set[i] != s2->set[i])
            return 0;
    return 1;
}

SortedIntSet *Union(SortedIntSet *s1, const SortedIntSet *s2, const SortedIntSet *s3)
{
    int k2, k3;

    s1->num = 0;
    k2 = k3 = 0;
    // 병합 정렬 방법과 유사.
    while (k2 < s2->num && k3 < s3->num) {
        if (s2->set[k2] < s3->set[k3])
            s1->set[s1->num++] = s2->set[k2++];
        else if (s2->set[k2] > s3->set[k3])
            s1->set[s1->num++] = s3->set[k3++];
        else {
            s1->set[s1->num++] = s2->set[k2++];
            k3++;
        }
        if (s1->num == s1->max) return s1;
    }

    if (k2 < s2->num)
        while (k2 < s2->num  &&  s1->num < s1->max)
            s1->set[s1->num++] = s2->set[k2++];
    else
        while (k3 < s3->num  &&  s1->num < s1->max)
            s1->set[s1->num++] = s3->set[k3++];

    return s1;
}

SortedIntSet *Intersection(SortedIntSet *s1, const SortedIntSet *s2, const SortedIntSet *s3)
{
    int k2, k3;

    s1->num = 0;
    k2 = k3 = 0;
    // 같은 원소를 찾을 때까지 돌림.
    while (k2 < s2->num && k3 < s3->num) {
        if (s2->set[k2] < s3->set[k3])
            k2++;
        else if (s2->set[k2] > s3->set[k3])
            k3++;
        else {
            s1->set[s1->num++] = s2->set[k2];
            k3++;
            if (s1->num == s1->max)
                return s1;
        }
    }
    return s1;
}

SortedIntSet *Difference(SortedIntSet *s1, const SortedIntSet *s2, const SortedIntSet *s3)
{
    int k2, k3;

    s1->num = 0;
    k2 = k3 = 0;
    // 이터레이터를 사용하며 진행.
    while (k2 < s2->num && k3 < s3->num) {
        if (s2->set[k2] < s3->set[k3])
            s1->set[s1->num++] = s2->set[k2++];
        else if (s2->set[k2] > s3->set[k3])
            k3++;
        else {
            k2++;
            k3++;
        }
        if (s1->num == s1->max) return s1;
    }

    if (k2 < s2->num)
        while (k2 < s2->num  &&  s1->num < s1->max)
            s1->set[s1->num++] = s2->set[k2++];
    return s1;
}

SortedIntSet *SymmetricDifference(SortedIntSet *s1, const SortedIntSet *s2, const SortedIntSet *s3)
{
    int k2, k3;

    s1->num = 0;
    k2 = k3 = 0;
    // 이터레이터를 사용하며 진행.
    while (k2 < s2->num && k3 < s3->num) {
        if (s2->set[k2] < s3->set[k3])
            s1->set[s1->num++] = s2->set[k2++];
        else if (s2->set[k2] > s3->set[k3])
            s1->set[s1->num++] = s3->set[k3++];
        else {
            k2++;
            k3++;
        }
        if (s1->num == s1->max) return s1;
    }

    if (k2 < s2->num)
        while (k2 < s2->num && s1->num < s1->max)
            s1->set[s1->num++] = s2->set[k2++];
    else
        while (k3 < s3->num && s1->num < s1->max)
            s1->set[s1->num++] = s3->set[k3++];

    return s1;
}

SortedIntSet *ToUnion(SortedIntSet *s1, const SortedIntSet *s2)
{
    int i;

    for (i = 0; i < s2->num; i++)
        Add(s1, s2->set[i]);

    return s1;
}

SortedIntSet *ToIntersection(SortedIntSet *s1, const SortedIntSet *s2)
{
    int i = 0;

    while (i < s1->num) {
        if (IsMember(s2, s1->set[i]) == -1)
            Remove(s1, s1->set[i]);
        else
            i++;
    }
    return s1;
}

SortedIntSet *ToDifference(SortedIntSet *s1, const SortedIntSet *s2)
{
    int i;

    for (i = 0; i < s2->num; i++)
        Remove(s1, s2->set[i]);

    return s1;
}

int IsSubset(const SortedIntSet *s1, const SortedIntSet *s2)
{
    int i, j;

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

int IsProperSubset(const SortedIntSet *s1, const SortedIntSet *s2)
{

    if (s1->num >= s2->num)
        return 0;

    return IsSubset(s1, s2);
}

void Print(const SortedIntSet *s)
{
    int i;

    printf("{ ");
    for (i = 0; i < s->num; i++)
        printf("%d ", s->set[i]);
    printf("}");
}

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

void Clear(SortedIntSet *s)
{
    s->num = 0;
}

void Terminate(SortedIntSet *s)
{
    if (s->set != NULL) {
        free(s->set);
        s->max = s->num = 0;
    }
}

 

연습문제 Q_3 > 실습 7 - 7의 프로그램 기능 중 '(5) 여러 연산' 에 집합 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);
                //Q_3 대칭 차집합 : 두 집합 A, B가 있을 때 공통부분을 뺀 나머지 원소들의 집합.
                printf("s1 대칭차집합 s2 = "); PrintLn((s1 & ~s2) | (s2 & ~s1));
                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;
}

 

 

공부 내용 정리

 

집합 

집합이란 명확한 조건을 만족하는 자료의 모임을 의미한다. 
집합이란 객관적으로 범위를 규정한 '어떤 것'의 모임이며, 그 집합 안에서 각각의 '어떤 것'을 원소 라고 부른다. 

Ex)
집합 X의 원소가 1,5 라면 아래와 같이 표현한다.
X = {1, 5}
다만 집합의 원소에는 순서가 없어서 아래와 같이 표기해도 같은 표현이다.
X = {1, 5}


집합에 포함되는 원소들은 서로 달라야 한다. 예를 들어 {1, 5, 1}같은 집합은 있을 수 없다. 또한 집합은 집합을 원소로 가질 수 있다.
+ 원소의 중복을 허용하는 집합은 다중 집합이라고 하며, 집합과는 구별하여 부른다.



∙ 부분집합 

A = {1, 3}, B = {1, 3, 5}와 같이
집합 A의 모든 원소가 집합 B의 원소이면 A는 B의 부분집합이고,  'A는 B에 포함된다' 라고 말한다.
+ A와 B가 서로 같은 경우 A와 B는 서로 부분집합 관계가 된다.


∙ 진부분집합 

집합 A의 모든 원소가 집합 B의 원소이면서 집합 A와 집합 B가 같지 않을 때 'A는 B의 진부분집합이다' 라고 말한다. 예를 들어 A = {1, 3}, B = {1, 3, 5}인 경우 'A는 B의 부분집합이면서 진부분집합이다' 라고 할 수 있지만 A={1, 3, 5}, B = {1, 3, 5}인 경우는 A는 B의 부분집합이지만 진부분집합은 아니다.

 

집합의 연산

 

∙ 합집합 

집합 A와 집합 B 가운데 적어도 한쪽에 속하는 원소의 집합
Ex) A = {1, 3, 5}, B = {1, 4, 6}이면 A와 B의 합집합은 {1, 3, 4, 5, 6} 이다. 

∙ 교집합 

집합 A와 B 양쪽 모두에 속하는 원소의 집합
Ex) A = {1, 3, 5}, B = {1, 4, 6}이면 A와 B의 교집합은 {1} 이다. 

∙ 차집합 

집합 A의 원소 가운데 집합 B의 원소를 제외한 원소의 집합
Ex) A = {1, 3, 5}, B = {1, 4, 6}이면 A와 B의 차집합은 {3, 5} 이다.



배열로 집합 만들기 

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


배열을 사용하여 집합을 표현하려면 집합의 원소 개수와 배열의 요소 개수는 항상 같아야 한다. 따라서 다음과 같이 집합을 표현하는 배열과 이 배열의 정보(집합의 최대 크기, 집합의 원소 개수)를 담은 구조체를 사용해야 한다.
Ex) int형을 원소로 갖는 집합을 구조체 IntSet으로 관리
typedef struct {
int max; // 집합의 최대 크기
int num; // 집합의 원소 개수
int *set; // 집합
}


비트 벡터로 집합 만들기 

집합의 최대 요소의 개수인 max의 값이 작을 경우 집합을 하나의 정수로 표현할 수 있다.
Ex) unsigned long의 아래쪽 32비트를 사용하여 0번째부터 31번째 까지의 수에 대한 집합을 다룰 수 있다.

 

 

출처 - '자료구조와 함께 배우는 알고리즘 입문 C언어편' 도서