집합 (추상 자료형)

개요

집합(Set)은 컴퓨터 과학 분야의 추상 자료형의 일종으로서 값들이 중복 없이, 그리고 순서 없이 저장된 모임이다. 이 개념은 수학에서의 집합에서 따온 것이다.

연산

집합은 다음과 같은 연산을 제공한다. 기호는 구현에 따라 다를 수 있으며, 제공되는 연산도 다양하다.

1. union(S, T): 집합 S, T에 있는 원소를 모두 모은 새 집합을 반환한다(합집합).
2. Intersection(S, T): 집합 S, T의 공통된 원소만을 모은 새 집합을 반환한다(교집합).
3. difference(S, T): 집합 S의 원소 중 집합 T에 포함된 원소를 제외한 새 집합을 반환한다(차집합).
4. has(S, x): 값 x가 집합 S의 원소인지 확인한다.

프로그래밍 언어에서의 지원

각 언어에서는 집합을 내장 자료형으로 제공하는 경우가 많다.

Python에서

파이썬은 집합 구조를 언어 차원에서 적극적으로 지원하고 있는데, { } 기호를 이용해 집합을 생성할 수 있다. 수학 집합의 원소 나열법처럼, {x, y, z}는 x, y, z를 가진 집합을 생성한다.

A = {1, 3, 5, 7, 9}
B = {1, 2, 9, 13}
C = set([3, 3, 7])          # 리스트를 이용해서 생성할 수도 있다. 중복된 원소는 자동으로 제거된다.
# 교집합
set.intersection(A, B)      # {1, 9}
A.intersection(B)           # {1, 9}
A & B                       # {1, 9}
set.intersection(A, B, C)   # set() (공집합)

#합집합
set.union(A, B)    # {1, 2, 3, 5, 7, 9, 13}
A.union(B)
A | B

JavaScript에서

자바스크립트는 ECMAScript 2015부터 Set형을 지원하기 시작했다.

let A = new Set([1, 3, 5, 7, 9]) // 집합 {1, 3, 5, 7, 9} 생성

JS Set의 특징은 순서를 기억한다는 것인데, 엄밀하게는 수학적인 집합이 아니게 된다. 집합에 추가된 순서대로 저장되며 (중복된 원소는 제외), 이를 순회할 수 있는 반복자까지 지원한다. 집합 기본 연산의 제공은 영 부실해서, 교집합이나 합집합과 같은 연산은 직접 구현해야 한다.

let a = new Set([1,2,3]);
let b = new Set([4,3,2]);
let union = new Set([...a, ...b]); // 합집합
let intersection = new Set([...a].filter(x => b.has(x))); // 교집합
let difference = new Set([...a].filter(x => !b.has(x))); // 차집합