관계와 함수 - 매핑·동치·순서

이 장에서 배우는 것

앞 장에서 집합을 이용해 어떤 원소가 대상에 포함되는지 표현했다. 이번에는 원소 둘 사이의 연결을 표현한다. 같은 회원이 사용하는 계정, 서로 비교할 수 있는 권한 묶음, 입력과 출력의 대응이 모두 여기에 해당한다. 연결을 코드로 저장하는 일과 그 연결이 어떤 규칙을 만족하는지 확인하는 일을 함께 살펴본다.

특히 “같은 것으로 취급한다”는 말의 의미를 구체적으로 만든다. 계정 두 개가 같다고 입력했을 때 어디까지 같은 그룹에 포함해야 하는지 정하고, 그 규칙을 실행되는 프로그램으로 옮긴다. 전공 수업에서 사용하는 이름도 함께 익히되, 이름보다 코드가 어떤 질문에 답하는지에 먼저 집중한다.

• 두 원소의 연결을 순서쌍으로 표현하고 반사성·대칭성·추이성을 검사한다.
• 동치 관계로 집합을 겹치지 않는 그룹으로 나눈다.
• 함수의 정의역과 공역을 구분하고 단사·전사를 코드로 확인한다.
• 해시 함수가 여러 입력을 같은 출력으로 보낼 수 있다는 것을 작은 예로 확인한다.
• 유니온 파인드 단순판으로 계정 연결 정보를 동치류로 묶는다.

문제 상황

서비스 운영 도구에서 같은 사용자가 만든 계정을 정리한다고 하자. 검토가 끝난 연결 정보로 “계정 가와 계정 나는 같은 사용자다”, “계정 나와 계정 다는 같은 사용자다”가 들어왔다. 화면에는 가·나·다를 하나의 묶음으로 표시해야 한다. 가와 다를 직접 연결한 기록이 없다는 이유로 서로 다른 그룹에 두면 같은 사용자의 계정이 나뉜다.

이번 예제의 계정은 가·나·다·라·마·바다. 확인된 연결은 가와 나, 나와 다, 라와 마다. 바에는 연결 기록이 없다. 원하는 결과는 가·나·다, 라·마, 바라는 세 그룹이다. 연결 기록이 없는 바도 자기 자신과 같은 계정이므로 하나의 그룹을 이룬다.

여기에는 중요한 가정이 있다. 입력 기록은 “서로 비슷하다”가 아니라 “같은 사용자로 확인되었다”는 뜻이다. 비슷한 닉네임이나 같은 접속 주소만으로 연결했다면 이 가정이 성립하지 않을 수 있다. 프로그램을 만들기 전에 연결의 뜻을 정해야 하는 이유다.

먼저 연결의 규칙을 작은 집합에서 검사한다. 그다음 모든 계정 쌍을 직접 저장하지 않고도 같은 그룹인지를 알아낼 수 있는 자료구조를 만든다. 자료구조란 데이터를 저장하고 다루는 방식을 뜻한다.

관계는 두 원소 사이의 규칙이다

원소 두 개를 순서대로 묶은 것을 순서쌍이라 한다. Python에서는 ("가", "나")처럼 길이가 2인 튜플로 표현할 수 있다. 튜플은 리스트처럼 여러 값을 담지만, 만든 뒤 항목을 바꿀 수 없는 묶음이다. 순서가 있으므로 ("가", "나")와 ("나", "가")는 서로 다른 값이다.

집합 A의 원소와 집합 B의 원소를 하나씩 골라 만든 모든 순서쌍의 집합을 곱집합이라 하며 A × B로 쓴다. 그중 규칙에 맞는 순서쌍을 모은 것이 관계다. 전공 수업에서는 두 원소 사이의 관계를 이항 관계(binary relation)라고 부른다. 이 장에서는 주로 같은 집합 안의 원소를 비교한다.

accounts = {"가", "나"}
all_pairs = set()

for left in accounts:
    for right in accounts:
        all_pairs.add((left, right))

assert len(all_pairs) == 4
assert ("가", "나") in all_pairs
assert ("나", "가") in all_pairs

confirmed = {("가", "나")}
assert confirmed <= all_pairs

assert는 뒤의 조건이 참인지 검사하는 문장이다. 거짓이면 실행을 멈추고 오류를 낸다. 위 코드는 출력 대신 검사 통과로 결과를 확인한다. 마지막 줄의 <=는 집합 사이에서 “왼쪽이 오른쪽의 부분집합인가”를 묻는다.

반사성·대칭성·추이성

관계가 만족할 수 있는 세 가지 규칙을 살펴본다. 반사성(reflexivity)은 모든 원소가 자기 자신과 관계를 맺는 성질이다. 대칭성(symmetry)은 한 방향으로 관계가 있으면 반대 방향으로도 관계가 있는 성질이다. 추이성(transitivity)은 앞뒤 두 관계를 이어 얻은 관계도 포함하는 성질이다.

집합 A 위의 관계 R에서 확인하는 세 가지 성질

성질	확인할 조건	계정 예
반사성	모든 a에 대해 (a, a)가 R에 있다	가는 가와 같다
대칭성	(a, b)가 있으면 (b, a)도 있다	가와 나가 같으면 나와 가도 같다
추이성	(a, b)와 (b, c)가 있으면 (a, c)도 있다	가와 나, 나와 다가 같으면 가와 다도 같다

조건은 관계 전체를 대상으로 한다. 일부 원소에서 성립한다고 해서 그 관계의 성질이 되는 것은 아니다. 반대로 실패한 원소나 순서쌍을 하나만 찾아도 해당 성질이 없다는 것을 확인할 수 있다. 다음 검사 함수는 이 조건을 반복문으로 그대로 옮긴 것이다. 입력 관계의 두 원소가 모두 A에 속한다고 가정한다.

def relation_properties(items, relation):
    reflexive = all((a, a) in relation for a in items)
    symmetric = all((b, a) in relation for a, b in relation)
    transitive = all(
        (a, c) in relation
        for a in items
        for b in items
        for c in items
        if (a, b) in relation and (b, c) in relation
    )
    return reflexive, symmetric, transitive


items = {1, 2, 3}
near = {
    (a, b)
    for a in items
    for b in items
    if abs(a - b) <= 1
}
assert relation_properties(items, near) == (True, True, False)
assert (1, 2) in near
assert (2, 3) in near
assert (1, 3) not in near

중괄호 안에서 반복문과 조건을 써서 집합을 만드는 표현은 집합 내포다. 위 코드는 두 값의 차이가 1 이하인 순서쌍을 모은다. abs는 수의 절댓값을 구한다. all은 전달받은 조건이 모두 참일 때 참을 반환한다. 확인할 조건이 하나도 없는 경우에도 참을 반환한다. 예를 들어 관계에 순서쌍이 없다면 대칭성을 어기는 순서쌍도 없다.

이 관계는 자기 자신과 가깝고, 가까움의 방향을 뒤집어도 결과가 같다. 하지만 1과 2가 가깝고 2와 3이 가깝다고 해서 1과 3이 가까운 것은 아니다. “비슷한 계정”을 같은 사용자로 이어 묶을 때 생길 수 있는 문제를 숫자 세 개로 확인한 셈이다.

순서는 대칭성과 다른 조건을 쓴다

집합 포함 관계도 관계다. 권한 묶음 P가 Q의 부분집합이면 P에 있는 권한을 Q도 모두 갖는다. 이 관계는 반사성과 추이성을 만족하지만 대칭성은 일반적으로 만족하지 않는다. 대신 P가 Q에 포함되고 Q가 P에 포함되면 두 집합이 같다는 조건이 성립한다. 이 성질을 반대칭성(antisymmetry)이라고 한다.

반대칭성은 “양방향 관계가 모두 없어야 한다”는 뜻이 아니다. 서로 다른 원소 사이에 양방향 관계가 생기지 않는다는 뜻이다. 반사성·반대칭성·추이성을 만족하는 관계를 부분 순서(partial order)라고 한다. 일부 두 원소는 어느 쪽이 앞인지 비교할 수 없으므로 “부분”이라는 말이 붙는다.

permissions = [set(), {"읽기"}, {"쓰기"}, {"읽기", "쓰기"}]

assert all(p <= p for p in permissions)
assert all(
    p == q
    for p in permissions
    for q in permissions
    if p <= q and q <= p
)
assert all(
    p <= r
    for p in permissions
    for q in permissions
    for r in permissions
    if p <= q and q <= r
)
assert not ({"읽기"} <= {"쓰기"})
assert not ({"쓰기"} <= {"읽기"})

읽기 권한만 있는 묶음과 쓰기 권한만 있는 묶음은 포함 관계로 비교할 수 없다. 권한을 단순히 개수로 비교하면 이 차이를 잃는다. 또 숫자의 <는 자기 자신에 대해 참이 아니므로, 여기서 정의한 반사적인 부분 순서와 구분해서 읽어야 한다.

동치 관계는 겹치지 않는 그룹을 만든다

반사성·대칭성·추이성을 모두 만족하는 관계를 동치 관계(equivalence relation)라고 한다. 원소 자체가 동일하지 않더라도, 정한 기준 아래에서 같은 것으로 취급한다는 뜻이다. 계정 이름 가와 나는 서로 다른 문자열이지만, 같은 사용자라는 기준에서는 동치일 수 있다.

어떤 원소 a와 동치인 원소를 모두 모은 집합을 동치류(equivalence class)라고 한다. a도 자기 자신과 동치이므로 그 집합에 포함된다. 가·나·다가 서로 동치라면 가의 동치류, 나의 동치류, 다의 동치류는 모두 같은 집합이다.

서로 다른 동치류는 원소를 공유하지 않는다. 두 동치류에 공통 원소가 있다고 가정해 보자. 첫 번째 그룹의 원소에서 공통 원소로, 공통 원소에서 두 번째 그룹의 원소로 관계를 이을 수 있다. 대칭성과 추이성 때문에 두 그룹의 원소는 결국 서로 동치다. 따라서 실제로는 같은 동치류다.

이처럼 전체 집합을 빠짐없이, 서로 겹치지 않는 비어 있지 않은 부분집합들로 나누는 것을 분할(partition)이라고 한다. 동치 관계를 정하면 분할이 생긴다. 반대로 분할을 먼저 정하고 “같은 그룹에 속한다”를 관계로 삼아도 동치 관계가 된다.

groups = [{"가", "나", "다"}, {"라", "마"}, {"바"}]
items = {"가", "나", "다", "라", "마", "바"}
relation = set()

for group in groups:
    for left in group:
        for right in group:
            relation.add((left, right))

assert set().union(*groups) == items
assert all(
    groups[i].isdisjoint(groups[j])
    for i in range(len(groups))
    for j in range(i + 1, len(groups))
)
assert relation_properties(items, relation) == (True, True, True)

isdisjoint는 두 집합에 공통 원소가 없는지 검사한다. union(*groups)의 별표는 리스트에 든 집합들을 각각의 인수로 펼쳐 전달한다. 여기서는 세 그룹을 모두 합쳐 전체 계정을 빠짐없이 담았는지 확인한다.

연결 기록에서 동치류를 만드는 방법

실무 입력에는 동치 관계의 모든 순서쌍이 들어 있지 않을 수 있다. 가와 나, 나와 다라는 기록만 있어도 같은 사용자라는 해석에 맞게 가와 다를 함께 묶어야 한다. 입력 기록을 포함하도록 반사·대칭·추이 관계를 보충한 가장 작은 관계를 생각할 수 있다. 전공 수업에서는 이런 보충을 동치 폐포(equivalence closure)라고 부른다.

모든 순서쌍을 실제로 만들 필요는 없다. 각 원소가 어느 그룹에 속하는지만 기억하면 된다. 그룹마다 대표 원소 하나를 두고, 대표가 같으면 같은 그룹으로 판단한다. 그룹을 합치고 대표를 찾는 자료구조를 유니온 파인드(union-find)라고 한다. 이름의 두 부분은 각각 합치기와 찾기를 뜻한다.

처음에는 각 계정이 자기 자신의 대표다. 두 계정의 대표를 찾고, 다르면 한 대표를 다른 대표에 연결한다. 이미 같은 대표라면 바꿀 것이 없다. 이 방식으로 같은 기록이 반복되거나 방향이 바뀐 기록이 들어와도 결과 그룹은 유지된다.

대표의 이름은 사용자의 본명이나 기본 계정을 뜻하지 않는다. 자료구조가 그룹을 식별하기 위해 택한 값이다. 입력 순서가 달라지면 대표가 달라질 수 있으므로, 화면에 표시할 이름이 필요하면 별도의 규칙으로 정해야 한다.

함수는 입력마다 출력을 하나 정한다

함수(function)는 관계 중에서도 특별한 경우다. 입력으로 허용한 집합의 모든 원소에 대해 출력이 정확히 하나 정해져야 한다. 입력 집합을 정의역(domain), 출력이 속하도록 미리 정한 집합을 공역(codomain)이라고 한다. 실제로 나온 출력만 모은 집합은 치역(image)이라고 한다.

예를 들어 계정에서 대표 계정으로 가는 대응을 생각할 수 있다. 정의역은 전체 계정이고 공역도 전체 계정으로 잡을 수 있다. 하지만 실제 대표가 가·라·바뿐이면 치역은 이 세 계정뿐이다. 공역은 가능한 출력의 범위로 지정한 집합이고, 치역은 실제 대응을 보고 얻은 집합이라는 차이가 있다.

수학의 함수와 Python의 함수는 관련이 있지만 같은 말로 취급할 수는 없다. Python 함수는 외부 상태에 따라 같은 인수에 다른 값을 반환하거나 입력에 따라 오류를 낼 수 있다. 수학의 함수로 다루려면 무엇을 입력으로 삼는지, 그 입력마다 어떤 출력이 정해지는지 명확히 해야 한다.

단사와 전사는 서로 다른 질문이다

서로 다른 입력이 서로 다른 출력을 가지면 단사(injective)라고 한다. 공역의 모든 원소가 적어도 한 입력의 출력으로 나타나면 전사(surjective)라고 한다. 둘 다 만족하면 전단사(bijective)라고 한다. 단사는 출력이 겹치는지를 묻고, 전사는 공역에 빠진 출력이 있는지를 묻는다.

유한한 대응표에서 함수의 성질을 확인하는 기준

구분	확인할 것	코드 기준
함수	모든 입력에 출력 하나가 있고 출력이 공역에 속한다	키 집합과 정의역, 값과 공역 검사
단사	서로 다른 입력의 출력이 겹치지 않는다	치역 크기와 정의역 크기가 같다
전사	공역에 실제로 나오지 않은 값이 없다	치역과 공역이 같다
전단사	단사이면서 전사다	두 검사가 모두 참이다

Python의 딕셔너리(dictionary)는 키 하나에 값 하나를 연결하는 저장 방식이다. 중괄호 안에 키: 값을 나열해 만든다. 서로 다른 키가 같은 값을 가질 수 있다. 같은 키를 다시 넣으면 값이 교체되므로 한 입력에 출력 여러 개를 저장하는 방식은 아니다.

def function_properties(domain, codomain, mapping):
    if set(mapping) != domain:
        raise ValueError("정의역과 키 집합이 다르다")

    outputs = set(mapping.values())
    if not outputs <= codomain:
        raise ValueError("공역 밖의 출력이 있다")

    injective = len(outputs) == len(domain)
    surjective = outputs == codomain
    return injective, surjective


domain = {"가", "나", "다"}
mapping = {"가": 10, "나": 20, "다": 30}

assert function_properties(domain, {10, 20, 30}, mapping) == (True, True)
assert function_properties(domain, {10, 20, 30, 40}, mapping) == (True, False)

merged = {"가": 10, "나": 10, "다": 20}
assert function_properties(domain, {10, 20}, merged) == (False, True)

set(mapping)은 딕셔너리의 키를 집합으로 모은다. values()는 값들을 꺼낸다. raise ValueError는 입력이 요구한 조건에 맞지 않음을 오류로 알린다. 마지막 두 검사는 공역도 함수의 성질을 판단하는 데 필요하다는 것을 보여 준다. 대응표가 같아도 공역에 40을 추가하면 전사가 아니게 된다.

해시 함수는 출력을 일부러 작은 범위에 모으기도 한다

해시 함수(hash function)는 입력에서 일정한 범위의 값을 계산하는 함수다. 저장 위치를 고르거나 데이터를 빠르게 구분할 후보를 만드는 데 쓰인다. 서로 다른 입력이 같은 해시값을 갖는 일을 충돌(collision)이라고 한다. 다음은 문자열의 각 글자를 정수로 바꾸어 더한 뒤 8로 나눈 나머지를 구하는 학습용 함수다.

def bucket_hash(text):
    return sum(ord(char) for char in text) % 8


assert bucket_hash("ab") == 3
assert bucket_hash("ba") == 3
assert "ab" != "ba"

ord는 문자 하나에 대응하는 유니코드 정수를 돌려준다. sum은 값들을 더하고, % 8은 8로 나눈 나머지를 구한다. 따라서 공역은 0부터 7까지로 정할 수 있다. 이 함수는 글자의 순서를 구분하지 못한다. 충돌을 쉽게 보여 주기 위한 예이며, 보안 목적이나 실제 분산 품질을 요구하는 용도로 사용할 함수는 아니다.

문자열 전체를 정의역으로 잡고 출력은 여덟 개만 허용하면 모든 문자열을 서로 다른 출력으로 보낼 수 없다. 해시 함수에 충돌이 있다는 사실 자체가 곧 구현 오류를 뜻하지는 않는다. 다만 같은 해시값을 얻었다는 이유로 원문까지 같다고 판단하면 안 된다.

“해시값이 같다”도 하나의 동치 관계다. 모든 입력은 자기 자신과 같은 해시값을 갖고, 값이 같다는 비교는 대칭적이며 추이적이다. 그 동치류에는 서로 다른 원문이 들어갈 수 있다. 동치 기준과 원문 동일성을 구분해야 한다.

완성 코드

다음 내용을 main.py에 저장한다. 외부 패키지와 네트워크를 사용하지 않는다. 작은 관계의 성질, 함수의 성질, 해시 충돌을 확인한 뒤 계정들을 묶는다. 마지막에는 만들어진 그룹에서 관계를 다시 구성해 동치 관계인지 검사한다.

딕셔너리 parent는 각 계정이 다음으로 따라갈 계정을 저장한다. 자기 자신을 가리키는 계정이 대표다. 대표를 찾을 때 연결을 하나씩 따라가는 단순판을 사용한다. 학습용으로 과정을 드러내기 위해 연결을 줄이는 최적화는 넣지 않는다.

def relation_properties(items, relation):
    reflexive = all((a, a) in relation for a in items)
    symmetric = all((b, a) in relation for a, b in relation)
    transitive = all(
        (a, c) in relation
        for a in items
        for b in items
        for c in items
        if (a, b) in relation and (b, c) in relation
    )
    return reflexive, symmetric, transitive


def function_properties(domain, codomain, mapping):
    if set(mapping) != domain:
        raise ValueError("정의역과 키 집합이 다르다")
    outputs = set(mapping.values())
    if not outputs <= codomain:
        raise ValueError("공역 밖의 출력이 있다")
    return len(outputs) == len(domain), outputs == codomain


def bucket_hash(text):
    return sum(ord(char) for char in text) % 8


def find(parent, item):
    while parent[item] != item:
        item = parent[item]
    return item


def union(parent, left, right):
    left_root = find(parent, left)
    right_root = find(parent, right)
    if left_root != right_root:
        parent[right_root] = left_root


def make_groups(items, links):
    if len(set(items)) != len(items):
        raise ValueError("계정 목록에 중복이 있다")

    parent = {item: item for item in items}
    for left, right in links:
        if left not in parent or right not in parent:
            raise ValueError("목록에 없는 계정이 연결에 있다")
        union(parent, left, right)

    grouped = {}
    for item in items:
        root = find(parent, item)
        if root not in grouped:
            grouped[root] = []
        grouped[root].append(item)

    groups = [sorted(group) for group in grouped.values()]
    return sorted(groups)


def main():
    numbers = {1, 2, 3}
    near = {
        (a, b)
        for a in numbers
        for b in numbers
        if abs(a - b) <= 1
    }
    near_properties = relation_properties(numbers, near)
    assert near_properties == (True, True, False)
    print("가까움 관계:", near_properties)

    domain = {"가", "나", "다"}
    mapping = {"가": 10, "나": 20, "다": 30}
    narrow = function_properties(domain, {10, 20, 30}, mapping)
    wide = function_properties(domain, {10, 20, 30, 40}, mapping)
    assert narrow == (True, True)
    assert wide == (True, False)
    print("공역 3개, 단사·전사:", narrow)
    print("공역 4개, 단사·전사:", wide)

    first_hash = bucket_hash("ab")
    second_hash = bucket_hash("ba")
    assert first_hash == second_hash == 3
    print("해시값:", first_hash, second_hash)

    items = ["가", "나", "다", "라", "마", "바"]
    links = [("가", "나"), ("나", "다"), ("라", "마")]
    groups = make_groups(items, links)
    assert groups == [["가", "나", "다"], ["라", "마"], ["바"]]

    print("그룹 수:", len(groups))
    for index, group in enumerate(groups, start=1):
        print(f"그룹 {index}: {', '.join(group)}")

    relation = set()
    for group in groups:
        for left in group:
            for right in group:
                relation.add((left, right))

    properties = relation_properties(set(items), relation)
    assert properties == (True, True, True)
    print("그룹 관계:", properties)


if __name__ == "__main__":
    main()

줄별 해설

relation_properties의 첫 검사는 각 원소의 자기 순서쌍이 있는지 확인한다. 두 번째 검사는 저장된 순서쌍을 뒤집어도 관계에 있는지 확인한다. 세 번째 검사는 a·b·c를 골라 앞의 두 연결이 있는 경우에만 a와 c의 연결을 요구한다. 반환 순서는 반사성, 대칭성, 추이성이다.

추이성 검사는 원소가 n개일 때 세 번 겹친 반복으로 n × n × n개의 조합을 살펴본다. 작은 입력의 정의 확인용이다. 계정이 많아지는 실제 서비스에서 모든 순서쌍과 세 원소 조합을 만들라는 뜻은 아니다.

function_properties는 먼저 대응표가 함수로 해석될 조건부터 검사한다. 정의역에 빠진 키나 추가 키가 있으면 오류를 내고, 공역 밖의 값도 거부한다. 그다음 치역의 크기로 단사를, 치역과 공역의 일치로 전사를 판단한다. 이 크기 비교는 코드처럼 유한한 정의역을 다룰 때 사용할 수 있다.

find의 while은 현재 계정이 자기 자신을 가리킬 때까지 진행한다. 예를 들어 다가 나를 가리키고 나가 가를 가리키며 가가 자신을 가리킨다면, 다의 대표는 가다. 여기서 부모라는 이름은 사용자 사이의 위아래 관계가 아니라 대표를 찾기 위한 내부 연결을 뜻한다.

union은 두 계정 자체가 아니라 두 계정의 대표를 구한다. 대표가 다를 때 오른쪽 대표의 다음 계정을 왼쪽 대표로 바꾼다. 기존 그룹 전체를 하나로 합치기 위해서다. 서로 다른 그룹의 대표 하나만 다른 대표에 연결하므로, 이 함수로 만든 연결을 따라가다가 원을 그리며 반복하는 상황은 생기지 않는다.

make_groups의 첫 검사는 계정 목록에 중복이 없는지 확인한다. 딕셔너리는 같은 키를 하나만 보관하므로 중복을 조용히 지우는 대신 입력 문제로 알린다. 이 예제의 계정은 집합과 딕셔너리의 원소나 키로 쓸 수 있는 문자열로 한정한다.

parent = {item: item for item in items}는 계정마다 자기 자신을 가리키는 항목을 만든다. 이후 연결 기록을 하나씩 읽으며 목록에 없는 계정을 거부하고 union을 호출한다. 연결을 모두 처리한 뒤에야 최종 대표를 기준으로 그룹을 모은다.

grouped의 키는 대표이고 값은 계정 리스트다. 처음 보는 대표라면 빈 리스트를 만든 뒤 계정을 추가한다. append는 리스트 끝에 원소를 붙인다. 따라서 연결 기록이 없었던 바도 자기 대표의 리스트에 들어간다.

마지막 두 번의 sorted는 그룹 내부와 그룹 목록을 정렬한다. 리스트끼리의 정렬은 앞 항목부터 비교한다. 이 예제에서는 문자열의 기본 비교 순서로 결과가 정해진다. 대표가 무엇으로 선택되었는지와 별개로 표시 순서를 일정하게 만드는 처리다.

enumerate는 반복할 항목과 번호를 함께 꺼낸다. start=1로 화면 번호를 1부터 시작한다. 문자열의 join은 계정 사이에 쉼표와 공백을 넣는다. f"..."는 중괄호 안의 값을 문자열에 넣는 표현이다.

마지막 검사는 같은 그룹 안의 모든 순서쌍을 만들어 관계의 성질을 확인한다. 원소가 여섯 개여서 가능한 검증이다. 파일 끝의 조건은 이 파일을 직접 실행했을 때 main()을 호출한다. 난수를 사용하지 않으며 집합의 순회 결과를 그대로 출력하지 않으므로 실행 결과가 일정하다.

실행 결과

macOS나 Linux의 터미널에서 파일이 있는 디렉터리로 이동한 뒤 다음 명령을 실행한다. Python 3.12 이상에서 실행할 수 있다.

python3 main.py

예상 출력은 다음과 같다. 첫 번째와 마지막 튜플의 항목은 반사성·대칭성·추이성 순서다. 함수 검사 튜플의 항목은 단사·전사 순서다.

가까움 관계: (True, True, False)
공역 3개, 단사·전사: (True, True)
공역 4개, 단사·전사: (True, False)
해시값: 3 3
그룹 수: 3
그룹 1: 가, 나, 다
그룹 2: 라, 마
그룹 3: 바
그룹 관계: (True, True, True)

실무에서 만나는 곳

계정 통합이나 중복 데이터 정리에서는 어떤 근거를 동치로 인정하는지가 먼저다. 검토된 동일 인물 기록은 그룹 합치기의 근거가 될 수 있다. 이름 일부가 같거나 같은 기기에서 접속했다는 기록은 그 자체로 추이적인 기준이 아니다. 판단 기준이 달라지면 같은 코드도 다른 의미의 결과를 만든다.

권한 묶음을 비교할 때는 부분 순서가 도움이 된다. 권한이 세 개라는 사실만으로 두 개짜리 묶음의 권한을 모두 포함한다고 판단할 수 없다. 실제 부분집합 검사를 해야 한다. 또 읽기 전용 묶음과 쓰기 전용 묶음처럼 비교할 수 없는 두 묶음을 허용해야 한다.

파일이나 요청의 해시값을 인덱스로 사용할 때는 충돌 뒤의 동작을 정해야 한다. 여기서 인덱스는 저장 대상을 빠르게 찾기 위한 표식이다. 학습용 해시값이 같다면 원문을 추가로 비교해야 원문 동일성을 판단할 수 있다. 원문 전체와 해시값이 각각 어떤 역할을 하는지 데이터 구조에 드러내는 것이 좋다.

단순판 유니온 파인드는 합치기 중심의 처리에 맞는다. 기록을 취소해 한 그룹을 다시 나누는 연산은 제공하지 않는다. 작은 작업이라면 유효한 연결 기록을 보관하고 처음부터 그룹을 다시 만들 수 있다. 또한 내부 연결이 길어지면 대표 찾기가 느려질 수 있다. 이 장의 구현은 작은 데이터에서 규칙을 확인하는 데 목적이 있다.

실무에서 자주 틀리는 것

입력 연결 목록을 곧바로 동치 관계라고 판단한다

연결 기록 두 개는 완성된 관계 전체와 다르다. 자기 자신과의 관계, 반대 방향의 관계, 이어지는 관계가 빠져 있다. 다음 코드는 완성 코드의 검사 함수가 정의되어 있다고 가정한다.

틀린 코드다.

items = {"가", "나", "다"}
links = {("가", "나"), ("나", "다")}
is_equivalence = all(relation_properties(items, links))
assert is_equivalence

이 검사는 실패한다. 기록의 뜻이 동일 사용자 확인이라면 관계 전체를 직접 검사하기 전에 기록으로부터 그룹을 구성해야 한다.

고친 코드다.

items = ["가", "나", "다"]
links = [("가", "나"), ("나", "다")]
groups = make_groups(items, links)
assert groups == [["가", "나", "다"]]

대표가 아니라 입력 계정의 연결만 바꾼다

이미 묶인 그룹의 중간 계정에 다른 그룹을 연결할 때, 그 계정만 이동시키면 기존 그룹이 의도와 다르게 갈라질 수 있다. 다음은 그 문제가 드러나는 작은 예다.

틀린 코드다.

parent = {"가": "가", "나": "가", "다": "다"}
parent["나"] = "다"
assert find(parent, "가") != find(parent, "나")

가와 나가 같은 그룹이었는데, 나만 다른 그룹을 가리키게 되었다. 합칠 때는 두 대표를 찾아 연결해야 한다.

고친 코드다.

parent = {"가": "가", "나": "가", "다": "다"}
union(parent, "나", "다")
assert find(parent, "가") == find(parent, "나")
assert find(parent, "나") == find(parent, "다")

치역을 공역으로 간주해 전사라고 한다

실제로 나온 출력만 공역으로 삼아 검사하면 원래 정해 둔 출력 범위에서 무엇이 빠졌는지 볼 수 없다.

틀린 코드다.

mapping = {"가": 10, "나": 20}
outputs = set(mapping.values())
is_surjective = outputs == set(mapping.values())
assert is_surjective

같은 집합을 자기 자신과 비교하므로 언제나 참이다. 공역을 별도로 정하고 비교한다.

고친 코드다.

domain = {"가", "나"}
codomain = {10, 20, 30}
mapping = {"가": 10, "나": 20}
assert function_properties(domain, codomain, mapping) == (True, False)

같은 해시값이면 원문도 같다고 판단한다

해시값은 여러 원문을 하나의 값에 모을 수 있다. 저장 후보를 좁히는 기준과 원문이 같은지를 판단하는 기준을 구분해야 한다.

틀린 코드다.

left = "ab"
right = "ba"
same_text = bucket_hash(left) == bucket_hash(right)
assert same_text

고친 코드다.

left = "ab"
right = "ba"
same_hash = bucket_hash(left) == bucket_hash(right)
same_text = left == right
assert same_hash
assert not same_text

한눈에 보기

관계와 함수를 코드로 읽을 때 확인할 질문

개념	핵심 질문	코드에서의 확인
관계	어떤 두 원소를 연결하는가	순서쌍의 집합
동치 관계	같은 것으로 묶을 규칙이 갖추어졌는가	반사성·대칭성·추이성
동치류	이 원소와 같은 그룹인 원소는 무엇인가	같은 대표를 가진 원소 모으기
부분 순서	비교할 수 없는 원소도 있는 순서인가	반사성·반대칭성·추이성
단사	서로 다른 입력의 출력이 겹치는가	정의역과 치역의 크기 비교
전사	공역의 모든 값이 실제로 나오는가	치역과 공역 비교
해시 충돌	다른 입력이 같은 해시값을 갖는가	원문 비교와 해시값 비교 분리

연습 문제

1. 집합 {1, 2, 3}에서 자기 자신과의 순서쌍 세 개와 (1, 2), (2, 1), (2, 3), (3, 2)를 관계로 정한다. 세 성질을 검사하고, 동치 관계로 만들기 위해 추가할 순서쌍을 모두 찾아라.
2. 정의역이 {"가", "나", "다"}이고 대응표가 {"가": 0, "나": 0, "다": 1}이다. 공역이 {0, 1}일 때와 {0, 1, 2}일 때 단사·전사를 각각 판정하라.
3. 완성 코드의 연결 기록에 ("다", "라")를 추가하라. 예상 그룹을 쓰고 코드로 확인하라. 이어 ("나", "가")와 ("가", "나")를 더 넣어도 결과가 같은지 확인하라.
4. 학습용 해시 함수에 "ab", "ba", "c", "d"를 넣어라. 같은 해시값을 갖는 문자열을 그룹으로 모으고, 출력 순서가 일정하도록 정렬하라.

정답과 해설

첫 번째 문제

반사성과 대칭성은 참이고 추이성은 거짓이다. 1에서 2로, 2에서 3으로 이어지는데 1에서 3으로 가는 관계가 없다. 반대 방향도 필요하므로 (1, 3)과 (3, 1)을 추가한다. 그러면 세 원소가 하나의 동치류가 된다.

items = {1, 2, 3}
relation = {
    (1, 1), (2, 2), (3, 3),
    (1, 2), (2, 1), (2, 3), (3, 2),
}
assert relation_properties(items, relation) == (True, True, False)
relation.update({(1, 3), (3, 1)})
assert relation_properties(items, relation) == (True, True, True)

두 번째 문제

가와 나의 출력이 같으므로 두 경우 모두 단사가 아니다. 치역은 {0, 1}이다. 첫 공역에서는 전사이고, 두 번째 공역에서는 2가 출력되지 않으므로 전사가 아니다.

domain = {"가", "나", "다"}
mapping = {"가": 0, "나": 0, "다": 1}
assert function_properties(domain, {0, 1}, mapping) == (False, True)
assert function_properties(domain, {0, 1, 2}, mapping) == (False, False)

세 번째 문제

다와 라가 연결되면 기존 두 그룹이 합쳐진다. 바는 여전히 혼자다. 이미 같은 그룹에 속한 계정 사이의 기록을 다시 넣어도 그룹은 달라지지 않는다. 두 대표가 같으면 합치기 함수가 아무것도 바꾸지 않기 때문이다.

items = ["가", "나", "다", "라", "마", "바"]
links = [
    ("가", "나"),
    ("나", "다"),
    ("라", "마"),
    ("다", "라"),
]
expected = [["가", "나", "다", "라", "마"], ["바"]]
assert make_groups(items, links) == expected

links.extend([("나", "가"), ("가", "나")])
assert make_groups(items, links) == expected

네 번째 문제

"ab"와 "ba"의 글자 정수 합은 195이고 "c"의 값은 99다. 둘 다 8로 나눈 나머지가 3이다. "d"의 값은 100이므로 나머지는 4다. 다른 원문 세 개가 같은 해시값으로 묶이는 것을 확인할 수 있다.

words = ["ab", "ba", "c", "d"]
buckets = {}

for word in words:
    value = bucket_hash(word)
    if value not in buckets:
        buckets[value] = []
    buckets[value].append(word)

assert buckets == {3: ["ab", "ba", "c"], 4: ["d"]}

for value in sorted(buckets):
    print(value, sorted(buckets[value]))

출력은 다음과 같다.

3 ['ab', 'ba', 'c']
4 ['d']

관계의 기준을 정하면 같은 원소끼리 묶거나, 원소 사이의 순서를 비교하거나, 입력에서 출력을 정할 수 있다. 다음 장에서는 원소를 고르고 배열하는 방법의 수를 센다.