집합 - 권한·필터·SQL 의 바탕

이 장에서 배우는 것

게시물을 읽을 수 있는 사람과 수정할 수 있는 사람을 따로 관리한다고 하자. 두 작업을 모두 할 수 있는 사람을 찾으려면 두 명단에서 겹치는 사람을 고르면 된다. 둘 중 하나라도 할 수 있는 사람을 찾으려면 두 명단을 합치면 된다. 집합은 이처럼 여러 대상을 묶고, 묶음 사이의 관계를 계산하는 도구다.

앞 장에서 작은 반례로 주장을 점검했다면, 이번에는 권한 목록을 집합으로 만들고 계산 결과를 확인한다. 수식에 등장하는 기호도 Python 연산과 나란히 읽는다. 기호를 먼저 외우기보다 같은 입력에 어떤 결과가 나오는지 살펴보는 것이 출발점이다.

• 집합의 원소, 중복 제거, 순서가 없다는 성질을 코드로 확인한다.
• 부분집합과 합집합·교집합·차집합·여집합을 구별한다.
• 여러 역할에서 얻은 권한을 합치고 금지 권한을 제거한다.
• 한 집합의 모든 부분집합을 모은 멱집합을 생성한다.

문제 상황

팀 문서 도구를 만든다고 하자. 읽기 역할은 문서를 읽을 수 있고, 작성 역할은 읽기와 쓰기를 할 수 있다. 운영 역할은 읽기·내보내기·삭제를 할 수 있다. 한 사용자가 여러 역할을 맡을 수도 있다. 역할 이름을 조건문으로 하나씩 비교하기 시작하면 역할이 추가될 때마다 분기가 늘어난다.

권한을 계산하는 규칙을 먼저 정하면 구조가 단순해진다. 이 장에서는 사용자가 맡은 역할의 권한을 모두 합친 뒤, 별도로 금지한 권한을 제거한다. 이 규칙에서 금지는 허용보다 우선한다. 여러 역할에 같은 권한이 있어도 금지 목록에 들어 있으면 최종 권한에서 빠진다.

예를 들어 읽기 역할과 작성 역할을 가진 사용자는 읽기와 쓰기를 허용받는다. 그런데 해당 사용자에게 쓰기를 금지했다면 최종 권한은 읽기뿐이다. 내보내기 기능을 실행하려면 읽기와 내보내기가 모두 필요하다고 정할 수도 있다. 이때는 필요한 권한 전체가 최종 권한 안에 들어 있는지 검사한다.

여기서 다루는 권한 이름은 read, write, export, delete다. 문자열의 뜻을 Python이 이해하는 것은 아니다. 프로그램이 같은 문자열을 같은 권한으로 취급하도록 약속한 것이다. 표기 실수를 줄이려면 권한 이름을 한곳에 모으고 그 목록 밖의 이름을 검사하는 방식이 도움이 된다.

집합과 포함 관계를 코드로 읽기

원소와 집합의 크기

집합은 구별할 수 있는 대상들을 모아 놓은 것이다. 그 안에 들어 있는 각각의 대상을 전공 수업에서는 원소(element)라고 부른다. 권한 집합에서 "read"는 원소 하나다. 원소가 몇 개인지를 나타내는 값을 집합의 크기 또는 원소 수라고 하며, 전공 수업에서는 기수(cardinality)라는 용어도 쓴다. 유한한 집합을 다루는 이 장에서는 len으로 센다.

permissions = {"read", "write", "read"}
print(len(permissions))
print("read" in permissions)
print("delete" in permissions)

# 출력
# 2
# True
# False

같은 원소를 두 번 적어도 집합에는 한 번만 들어간다. 집합은 원소의 순서도 구별하지 않는다. 따라서 {"read", "write"}와 {"write", "read"}는 같은 집합이다. 먼저 넣은 권한이나 나중에 넣은 권한에 특별한 뜻을 부여하려면 집합만으로는 부족하다.

집합을 그대로 출력했을 때의 원소 나열 순서에는 기대지 않는다. 이 장에서는 출력할 때 sorted로 정렬한다. sorted는 정렬된 새 리스트를 돌려준다. 계산에는 집합을 쓰고, 사람이 읽는 출력에는 정렬한 리스트를 쓰는 셈이다.

left = {"read", "write"}
right = {"write", "read"}
print(left == right)
print(sorted(left))

# 출력
# True
# ['read', 'write']

아무 원소도 없는 집합은 공집합(empty set)이라고 부른다. Python에서는 set()으로 만든다. 빈 중괄호 {}는 집합이 아니라 키와 값을 짝지어 저장하는 딕셔너리다. 딕셔너리는 완성 코드에서 역할 이름으로 권한 집합을 찾아오는 데 사용한다.

부분집합은 필요한 것이 모두 들어 있는가를 묻는다

A의 모든 원소가 B에도 들어 있으면 A는 B의 부분집합(subset)이다. 기호로는 A ⊆ B라고 쓰며, Python에서는 A <= B로 확인한다. 집합에 사용하는 <=는 수의 크기를 비교하는 것이 아니라 원소의 포함 관계를 검사한다.

부분집합에는 같은 집합도 포함된다. 읽기가 필요한 작업을 읽기 권한만 가진 사용자가 실행할 수 있어야 하므로, 권한 검사에서는 이 성질이 자연스럽다. A가 B에 포함되면서 둘이 같지는 않을 때는 진부분집합(proper subset)이라고 하며 A < B로 검사한다.

required = {"read", "write"}
available = {"read", "write"}

print(required <= available)
print(required < available)
print(set() <= available)

# 출력
# True
# False
# True

공집합은 모든 집합의 부분집합이다. 빠진 원소가 있는지 찾아보아도 검사할 원소 자체가 없기 때문이다. 권한 요구가 빈 집합인 작업은 이 규칙만 적용하면 누구나 통과한다. 이것이 서비스의 의도와 맞는지는 별도로 정해야 한다. 수학 규칙이 로그인 필요 여부까지 결정해 주지는 않는다.

집합의 크기만 비교해서 부분집합인지 판단할 수는 없다. {"delete"}의 크기는 {"read", "write"}보다 작지만 delete가 그 안에 들어 있지는 않다. 포함 관계는 개수가 아니라 원소를 비교하는 관계다.

네 가지 연산으로 권한과 필터 계산하기

두 집합을 A와 B라고 하자. 연산을 읽을 때는 “어느 쪽에 들어 있는 원소를 남기는가”를 말로 풀면 된다. 전공 수업에서 쓰는 기호와 Python 표기를 함께 정리하면 다음과 같다.

집합 연산은 원소를 남기는 기준이 서로 다르다

이름	기호	Python	남기는 원소
합집합	A ∪ B	A | B	어느 한쪽에라도 있는 원소
교집합	A ∩ B	A & B	양쪽 모두에 있는 원소
차집합	A − B	A - B	A에 있으면서 B에는 없는 원소
여집합	U − A	universe - A	전체 범위 U에서 A에 없는 원소

합집합(union)은 역할별 허용 권한을 합칠 때 쓴다. 교집합(intersection)은 두 조건을 함께 만족하는 대상을 찾을 때 쓴다. 차집합(difference)은 후보에서 제외 대상을 뺄 때 쓴다. 여집합(complement)은 전체 범위를 먼저 정하고 그 안에서 나머지를 찾는 연산이다.

a = {"read", "write"}
b = {"read", "export"}
universe = {"read", "write", "export", "delete"}

print(sorted(a | b))
print(sorted(a & b))
print(sorted(a - b))
print(sorted(b - a))
print(sorted(universe - a))

# 출력
# ['export', 'read', 'write']
# ['read']
# ['write']
# ['export']
# ['delete', 'export']

합집합과 교집합은 양쪽을 바꿔도 결과가 같다. 차집합은 방향에 따라 달라진다. A − B는 A에서 출발하지만 B − A는 B에서 출발한다. “두 집합의 차이”라는 말만으로는 어느 계산을 원하는지 알기 어렵다. “허용 집합에서 금지 집합을 뺀다”처럼 출발점을 밝혀야 한다.

그림의 세 칸은 순서를 나타내지 않는다. A에만 있는 원소, 양쪽에 있는 원소, B에만 있는 원소를 구분한 것이다. 합집합은 세 칸을 모두 선택하고, 교집합은 가운데만 선택한다. A − B는 왼쪽 칸만 선택한다.

여집합에는 전체 범위가 필요하다

전체 범위를 전공 수업에서는 전체집합(universal set)이라고 부르며 U로 나타내곤 한다. “이 사용자에게 없는 권한”을 계산하려면 서비스에서 인정하는 모든 권한을 알아야 한다. 읽기와 쓰기만 있는 서비스인지, 삭제와 내보내기도 있는 서비스인지에 따라 결과가 달라진다.

allowed = {"read"}
small_universe = {"read", "write"}
large_universe = {"read", "write", "delete"}

print(sorted(small_universe - allowed))
print(sorted(large_universe - allowed))

# 출력
# ['write']
# ['delete', 'write']

Python의 집합에는 전체 범위를 자동으로 추론하는 여집합 연산이 없다. 전체집합을 변수로 두고 차집합을 계산한다. 수학에서 A의 여집합이라고 부르려면 A도 정해 둔 전체집합 안에 있어야 한다. 완성 코드는 역할 권한과 금지 권한이 전체집합의 부분집합인지 검사한다.

실무에서 만나는 곳

권한 계산에서 합집합은 “어느 역할에서든 허용하면 후보에 넣는다”를 표현한다. 차집합은 “금지한 권한은 후보에서 제거한다”를 표현한다. 필요한 권한이 모두 있는지는 부분집합으로 검사한다. 반대로 필요한 권한 중 하나만 있으면 되는 규칙은 교집합이 비어 있지 않은지 검사한다.

available = {"read"}
required = {"read", "export"}

print(required <= available)
print(bool(required & available))

# 출력
# False
# True

bool은 값이 비어 있는지 등을 참·거짓으로 바꾸는 Python 기본 함수다. 빈 집합은 False이고 원소가 있는 집합은 True다. 위 두 검사는 질문 자체가 다르다. 내보내기에 두 권한이 모두 필요하다면 첫 번째 검사를 써야 한다. 두 번째 검사를 쓰면 read만 가진 사용자도 통과한다.

검색 필터에도 같은 계산을 적용할 수 있다. 공개 문서 번호의 집합과 최근 수정된 문서 번호의 집합을 교집합으로 묶으면 두 조건을 함께 만족하는 문서를 얻는다. 제외 문서 번호의 집합을 빼면 숨길 문서를 제거할 수 있다. 이때 집합에 문서 전체 대신 문서 번호를 넣으면 비교 기준이 분명해진다.

데이터베이스에서 데이터를 조회하는 언어인 SQL을 읽을 때도 집합 관점이 도움이 된다. 다만 조회 결과가 언제나 수학적 집합인 것은 아니다. SQL 결과에는 같은 값이 여러 번 나타날 수 있으며, 중복을 유지하는 계산과 제거하는 계산을 구분해야 한다. Python에서도 리스트를 집합으로 바꾸면 반복 횟수 정보가 사라진다.

rows = ["read", "read", "write"]
unique_permissions = set(rows)

print(len(rows))
print(len(unique_permissions))

# 출력
# 3
# 2

따라서 접속 기록 세 건을 서로 다른 사용자 수로 바꾸는 일과, 접속 횟수 세 건을 그대로 세는 일은 다른 문제다. 집합을 선택하기 전에 중복이 불필요한지, 아니면 보존해야 할 정보인지 정한다.

멱집합으로 가능한 권한 묶음 만들기

어떤 집합의 모든 부분집합을 모은 집합을 멱집합(power set)이라고 부른다. A = {read, write}라면 가능한 부분집합은 {}, {read}, {write}, {read, write}다. 아무것도 선택하지 않은 경우와 모두 선택한 경우도 포함한다. 이를 기호로 P(A)라고 쓴다.

생성 방법은 선택을 하나씩 늘리는 것이다. 처음에는 빈 집합 하나만 준비한다. read를 처리할 때 기존 묶음을 그대로 둔 경우와 read를 추가한 경우를 만든다. 다음에 write를 처리할 때도 모든 기존 묶음에 같은 작업을 한다.

원소 하나를 처리할 때마다 묶음 수는 두 배가 된다. 기존 부분집합에는 아직 처리하지 않은 원소가 없으므로, 그 원소를 추가한 새 부분집합은 기존 것과 겹치지 않는다. 새 원소를 지우면 원래 부분집합을 알 수 있으므로 새로 만든 것끼리도 중복되지 않는다. 이 관찰이 생성 방법의 근거다.

원소가 n개인 유한집합의 부분집합 수는 2의 n제곱이다. Python에서는 2 ** n으로 쓴다. 빈 집합도 부분집합이 하나이므로 2 ** 0은 1이다. 원소가 10개면 1,024개, 20개면 1,048,576개다. 개별 집합을 만드는 비용까지 있으므로 전체 멱집합은 작은 입력에서만 생성하는 편이 적절하다.

Python의 변경 가능한 set은 다른 set의 원소로 직접 넣을 수 없다. 집합 원소는 저장 위치를 찾는 데 사용하는 해시값이 안정적으로 유지되는 형태여야 하기 때문이다. 이 장에서는 수학적 멱집합을 “부분집합들을 담은 리스트”로 표현한다. 각 부분집합은 set이고, 바깥 리스트는 출력 순서와 생성 순서를 관리한다. 바깥 자료형까지 수학 기호와 같게 만들 필요는 없다.

완성 코드의 생성 함수는 입력 원소를 정렬한 뒤 처리한다. 매 단계에서 새 부분집합을 별도 리스트에 모으고, 생성이 끝난 뒤 기존 목록에 붙인다. 현재 순회하는 목록을 그 자리에서 계속 늘리지 않는 것이 핵심이다.

완성 코드

아래 내용을 main.py로 저장한다. 외부 패키지나 입력 파일은 필요하지 않다. 권한 계산, 부분집합 검사, 여집합, 멱집합 생성을 한 번 실행하고 끝낸다. 집합을 보여 주는 함수가 원소를 정렬하므로 실행할 때마다 출력이 같다.

def format_set(items):
    return "{" + ", ".join(sorted(items)) + "}"


def calculate_permissions(role_permissions, assigned_roles, denied, universe):
    if not denied <= universe:
        raise ValueError("정의되지 않은 금지 권한")

    granted = set()
    for role in sorted(assigned_roles):
        if role not in role_permissions:
            raise ValueError("정의되지 않은 역할: " + role)
        permissions = role_permissions[role]
        if not permissions <= universe:
            raise ValueError("정의되지 않은 역할 권한")
        granted = granted | permissions

    return granted, granted - denied


def power_set(items):
    subsets = [set()]
    for item in sorted(items):
        additions = []
        for subset in subsets:
            additions.append(subset | {item})
        subsets.extend(additions)
    return subsets


def main():
    universe = {"read", "write", "export", "delete"}
    role_permissions = {
        "reader": {"read"},
        "writer": {"read", "write"},
        "operator": {"read", "export", "delete"},
    }
    assigned_roles = {"reader", "writer"}
    denied = {"write"}
    required = {"read", "export"}

    granted, effective = calculate_permissions(
        role_permissions, assigned_roles, denied, universe
    )
    missing = required - effective
    unavailable = universe - effective
    shared = role_permissions["writer"] & role_permissions["operator"]

    print("역할: " + ", ".join(sorted(assigned_roles)))
    print("역할 합산: " + format_set(granted))
    print("금지: " + format_set(denied))
    print("최종 권한: " + format_set(effective))
    print("역할 공통 권한: " + format_set(shared))
    print("요구 권한 충족: " + str(required <= effective))
    print("부족한 요구 권한: " + format_set(missing))
    print("전체 중 없는 권한: " + format_set(unavailable))

    base = {"read", "write"}
    subsets = power_set(base)
    assert len(subsets) == 2 ** len(base)
    assert all(subset <= base for subset in subsets)
    assert power_set(set()) == [set()]

    print("멱집합 개수: " + str(len(subsets)))
    for index, subset in enumerate(subsets, start=1):
        print(str(index) + ": " + format_set(subset))


if __name__ == "__main__":
    main()

줄별 해설

format_set의 반환문은 집합의 원소를 정렬하고 쉼표로 연결한다. join은 여러 문자열 사이에 지정한 구분자를 넣어 하나의 문자열을 만든다. 빈 집합은 연결할 내용이 없으므로 {}로 표시된다. 이것은 화면 표시 방식이며, 코드에서 빈 집합을 만드는 문법은 여전히 set()이다. 이 함수는 권한 이름처럼 문자열로 이루어진 집합을 대상으로 한다.

calculate_permissions는 역할별 권한 표, 사용자의 역할 집합, 금지 권한, 전체 권한을 받는다. 첫 번째 if는 금지 권한에 전체집합 밖의 이름이 있는지 검사한다. raise ValueError는 값에 문제가 있음을 알리고 실행을 중단하는 문장이다. 모르는 권한 이름을 조용히 무시하지 않도록 넣었다.

granted = set()은 아직 아무 역할에서도 권한을 얻지 않은 상태다. 반복문은 역할 이름을 하나씩 꺼낸다. 딕셔너리에 role in role_permissions를 적용하면 그 이름의 키가 있는지 검사한다. role_permissions[role]은 그 키에 연결된 권한 집합을 가져온다. 이어지는 부분집합 검사는 현재 계산에 참여하는 역할 권한이 전체 범위 안에 있는지 확인한다.

granted = granted | permissions는 지금까지 모은 권한과 이번 역할의 권한을 합친다. |는 새 집합을 만들므로 역할 표에 저장한 집합은 바뀌지 않는다. 함수의 마지막 줄은 합산 권한과 금지를 뺀 최종 권한을 함께 돌려준다. 호출하는 쪽에서는 granted, effective라는 두 이름으로 나누어 받는다.

power_set의 [set()]은 빈 리스트가 아니다. 빈 집합 하나가 들어 있는 리스트다. 따라서 입력이 비어 있어도 결과에는 공집합 하나가 남는다. subset | {item}은 기존 부분집합을 바꾸지 않고 새 원소를 포함한 집합을 만든다. append는 새 부분집합 하나를 목록 뒤에 붙이고, extend는 새 목록의 항목들을 기존 목록 뒤에 붙인다.

main의 딕셔너리는 역할 이름과 권한 집합을 연결한 표다. 여기서는 reader와 writer만 사용자의 역할로 지정한다. operator는 사용자의 역할이 아니며, 두 역할의 공통 권한을 계산하는 예에 사용한다. 최종 권한을 구한 뒤에는 요구 권한에서 최종 권한을 빼서 부족한 권한을 찾고, 전체집합에서 최종 권한을 빼서 없는 권한 전체를 찾는다.

required <= effective는 부족한 권한이 하나도 없는지 묻는 검사다. str은 참·거짓이나 정수를 출력용 문자열로 바꾼다. assert는 뒤의 조건이 거짓이면 실행을 멈추는 개발 중 확인 문장이다. all은 나열된 검사 결과가 모두 참인지 확인한다. 여기서는 개수, 포함 관계, 빈 입력의 결과를 점검한다. 이 세 조건만으로 모든 오류가 없다고 증명되는 것은 아니지만, 흔한 실수를 찾는 데 도움이 된다.

마지막 반복문의 enumerate는 항목에 번호를 붙여 꺼낸다. start=1은 표시 번호를 1부터 시작하라는 뜻이다. 파일 끝의 조건문은 이 파일을 직접 실행했을 때 main을 호출하는 Python의 관용적인 진입 코드다.

실행 결과

터미널에서 main.py가 있는 디렉터리로 이동한 뒤 실행한다.

python3 main.py

예상 출력은 다음과 같다.

역할: reader, writer
역할 합산: {read, write}
금지: {write}
최종 권한: {read}
역할 공통 권한: {read}
요구 권한 충족: False
부족한 요구 권한: {export}
전체 중 없는 권한: {delete, export, write}
멱집합 개수: 4
1: {}
2: {read}
3: {write}
4: {read, write}

부족한 요구 권한과 전체 중 없는 권한은 서로 다르다. 이번 작업에 필요한데 없는 것은 export뿐이다. delete와 write도 없지만 이번 작업의 요구에는 들어 있지 않다. 오류 안내에는 부족한 요구 권한을, 관리 화면에는 전체 중 없는 권한을 사용하는 식으로 목적에 맞게 구분할 수 있다.

실무에서 자주 틀리는 것

집합의 교집합 자리에 and를 쓴다

and는 집합의 공통 원소를 계산하지 않는다. 왼쪽 값이 비어 있지 않으면 오른쪽 값을 돌려준다. 다음 코드는 read가 공통 원소라는 기대와 달리 export까지 남긴다.

# 틀린 코드
a = {"read"}
b = {"read", "export"}
print(sorted(a and b))
# ['export', 'read']

# 고친 코드
print(sorted(a & b))
# ['read']

조건을 연결하는 연산과 집합을 계산하는 연산은 구별해야 한다. 합집합도 or가 아니라 |로 구한다.

금지를 제거한 뒤 다시 허용을 합친다

이 장의 규칙은 금지가 우선한다는 것이다. 금지 권한을 먼저 뺐더라도 뒤에서 다른 역할의 허용을 합치면 금지한 권한이 돌아올 수 있다.

first_role = {"read"}
second_role = {"write"}
denied = {"write"}

# 틀린 코드
wrong = (first_role - denied) | second_role
print(sorted(wrong))
# ['read', 'write']

# 고친 코드
correct = (first_role | second_role) - denied
print(sorted(correct))
# ['read']

집합 연산 자체가 잘못된 것은 아니다. 정책과 계산 순서가 맞지 않는 것이다. 먼저 모든 허용을 합산하고 마지막에 금지를 적용한다는 규칙을 함수 한곳에 모으면 호출 위치마다 다른 순서로 계산하는 일을 줄일 수 있다.

부분집합 검사를 개수 비교로 바꾼다

요구 권한이 더 적다고 해서 필요한 권한이 들어 있다는 뜻은 아니다. 원소 하나짜리 반례로도 차이를 확인할 수 있다.

required = {"delete"}
available = {"read", "write"}

# 틀린 코드
print(len(required) <= len(available))
# True

# 고친 코드
print(required <= available)
# False

개수 비교는 저장 공간이나 화면 표시량을 판단할 때 유용하지만, 권한 포함 여부를 대신하지 않는다. 비교 대상이 무엇인지 문장으로 적어 보면 적절한 연산을 고르기 쉽다.

멱집합에서 공집합을 빼먹는다

아무 권한도 선택하지 않는 경우도 가능한 권한 묶음이다. 다음의 틀린 코드는 입력이 하나일 때도 공집합을 빠뜨린다.

items = {"read"}

# 틀린 코드
wrong = [{item} for item in sorted(items)]
print(len(wrong))
# 1

# 고친 코드
subsets = [set()]
for item in sorted(items):
    additions = [subset | {item} for subset in subsets]
    subsets.extend(additions)
print(len(subsets))
# 2

대괄호 안의 식 for 이름 in 목록은 반복하면서 새 리스트를 만드는 리스트 내포 문법이다. 완성 코드의 내부 반복문을 짧게 쓴 것이다. 처음부터 원소별 한 개짜리 집합만 만들면 공집합뿐 아니라 여러 원소를 함께 고르는 경우도 놓친다.

한눈에 보기

질문을 먼저 정하면 필요한 집합 연산을 고르기 쉽다

질문	표현	확인할 점
이 권한이 있는가	"read" in allowed	원소 하나를 검사한다
필요한 권한이 모두 있는가	required <= allowed	같은 집합도 통과한다
어느 역할에서든 허용했는가	a | b	중복은 한 번만 남는다
두 조건을 모두 만족하는가	a & b	겹치는 원소만 남는다
후보에서 무엇을 제외하는가	candidates - denied	빼는 방향이 중요하다
전체 범위에서 무엇이 없는가	universe - allowed	전체집합을 먼저 정한다
가능한 모든 부분집합은 무엇인가	power_set(items)	빈 집합도 포함한다

집합은 중복 횟수와 순서를 버리는 대신 포함 관계와 묶음 계산을 분명하게 표현한다. 이 선택이 데이터의 의미에 맞는지가 먼저다. 다음 장에서 다룰 관계와 함수는 이렇게 모아 둔 대상 사이에 어떤 연결과 대응을 둘 것인지로 관심을 넓힌다.

연습 문제

1. A = {"read", "write"}, B = {"write", "delete"}일 때 합집합, 교집합, A − B, B − A를 정렬하여 출력하라. 차집합의 두 결과가 다른 이유를 설명하라.

2. 완성 코드의 사용자 역할을 {"writer", "operator"}로 바꾸고 금지 권한을 {"delete", "write"}로 바꾸라. 요구 권한은 그대로 둘 때 최종 권한과 충족 여부를 예상한 뒤 실행 결과와 비교하라.

3. 전체집합이 {"read", "write", "export"}이고 허용 권한이 {"read", "export"}일 때 여집합을 구하라. 전체집합에 "delete"를 추가하면 결과가 어떻게 달라지는지 코드로 확인하라.

4. 완성 코드의 power_set에 {"read", "write", "export"}를 전달하라. 부분집합 수를 확인하고, 그중 "read"를 포함하면서 "write"는 포함하지 않는 부분집합만 출력하라.

정답과 해설

집합 연산의 방향 확인

a = {"read", "write"}
b = {"write", "delete"}

print(sorted(a | b))
print(sorted(a & b))
print(sorted(a - b))
print(sorted(b - a))

# 출력
# ['delete', 'read', 'write']
# ['write']
# ['read']
# ['delete']

A − B는 A에서 write를 제거한 결과이고, B − A는 B에서 write를 제거한 결과다. 같은 원소를 제거해도 출발 집합이 다르므로 남는 원소가 다르다.

여러 역할과 금지 권한 계산

writer = {"read", "write"}
operator = {"read", "export", "delete"}
denied = {"delete", "write"}
required = {"read", "export"}

effective = (writer | operator) - denied
print(sorted(effective))
print(required <= effective)

# 출력
# ['export', 'read']
# True

합산 권한에는 네 권한이 모두 들어간다. delete와 write를 제거하면 export와 read가 남는다. 필요한 두 권한이 모두 있으므로 검사는 True다.

전체 범위가 달라지는 여집합

universe = {"read", "write", "export"}
allowed = {"read", "export"}

print(sorted(universe - allowed))
expanded_universe = universe | {"delete"}
print(sorted(expanded_universe - allowed))

# 출력
# ['write']
# ['delete', 'write']

허용 권한이 같아도 전체집합이 달라지면 여집합이 달라진다. 따라서 여집합 결과를 저장하거나 전달할 때는 어느 전체 범위를 기준으로 계산했는지 함께 알아야 한다.

멱집합에서 조건에 맞는 묶음 고르기

다음 코드는 완성 코드를 main.py로 저장한 뒤, 같은 디렉터리의 Python에서 실행할 수 있다. main.py를 가져올 때는 파일 끝의 조건문 덕분에 main 함수가 자동 실행되지 않는다.

from main import format_set, power_set

subsets = power_set({"read", "write", "export"})
print(len(subsets))
for subset in subsets:
    if "read" in subset and "write" not in subset:
        print(format_set(subset))

# 출력
# 8
# {read}
# {export, read}

read는 반드시 넣고 write는 반드시 빼므로 export를 넣을지 말지만 남는다. 따라서 조건을 만족하는 부분집합은 두 개다. 전체 멱집합을 만든 뒤 고르는 방식은 작은 예를 확인하는 데 편리하다. 실제 입력이 크다면 필요한 조건을 먼저 고정하여 생성해야 할 경우를 줄일 수 있다.