집합

집합은 어떤 값이 그 안에 있는지 없는지를 답해 주는 자료구조입니다. 오늘 들른 사용자 번호를 담아 두고 「이 사람이 왔었나」를 묻는 데 씁니다. 같은 값을 두 번 담지 않습니다. 넣은 순서도 남기지 않습니다.

상세

하루 동안 서비스에 들른 사람이 몇 명인지 센다고 해 봅시다. 한 사람이 스무 번 들러도 한 명입니다. 들를 때마다 사용자 번호를 목록에 적어 두면, 나중에 겹치는 번호를 걷어내는 일이 따로 남습니다.

집합은 값을 겹치지 않게 모아 두는 자료구조입니다. 어떤 값이 그 안에 있는지를 묻는 데 씁니다. 물음에는 「들어 있다」와 「들어 있지 않다」 둘 중 하나로만 답합니다. 담긴 값 하나하나를 원소라고 부릅니다.

집합이 지키는 약속은 셋입니다.

세 약속을 뒤집으면 집합을 쓰면 안 되는 때가 나옵니다. 순서가 뜻을 가지거나 같은 값이 몇 개인지를 세야 하는 일에는 집합이 안 맞습니다. 그때는 배열이나 리스트를 씁니다.

배열과 갈리는 대목

배열은 칸마다 번호가 붙어 있습니다. 같은 값이 여러 번 담깁니다. 값 하나가 들어 있는지 알려면 첫 칸부터 차례로 견주어 보아야 합니다. 칸이 백만 개면 없는 값을 찾을 때 백만 번을 견줍니다.

집합은 칸 번호를 포기하는 대신 그 견주는 일을 없앱니다. 둘을 나란히 놓으면 이렇습니다.

마지막 두 줄이 맞바꿈입니다. 칸 번호를 내주고, 「들어 있나」에 견주지 않고 답하는 것을 얻었습니다.

담는 모양

집합을 만드는 가장 흔한 방법은 값에서 칸 번호를 계산해 내는 것입니다. 값을 넣어 주면 정해진 수 하나를 돌려주는 계산을 해시 함수라고 부릅니다. 같은 값을 넣으면 언제나 같은 수가 나옵니다.

값을 담는 칸 하나하나는 버킷이라고 부릅니다. 값을 해시 함수에 넣으면 수가 하나 나옵니다. 그 수가 가리키는 버킷에 그 값을 둡니다.

사과와 포도가 이미 담긴 집합에 감을 넣으면 버킷이 어떻게 차는지 그림으로 보면 이렇습니다.

flowchart TD
    V["넣을 값 · 감"] --> H["해시 함수"]
    subgraph 버킷
        B0["0번 버킷"] --> S1["사과"]
        B1["1번 버킷 · 비어 있다"]
        B2["2번 버킷"] --> S2["포도"]
        S2 --> S3["감 · 방금 들어왔다"]
        B3["3번 버킷 · 비어 있다"]
    end
    H -->|"2번"| B2

같은 값은 언제나 같은 버킷으로 갑니다. 그래서 이미 있는지 보려면 버킷 하나만 열어 보면 됩니다. 나머지 버킷은 안 봐도 됩니다. 넣은 순서가 아니라 값이 버킷을 정하므로, 순서가 남지 않는 것도 이 방법에서 옵니다.

버킷은 정해진 개수뿐이라 서로 다른 값이 같은 버킷을 받기도 합니다. 그림에서 포도와 감이 한 버킷에 매달린 것이 그 꼴입니다. 그래서 버킷을 열면 그 안에 든 값들을 하나씩 견주어 봅니다.

빈 버킷이 그림에 보이는 것도 눈여겨볼 대목입니다. 집합은 담긴 값 수보다 버킷을 넉넉히 잡아 둡니다. 버킷이 값 수만큼만 있으면 한 버킷에 여럿이 몰려 견줄 것이 늘어납니다.

값을 넣을 때 도는 순서

넣기는 언제나 같은 순서로 돕니다. 이미 있는 값을 다시 넣어도 오류가 나지 않습니다. 그냥 아무 일도 일어나지 않는다는 것이 이 그림의 요점입니다.

flowchart TD
    A["값을 넣어 달라는 요청"] --> B["해시 함수로 버킷 번호를 구한다"]
    B --> C{"그 버킷에 같은 값이 있나"}
    C -->|있다| D["아무것도 하지 않는다"]
    C -->|없다| E["그 버킷에 값을 담는다"]

덕분에 「이미 넣었던가」를 부르는 쪽이 챙기지 않아도 됩니다. 중복을 막는 책임이 집합 안으로 들어와 있는 것입니다.

두 집합을 맞대는 연산

집합이 둘 있으면 물을 것이 셋 생깁니다. 둘을 합치면 무엇이 되는가, 둘 다에 있는 값은 무엇인가, 한쪽에만 있는 값은 무엇인가입니다. 차례로 합집합 · 교집합 · 차집합이라고 부릅니다.

파이썬 표기로 적으면 이렇습니다.

a = {1, 2, 3}
b = {3, 4}
a | b    # {1, 2, 3, 4}
a & b    # {3}
a - b    # {1, 2}

3 만 양쪽에 있어서 합집합에서는 한 번만 나오고 교집합에는 그 값만 남습니다. 세 연산은 같은 두 집합을 세 구역으로 갈라 놓습니다. 어느 구역을 집어 가느냐만 다릅니다.

flowchart TD
    subgraph 구역["두 집합이 갈리는 세 구역"]
        R1["a 에만 있는 값 · 1 · 2"]
        R2["양쪽에 있는 값 · 3"]
        R3["b 에만 있는 값 · 4"]
    end
    R1 --> U["합집합은 세 구역을 다 집는다"]
    R2 --> U
    R3 --> U
    R2 --> I["교집합은 가운데 구역만 집는다"]
    R1 --> D["차집합 a - b 는 첫 구역만 집는다"]

권한 검사가 이 연산 하나로 끝나는 일이 흔합니다. 사용자가 가진 권한과 이 화면이 요구하는 권한의 교집합이 비어 있으면 못 들어오는 것입니다.

해시 기반과 정렬 기반

집합을 만드는 방법은 크게 둘입니다. 하나는 앞에서 본 버킷 방식입니다. 다른 하나는 값을 크기순으로 줄 세워 담는 방식입니다. 이 모양을 트리라고 부릅니다.

트리는 꼭대기에 값 하나를 놓습니다. 그 아래로 가지가 둘씩 뻗습니다. 어떤 값의 왼쪽에는 그보다 작은 값이 놓입니다. 오른쪽에는 큰 값이 놓입니다.

flowchart TD
    R["50"]
    R --> L1["30 · 왼쪽은 작은 값"]
    R --> R1["70 · 오른쪽은 큰 값"]
    L1 --> L2["10"]
    L1 --> L3["40"]
    R1 --> R2["60"]
    R1 --> R3["80"]

값이 크기순으로 놓여 있습니다. 왼쪽 끝부터 따라가면 작은 값부터 차례로 나옵니다. 찾을 때는 한 층 내려갈 때마다 볼 값이 반으로 줍니다. 두 방식은 걸리는 시간이 다릅니다.

n 은 담긴 원소의 개수입니다. O(1) 은 원소가 몇 개든 걸리는 시간이 늘지 않는다는 뜻입니다. O(log n) 은 원소가 두 배가 될 때 한 단계씩만 는다는 뜻입니다. 이 표기의 정본은 빅오 표기법입니다.

작은 값부터 차례로 훑을 일이 있으면 트리 쪽을 씁니다. 있나 없나만 물을 것이면 해시 쪽을 씁니다.

집합이 하는 일 셋

집합이 하는 일은 대개 셋 중 하나입니다.

첫째는 겹치는 값을 걷어내는 일입니다. 값을 차례로 담고 나면 그 안에는 서로 다른 값만 남습니다. 서로 다른 방문자 수를 세는 일이 여기 해당합니다.

둘째는 지나온 곳을 표시하는 일입니다. 그래프나 트리를 훑을 때, 한 번 지난 노드를 다시 밟으면 같은 곳을 맴돌게 됩니다. 지난 노드를 집합에 담아 둡니다. 밟기 전에 물어 보면 맴돌이가 끝납니다.

밟기 전에 묻는 순서를 그림으로 보면 이렇습니다.

flowchart TD
    A["다음 노드로 간다"] --> B{"지나온 집합에 있나"}
    B -->|있다| C["건너뛴다"]
    B -->|없다| D["집합에 담고 밟는다"]
    C --> A
    D --> A

그래서 탐색 알고리즘 설명에는 「지나온 집합」이 거의 늘 따라 나옵니다.

셋째는 가진 것과 필요한 것을 견주는 일입니다. 권한 · 태그 · 라벨처럼 순서가 상관없는 이름 묶음을 다룰 때, 앞 절의 교집합과 차집합이 그대로 답이 됩니다.

글에서 만나는 「집합」

집합은 수학에서 온 말입니다. 그래서 기술 문서가 「~의 집합」이라고 적을 때는 자료구조를 가리키지 않는 때가 많습니다. 수학에서 쓰던 뜻, 곧 겹치지 않게 묶은 모임을 말하는 것입니다. 알고리즘을 「정해진 단계의 집합」이라고 적는 문장이 그렇습니다.

두 뜻은 어긋나지 않습니다. 자료구조 집합은 수학의 집합을 메모리에 옮겨 담은 것이기 때문입니다. 다만 글에서 쓰는 쪽은 담는 방법도 걸리는 시간도 말하지 않습니다.

그래서 이 말을 만나면 담는 그릇을 말하는 문장인지 그냥 묶음을 말하는 문장인지를 갈라 읽으면 됩니다. 버킷이나 걸리는 시간 이야기가 함께 나오면 그릇을 말하는 것입니다.

관련 항목

집합이 속하는 상위 분류

자료구조 · 추상 자료형 · 컬렉션

집합과 견주어 고르는 다른 자료구조

배열 · 리스트 · 맵 · 스택 · 큐 · 튜플

집합을 실제로 담아내는 구현

해시테이블 · 해시 셋 · 트리 셋 · 이진 탐색 트리 · 비트셋 · 블룸필터

집합을 만드는 데 쓰는 밑감

해시 함수 · 버킷 · 해시 충돌 · 트리 · 동등성 · 불변 객체

집합끼리 맞대는 연산

합집합 · 교집합 · 차집합 · 부분집합 · 대칭차집합

집합을 설명할 때 쓰는 개념

원소 · 카디널리티 · 공집합 · 멱집합 · 빅오 표기법

집합을 밑감으로 쓰는 알고리즘

그래프 탐색 · 너비 우선 탐색 · 중복 제거 · 방문 표시

집합의 뜻이 비롯된 수학 분야

집합론 · 벤 다이어그램 · 가산 집합