# 6. 집합(set)

정의

정렬되지 않은 컬렉션인 집합은 중복되는 원소가 없으며, 유한 집합의 개념을 컴퓨터 과학에 적용한 개념입니다. 교집합, 합집합, 차집합 등 다양한 수리적 개념이 있으며, 실제 ES6에는 set과 map이라는 좋은 자료구조가 클래스로 존재합니다.

배열이 아닌 객체로 집합을 표현한다

자바스크립트의 객체는 동일한 키로 여러 프로퍼티를 가질 수 없으므로 집합에서 원소가 중복되지 않는 특성이 그대로 보장됩니다. ES6의 Map과 Set에 대한 이해를 간단히 정리하고, 모방하여 클래스를 사용하여 구현하고 기본적인 메소드를 생각해보고자 합니다.

👉🏻 Map과 Set

형태

class Set {
  constructor() {
    this.items = {};
  }
  
  has(value) {
    return this.items.hasOwnProperty(value);
  }
  
  add(value) {
    if(!this.has(value)) {
      this.items[value] = value;
      return true;
    }
    return false;
  }
  
  remove(value) {
    if(this.ahs(value)) {
      delete this.item[value];
      return true;
    }
    return false;
  }
  
  clear() {
    this.items = {};
  }
  
  size() {
    return Object.keys(this.items).length;
  }
  
  values() {
    return Object.keys(this.items);
  }
}

let set = new Set();
set.add(1);
set.add(2);
set.has(1);    // true
set.values();  // [ '1', '2' ]

합집합

두 집합 중 어느 한 쪽이라도 포함된 원소로 구성된 집합

class Set {
  constructor() {
    this.items = {};
  }
  
  // ...
  
  union(otherSet) {
    let unionSet = new Set();
    let values = this.values();
    for(let i = 0; i < values.length; i++) {
      unionSet.add(values[i]);
    }
    values = otherSet.value();
    for(let i = 0; i < values.length; i++) {
      unionSet.add(values[i]);
    }
    return unionSet;
  }
}

let unionAB = setA.union(setB);
unionAB.values();  // [ '3', '4', '5', '6' ]

교집합

두 집합 모두 포함되어 있는 원소로 구성된 집합을 구한다.

class Set {
  constructor() {
    this.items = {};
  }
  
  // ...
  
 intersection(otherSet) {
    let intersectionSet = new Set();
    let values = this.values();
    for(let i = 0; i < values.length; i++) {
      if(otherSet.has(values[i])) {
        intersectionSet.add(values[i]);
      }
    }
    return intersectionSet;
  }
}

let intersectionAB = setA.intersection(setB);
intersectionAB.values();  // [ '5' ]

차집합

첫 번째 집합에는 있지만 두 번째 집합에는 없는 원소로 구성된 집합을 구한다.

  constructor() {
    this.items = {};
  }
  
  // ...
  
 difference(otherSet){
    let differenceSet = new Set();
    let values = this.values();
    for(let i = 0; i < values.length; i++) {
      if(!otherSet.has(values[i])){
        differenceSet.add(values[i]);
      }
    }
    return differenceSet;
  }
}

let differenceAB = setA.difference(setB);  
differenceAB.values();  // [ '3', '4' ]

부분집합

어떤 집합이 다른 집합의 일부인지 확인

  constructor() {
    this.items = {};
  }
  
  // ...
  
  subset(otherSet) {
    if (this.size() > otherSet.size()) {
      return false;
    } else {
      let values = this.values();
      for (let i = 0; i < values.length; i++) {
        if (!otherSet.has(values[i])) {
          return false;
        }
      }
      return true;
    }
  }
}

let setA = new Set();
setA.add(3);
setA.add(4);
setA.add(5);
setA.values();  // [3, 4, 5]

let setB = new Set();
setB.add(5);
setB.add(6);
setB.values();  // [5, 6]

let setC = new Set();
setC.add(3);
setC.add(4);
setC.values();  // [3, 4]

console.log(setC.subset(setA));  // true

유니온 파인드(Union-find)

👉🏻 유니온 파인드의 개념

정의

합집합 찾기라고도 불리우며, 트리형 자료 구조의 일종으로 일반적인 트리의 형태와는 조금 다릅니다. 상호 배타적인 집합을 다루기 때문에 서로소 집합(disjoint set)이라고도 합니다. 교집합이 없는 부분 집합들을 관리하는 자료 구조로, 유니온 연산은 모두가 떨어져있는 집합을 원하는 방향으로 합쳐가는 과정을 의미합니다. 연결리스트와 트리구조로 구현이 가능합니다.

배열을 이용한 forest를 형태로 구현하는 것이 일반적입니다. 해당 집합을 대표하는 원소로 tree의 root에 있는 원소의 번호가 위치합니다. 어떤 노드 x의 부모 노드를 par(x)로 저장하며 x = par(x)이면, 대표 노드가 됩니다.

• Make-set : 초기화 연산, 모든 집합 객원화
• Find : 어떤 원소가 주어졌을 경우, 해당 원소가 속한 집합을 반환(해당 원소가 속한 집합을 대표하는 원소를 반환)
• Union : 두 개의 집합을 하나의 집합으로 합침

Make-set

초기 상태에는 원소가 1개만 있는 부분 집합으로만 구성됩니다. UnionFind를 사용하기 전에 반드시 makeSet()을 호출해주어야 합니다.

Find

par(x) = x이면 현재 탐색 중인 정점이 집합을 대표하는 정점이므로 그대로 반환하고, 그게 아니라면 대표 정점을 만날 때 까지 부모 정점을 따라서 탐색,
경로 압축(path compression)이라는 최적화를 사용합니다.

Union

인자 x가 속한 집합과 y가 속한 집합을 합칩니다.

연결리스트로 구현

트리로 구현