집합에 대해서

안녕하세요, 오늘은 여러분들에게 집합이라는 자료구조에 대해서 설명하려고 합니다.
이 집합은 다른 자료구조들과는 달리 상당히 간단하고 복잡하지 않아 쉽게 이해하실 수 있을 것입니다.

🎨 집합이란 무엇인가?

집합이라는 것에 대해서 간단히 표현하면 집합은 명확한 조건을 기준으로 그 조건을 만족하는 자료들의 모임이라고 할 수 있습니다. 각 집합 안에 포함되는 각각의 어떠한 것들을 요소라고 부르며 그러한 요소들이 모여서 하나의 집합을 이룬다고 말할 수 있는 것이죠!

 

위의 사진은 영국 프리미어리그에 속하는 축구팀의 집합을 나타낸 것입니다. 위와 같은 상황에서 집합의 이름은 프리미어리그에 속하는 축구팀의 집합이 될 것이고 그 집합에 포함되는 각 축구팀이 각각의 요소가 될 것입니다. 집합의 개념 자체는 크게 어렵지 않죠?

🔢 집합의 표현 방식

실제로 집합은 수학 문제, 일상생활 등 다양한 방면에서 사용하고 있습니다. 그럼 이번에는 수학에서 집합을 표현할 때 어떤 방식으로 작성을 하고 이용을 하는지에 대해서 살펴보겠습니다. 먼저 아래와 같이 집합 N의 요소가 1, 2, 3, 4, 5라면 아래와 같이 표현합니다.

 

N = { 1, 2, 3, 4, 5 }

집합에서는 각각의 요소에 대한 순서가 따로 정해져있지 않습니다. 같은 집합에 포함되는 요소의 값은 서로 같으면 안 되며 고유한 값을 가지면서 서로 달라야만 합니다. 하지만 요소의 중복을 허용하는 집합이 존재하기는 하며 그것을 저희는 일반적인 집합과는 구별해서 부르며 다중 집합이라고 부릅니다. 심지어 집합의 요소에는 또 다른 집합을 요소로 추가할 수 있다는 점도 꼭 기억해두세요!

🍱 부분집합과 진부분집합

집합의 종류로는 대표적으로 부분집합과 진부분 집합 이 두 가지가 존재합니다. 각 집합은 공통적인 부분이 아주 많아 거의 유사하지만 한 가지의 다른 점이 존재하기 때문에 이에 대한 차이를 확실히 파악해야 합니다. 먼저 부분집합에 대해 알아보도록 하겠습니다.

 

부분집합에 대해서

• A = { 1, 3 } | B = { 1, 3, 5 }와 같이 집합 A의 모든 요소가 집합 B의 요소이면 A는 B의 부분집합이다.

• A = { 1, 3, 5 } | B = { 1, 3, 5 }와 같이 집합 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의 요소이면서 집합 A와 집합 B가 서로 같지 않을 때 집합 A는 집합 B의 진부분 집합이라고 말할 수 있습니다. 각각의 집합은 포함 관계여야지 동일하면 안됩니다.

🛠 집합의 연산 종류

집합에 대한 대표적인 연산의 종류로는 합집합, 교집합, 차집합 이 세 가지가 존재합니다. 각각의 연산들에 대한 방식이 아주 간단하여 여러분들이 사용하고 이해하는데 크게 어렵지 않을 것이라고 생각합니다. 아래의 세 가지 연산들의 개념을 알아보도록 하겠습니다.

 

합집합 연산

• 집합 A와 집합 B 가운데 적어도 한쪽에 속하는 요소의 집합을 A와 B의 합집합이라고 부른다.

• A = { 1, 3, 5 } | B = { 1, 4, 6 } 이면 A와 B의 합집합은 { 1, 3, 4, 5, 6 } 이다.

교집합 연산

• 집합 A와 집합 B 양쪽 모두에 속하는 요소의 집합을 A와 B의 교집합이라고 부른다.

• A = { 1, 3, 5 } | B = { 1, 4, 6 } 이면 A와 B의 교집합은 { 1 } 이다.

차집합 연산

• 집합 A의 요소 가운데 집합 B의 요소를 제외한 요소의 집합을 차집합이라고 부른다.

• A = { 1, 3, 5 } | B = { 1, 4, 6 } 이면 A와 B의 차집합은 { 3, 5 } 이다.

⛳️ 배열로 집합 만들기

이번에는 앞에서 배운 집합의 개념들을 바탕으로 Java 언어를 활용해 집합을 실질적으로 구현해보도록 하겠습니다. 다양한 집합 구현 방식 중 저희는 배열을 이용하여 이번에 집합을 구현해볼 것이며 각각의 필요 성분들에 대해서 하나씩 살펴보도록 하겠습니다.

---

멤버 변수

클래스 이름은 IntSet이며 IntSet 클래스 속 멤버 변수들은 아래와 같습니다. 먼저 max 변수는 집합의 최대 크기를 나타내는 변수이며 또한 num 변수는 집합 속 존재하는 요소의 개수를 카운트하는 변수입니다. 마지막으로 set 정수형 배열은 집합을 의미합니다.

public class IntSet {
    private int max;
    private int num;
    private int[] set;  
}   

생성자

IntSet 클래스의 생성자에서는 매개변수로 집합이 가질 수 있는 가장 큰 값인 capacity 인자를 사용자로부터 전달받습니다. 그 후 max 변수 값을 전달받은 capacity 값으로 직접 초기화시켜주며 최종적으로 set 정수형 배열을 집합으로 만들어주고 있습니다.

public IntSet(int capacity){
   num = 0;
   max = capacity;
   set = new int[max];
}

각종 메소드

마지막으로 아래의 코드들은 집합에 관련된 다양한 기능을 수행하는 메소드들입니다. 아래의 메소드들 역시 위와 같이 구체적으로 설명하면 좋겠으나 양이 많다 보니 주석을 통해서 코드를 스스로 이해할 수 있을 것이라고 생각이 듭니다. 이 점 양해 부탁드립니다.

public class IntSet {

    // 집합의 최대 개수 반환
    public int capacity(){
        return max;
    }

    // 집합의 요소 개수 반환
    public int size(){
        return num;
    }

    // 집합에서 n을 검색하여 인덱스 값 반환
    public int indexOf(int n){
        for(int i = 0; i < num; i++){
            if(set[i] == n) return i;
        }
        return -1;
    }

    // 집합에서 n이 존재하는지 확인
    public boolean contains(int n){
        return indexOf(n) != -1;
    }

    // 집합에 n을 추가
    public boolean add(int n){
        if(num >= max || contains(n)){
            return false;
        }else{
            set[num++] = n;
            return true;
        }
    }

    // 집합에서 n을 삭제
    public boolean remove(int n){
        int idx;

        if(num <= 0 || (idx = indexOf(n)) == -1){
            return false;
        }else{
            set[idx] = set[--num];
            return true;
        }
    }

    // 집합 s에 현재 집합을 복사
    public void copyTo(IntSet s) {
        int n = (s.max < num) ? s.max : num;
        for (int i = 0; i < n; i++) {
            s.set[i] = set[i];
        }
        s.num = n;
    }

    // 집합 s를 현재 집합에 복사
    public void copyFrom(IntSet s){
        int n = (max < s.num) ? max : s.num;
        for(int i = 0; i < n; i++){
            set[i] = s.set[i];
        }
        num = n;
    }

    // 집합 s와 현재 집합이 같은지 확인
    public boolean equalTo(IntSet s){
        if(num != s.num) return false;
        else{
            for(int i = 0; i < num; i++){
                int j = 0;
                for(; j < s.num; j++){
                    if(set[i] == s.set[j]) break;
                }
                if(j == s.num){
                    return false;
                }
            }
        }
        return true;
    }

    // 집합 s1과 s2의 합집합을 복사
    public void union(IntSet s1, IntSet s2){
        copyFrom(s1);
        for(int i = 0; i < s2.num; i++){
            add(s2.set[i]);
        }
    }

    // 문자열 형식으로 반환
    public String toString(){
        StringBuffer temp = new StringBuffer("{ ");

        for(int i = 0; i < num; i++){
            temp.append(set[i] + " ");
        }
        temp.append("}");
        return temp.toString();
    }
}

---

📸 집합 구현하기

그럼 이제 정말 마지막으로 위에서 열심히 구현한 코드들을 적극적으로 활용하여 실질적으로 집합을 구현해보도록 하겠습니다. 클래스 이름은 IntSetTester이며 main 함수 안에 아래의 코드를 입력하여 정상적으로 프로그램이 실행되는지 확인해보시기 바랍니다.

public class IntSetTester {
    public static void main(String[] args) {
        IntSet s1 = new IntSet(20);
        IntSet s2 = new IntSet(20);
        IntSet s3 = new IntSet(20);

        s1.add(10);
        s1.add(15);
        s1.add(20);
        s1.add(25);

        s1.copyTo(s2);

        s2.add(12);
        s2.remove(25);

        s3.copyFrom(s2);

        System.out.println("s1 = " + s1); // {10, 15, 20, 25}
        System.out.println("s2 = " + s2); // {10, 15, 20, 12}
        System.out.println("s3 = " + s3); // {10, 15, 20, 12}

        System.out.println("집합 s1에 15는 " + (s1.contains(15)? "포함됩니다." : "포함되지 않습니다.")); // 포함된다.
        System.out.println("집합 s2에 25는 " + (s2.contains(25)? "포함됩니다." : "포함되지 않습니다.")); // 포함되지 않는다.
        System.out.println("집합 s1과 s2는 " + (s1.equalTo(s2)? "같습니다." : "같지 않습니다.")); // 같지 않습니다.
        System.out.println("집합 s2와 s3는 " + (s2.equalTo(s3)? "같습니다." : "같지 않습니다.")); // 같습니다.

        s3.union(s1, s2);

        System.out.println("집합 s1과 s2의 합집합은 " + s3 + "입니다."); // 10, 15, 20, 25, 12
    }
}

👍 글을 마치며

오늘은 오랜만에 자료구조라는 주제에 대해 글을 작성하였습니다. 최근에 저는 알고리즘 문제를 꾸준히 풀고 있습니다. 그러나 알고리즘 문제를 풀면서 깊이 느낀 것이 한 가지가 있는데요, 그것은 자료구조를 확실히 알아야 알고리즘 문제를 더 쉽게 풀 수 있다는 것입니다. 각 문제에 어떤 자료구조를 사용해야지 코드가 효율적이고 수행 속도가 빠른지 판단할 수 있는 능력이 필요하기 때문입니다.

 

참고 : Do it 자료구조와 함께 배우는 알고리즘 입문 자바 편