종합 - 코딩 테스트와 실무 문제에서 이산수학 찾기

이 장에서 배우는 것

개발 문제는 처음부터 집합이나 그래프라는 이름으로 주어지지 않는다. “이 역할들을 함께 부여해도 되는가”, “어느 작업부터 실행해야 하는가”, “식별자가 겹칠 가능성은 얼마나 되는가”처럼 업무의 말로 주어진다. 이 장에서는 그 말을 계산할 수 있는 대상으로 바꾼다. 앞 장에서 조건과 상태를 구분했듯이, 이번에는 대상과 제약을 구분하고 앞에서 익힌 도구를 골라 연결한다.

새로운 공식을 많이 추가하는 대신 세 문제를 끝까지 해결한다. 권한 조합은 집합과 경우의 수로, 의존성 순서는 그래프로, 충돌 확률은 충돌이 없는 경우의 확률로 계산한다. 코드를 쓰기 전에 무엇을 입력으로 받고 무엇을 정답으로 인정할지 정하는 과정도 함께 살펴본다.

• 업무 설명에서 대상, 관계, 제약, 구할 값을 찾아 수학 구조로 옮긴다.
• 역할의 권한을 합쳐 필수 권한을 충족하는 최소 역할 조합을 찾는다.
• 작업의 선행 조건을 지키는 실행 순서를 구하고 순환 때문에 막히는 경우를 확인한다.
• 충돌 확률을 정확한 분수로 계산하고 작은 전체 열거로 결과를 검산한다.

문제 상황

작은 데이터 처리 도구를 만든다고 하자. 사용자는 역할에 따라 자료를 읽거나 수정하고 검토한다. 서버에서는 자료 수집, 정리, 보고서 생성, 보관 작업을 실행한다. 처리 결과에는 정해진 개수의 후보 중 하나를 골라 식별자를 붙인다. 세 기능은 서로 달라 보이지만, 모두 “무엇을 하나의 대상으로 보고 어떤 조건을 검사할 것인가”를 정해야 구현할 수 있다.

첫 번째 요청은 “수정과 검토에 필요한 역할을 가장 적게 부여하라”다. 역할 수가 적다는 말과 권한 수가 적다는 말은 다르다. 이 장에서는 역할 개수를 최소화하고, 같은 개수의 답이 여러 개면 역할 이름을 정렬한 순서에서 먼저 발견한 답을 선택한다. 요청에 없는 권한을 함께 얻게 되는지도 별도로 보여 준다.

두 번째 요청은 “선행 작업이 끝난 뒤에 각 작업을 실행하라”다. 수집 이후에는 보관과 정리를 모두 시작할 수 있다. 따라서 가능한 실행 순서가 하나뿐이라고 가정하면 안 된다. 여기서는 실행 가능한 작업이 여러 개면 이름이 앞선 작업부터 고른다. 이 선택은 업무 우선순위가 아니라 결과를 일정하게 만드는 규칙이다.

세 번째 요청은 “후보가 네 개인 식별자를 세 번 발급하면 한 번이라도 겹칠 확률을 구하라”다. 매번 네 후보를 같은 확률로 고르고, 앞선 선택이 다음 선택에 영향을 주지 않는다고 가정한다. 실제 발급기가 이 조건을 만족하는지는 별개의 확인 사항이다. 계산 코드는 이 가정을 입력 크기와 함께 명확하게 드러내야 한다.

업무 문장을 계산 대상으로 바꾸기

먼저 입력, 조건, 출력으로 문장을 나눈다. 입력은 계산에 주어지는 자료다. 조건은 허용되는 답을 가르는 규칙이다. 출력은 우리가 실제로 구하려는 값이다. 전공 수업에서는 현실의 대상을 수학적 대상으로 바꾸는 일을 모델링(modeling)이라고 부른다. 이름보다 중요한 것은 코드가 다루지 않는 가정을 찾아내는 일이다.

세 요청을 입력과 조건, 출력으로 나누면 필요한 도구가 드러난다

요청	입력	조건	출력과 도구
권한 조합	역할별 권한, 필수 권한	필수 권한을 모두 포함	최소 역할 조합, 집합과 조합
의존성 순서	작업별 선행 작업	모든 선행 작업을 먼저 실행	실행 순서, 방향 그래프
충돌 확률	후보 수, 발급 횟수	독립적이고 균등한 선택	한 번 이상 충돌할 확률, 여사건

권한 조합에서는 선택 순서가 의미 없다. 검토 역할과 수정 역할을 고르는 것은 수정 역할과 검토 역할을 고르는 것과 같은 선택이다. 따라서 순서를 구별하는 나열 대신, 같은 역할 묶음을 한 번씩만 만드는 조합을 쓴다. 반대로 의존성 문제에서는 순서가 정답의 일부다. 같은 작업을 모두 포함해도 보고서를 정리보다 먼저 만들면 잘못된 답이다.

충돌 문제에서도 순서를 버리면 안 된다. 식별자 발급 결과가 A, A, B인 경우와 A, B, A인 경우는 서로 다른 발급 과정이다. 각 과정이 같은 확률을 가진다는 가정 아래에서 과정을 세어야 한다. 결과를 집합으로만 저장하면 중복이 사라져 충돌이 있었는지조차 복원하기 어렵다.

문제를 바꿔 적은 뒤에는 작은 반례를 만든다. 필수 권한이 비어 있으면 역할을 하나도 고르지 않는 것이 답이다. 작업 A와 B가 서로를 기다리면 실행 순서가 없다. 후보가 네 개인데 다섯 번 발급하면 중복은 반드시 생긴다. 이런 입력은 구현을 마친 뒤 덧붙이는 장식이 아니라, 함수가 지켜야 하는 약속을 구체화한다.

권한은 합치고, 의존성은 방향을 붙인다

역할 개수를 최소화하는 권한 조합

역할 하나가 가진 권한을 집합으로 저장한다. 여러 역할을 선택했을 때의 권한은 각 집합을 합친 합집합이다. 필수 권한이 이 합집합에 모두 들어 있으면 요구를 충족한다. Python 집합에서 required <= granted는 왼쪽의 모든 원소가 오른쪽에도 있는지 검사한다.

다만 요구 충족 여부만으로 최소 역할 수가 정해지지는 않는다. 역할을 0개 선택하는 경우부터 시작해 1개, 2개 순서로 검사한다. 처음 답을 발견한 크기가 최소다. 전공 수업에서는 가능한 후보를 빠짐없이 살펴보는 방법을 완전 탐색(exhaustive search)이라고 부른다. 이 예에서는 조합을 역할 수가 작은 순서대로 생성하므로 첫 답을 바로 반환해도 된다.

역할이 r개라면 각 역할을 선택하거나 선택하지 않을 수 있으므로 전체 부분집합은 2의 r제곱 개다. 이 숫자는 역할 수가 늘면 빠르게 커진다. 따라서 이 구현은 역할 종류가 적거나, 작은 입력에서 다른 구현의 답을 검증할 때 적합하다. 후보를 전부 검사한다는 구조 자체가 정확성의 근거지만, 큰 입력에서 빠르다는 근거가 되지는 않는다.

또한 여기서는 금지 권한이나 역할 간 충돌 규칙을 넣지 않는다. 필수 권한 충족과 최소 역할 수만 계산한다. 실제 요구에 “검토와 수정 역할을 동시에 부여하지 말라”가 있다면 선택한 역할 조합을 검사하는 조건을 추가해야 한다. 수학 구조를 고르는 것과 업무 규칙을 빠짐없이 옮기는 것은 함께 해야 하는 일이다.

선행 작업 수가 0인 작업부터 실행하기

작업을 점으로, 선행 작업에서 후속 작업으로 향하는 관계를 화살표로 나타낸다. 전공 수업에서는 점을 정점(vertex), 화살표를 방향 간선(directed edge)이라고 부른다. 예를 들어 수집이 끝나야 정리를 시작할 수 있다면 화살표는 수집에서 정리로 향한다.

코드의 입력은 반대쪽에서 읽기 편하게 저장한다. "clean": {"collect"}는 정리 작업이 수집을 기다린다는 뜻이다. 입력을 읽으면서 수집의 후속 작업 목록에 정리를 추가한다. 자료를 저장한 방향과 그림의 화살표 방향을 혼동하지 않아야 한다.

각 작업에 아직 끝나지 않은 선행 작업 수를 둔다. 처음에는 선행 작업 집합의 크기이며, 원래 그래프에서 들어오는 간선 수인 진입 차수(in-degree)와 같다. 선행 작업 수가 0인 작업을 실행하고, 그 작업을 기다리던 후속 작업의 수를 하나씩 줄인다. 모든 작업을 처리했다면 얻은 순서는 선행 관계를 지키는 위상 정렬(topological sort) 결과다.

처리한 작업 수가 전체보다 적다면 남은 작업을 시작할 수 없다. 선행 작업 이름이 모두 유효한 유한 그래프에서는 순환 때문에 이런 일이 생긴다. 다만 남은 작업 모두가 순환 위에 있는 것은 아니다. A와 B가 서로 기다리고 C가 B를 기다리면 C도 막히지만, C에서 출발해 C로 돌아오는 경로는 없다. 완성 코드의 오류 메시지는 이 차이를 지키기 위해 남은 항목을 “미처리 작업”이라고 부른다.

선행 작업 이름이 입력에 없는 경우도 따로 검사한다. 이는 순환과 다른 입력 오류다. 존재하지 않는 작업을 기다리는 상황을 순환이라고 보고하면 사용자는 잘못된 부분을 찾기 어렵다.

충돌 확률은 겹치지 않는 경우부터 계산한다

후보가 m개이고 n번 발급한다고 하자. 여기서 충돌은 발급 결과 중 같은 값이 한 번 이상 나오는 사건이다. 특정 두 번의 발급 결과가 같은 사건과는 다르다. 세 번 발급했을 때는 첫째와 둘째, 첫째와 셋째, 둘째와 셋째 중 어느 곳에서든 중복이 생길 수 있다.

충돌을 직접 세면 여러 쌍이 동시에 겹치는 경우를 중복해서 셀 수 있다. 대신 한 번도 겹치지 않는 확률을 구해 1에서 뺀다. 관심 있는 사건이 일어나지 않는 사건을 전공 수업에서는 여사건(complement)이라고 부른다.

첫 발급은 어떤 값을 골라도 된다. 두 번째는 앞에서 고른 한 값을 피해야 하므로 가능한 후보가 m − 1개다. 지금까지 i번 모두 달랐다면 다음에는 이미 사용한 i개를 피해야 한다. 따라서 n이 m 이하일 때 충돌 없는 확률은 다음 곱이다.

P(충돌 없음) = (m / m) × ((m − 1) / m) × … × ((m − n + 1) / m)

P(한 번 이상 충돌) = 1 − P(충돌 없음)

이 곱의 각 항은 앞선 선택에 중복이 없다는 조건 아래에서 다음 선택도 중복되지 않을 확률이다. 발급 결과들이 독립적이라는 가정이 있어도 “지금까지 중복이 없다”와 “다음에도 중복이 없다”라는 사건들을 조건 없이 독립으로 취급하는 것은 아니다.

후보가 4개이고 3번 발급하면 충돌 없는 확률은 1 × 3/4 × 2/4 = 3/8이다. 따라서 충돌 확률은 5/8이다. 후보보다 많이 발급하면 같은 후보를 두 번 이상 써야 하므로 확률은 1이다. 발급 횟수가 0이면 충돌할 쌍도 없으므로 확률은 0으로 정한다.

완성 코드에서는 표준 라이브러리의 Fraction을 쓴다. 분자와 분모를 정수로 보관하는 분수 자료형이다. 계산 중간에는 정확한 분수를 유지하고, 마지막에 화면에 보여 줄 때만 소수로 바꾼다. 작은 경우에는 가능한 발급 과정을 모두 만들어 계산 결과와 대조한다. 네 후보를 세 번 고르는 과정은 4 × 4 × 4 = 64개이므로 직접 확인하기에 충분히 작다.

완성 코드

아래 내용을 main.py로 저장한다. 사용하는 모듈은 모두 Python 3.12 이상 표준 라이브러리에 포함된다. 난수를 사용하지 않으며, 집합을 출력할 때는 정렬하므로 실행할 때마다 같은 결과가 나온다. 역할별 권한과 작업별 선행 조건을 저장하는 중괄호 자료는 이름에 값을 연결하는 사전이다. items()로 이름과 값을 함께 꺼낸다.

from fractions import Fraction
from itertools import combinations, product


def minimum_roles(roles, required):
    names = sorted(roles)
    for size in range(len(names) + 1):
        for chosen in combinations(names, size):
            granted = set()
            for name in chosen:
                granted.update(roles[name])
            if required <= granted:
                return chosen
    return None


def dependency_order(dependencies):
    names = set(dependencies)
    for task, parents in dependencies.items():
        unknown = parents - names
        if unknown:
            raise ValueError(
                f"{task}: 없는 선행 작업 {sorted(unknown)}"
            )

    remaining = {}
    following = {}
    for task in dependencies:
        remaining[task] = len(dependencies[task])
        following[task] = []

    for task, parents in dependencies.items():
        for parent in parents:
            following[parent].append(task)

    ready = sorted(
        task for task in dependencies if remaining[task] == 0
    )
    order = []
    while ready:
        task = ready.pop(0)
        order.append(task)
        for child in sorted(following[task]):
            remaining[child] -= 1
            if remaining[child] == 0:
                ready.append(child)
        ready.sort()

    if len(order) != len(dependencies):
        blocked = sorted(
            task for task in dependencies if remaining[task] > 0
        )
        raise ValueError(f"순환으로 미처리 작업: {blocked}")
    return order


def collision_probability(bucket_count, draw_count):
    if bucket_count <= 0 or draw_count < 0:
        raise ValueError("후보 수는 양수, 발급 횟수는 0 이상이어야 한다")
    if draw_count > bucket_count:
        return Fraction(1, 1)

    no_collision = Fraction(1, 1)
    for used in range(draw_count):
        no_collision *= Fraction(
            bucket_count - used, bucket_count
        )
    return 1 - no_collision


def enumerate_collision_probability(bucket_count, draw_count):
    if bucket_count <= 0 or draw_count < 0:
        raise ValueError("후보 수는 양수, 발급 횟수는 0 이상이어야 한다")
    collision_count = 0
    total_count = 0
    for sequence in product(range(bucket_count), repeat=draw_count):
        total_count += 1
        if len(set(sequence)) != len(sequence):
            collision_count += 1
    return Fraction(collision_count, total_count)


def main():
    roles = {
        "viewer": {"read"},
        "editor": {"read", "write"},
        "auditor": {"read", "audit"},
    }
    required = {"write", "audit"}
    chosen = minimum_roles(roles, required)
    assert chosen == ("auditor", "editor")

    granted = set()
    for name in chosen:
        granted.update(roles[name])
    print("권한 조합:", list(chosen))
    print("확보 권한:", sorted(granted))
    print("추가 권한:", sorted(granted - required))

    assert minimum_roles(roles, set()) == ()
    assert minimum_roles(roles, {"delete"}) is None

    dependencies = {
        "collect": set(),
        "clean": {"collect"},
        "report": {"clean"},
        "archive": {"collect"},
    }
    order = dependency_order(dependencies)
    print("실행 순서:", " -> ".join(order))
    assert dependency_order({}) == []

    cyclic = {
        "a": {"b"},
        "b": {"a"},
        "c": {"b"},
    }
    try:
        dependency_order(cyclic)
    except ValueError as error:
        print("의존성 오류:", error)
    else:
        raise AssertionError("순환을 발견하지 못했다")

    try:
        dependency_order({"report": {"missing"}})
    except ValueError:
        pass
    else:
        raise AssertionError("없는 선행 작업을 발견하지 못했다")

    exact = collision_probability(4, 3)
    counted = enumerate_collision_probability(4, 3)
    assert exact == counted == Fraction(5, 8)
    assert collision_probability(4, 0) == 0
    assert collision_probability(4, 1) == 0
    assert collision_probability(4, 5) == 1

    for buckets in range(1, 5):
        for draws in range(5):
            assert collision_probability(
                buckets, draws
            ) == enumerate_collision_probability(buckets, draws)

    print(f"충돌 확률: {exact} = {float(exact):.6f}")
    print("전체 열거:", counted)
    print("후보보다 많이 발급:", collision_probability(4, 5))
    print("검산: 통과")


if __name__ == "__main__":
    main()

줄별 해설

역할을 적게 고르는 줄부터 읽기

첫 두 줄은 분수, 조합, 반복 선택을 만드는 도구를 가져온다. combinations는 입력 원소 중 지정한 개수를 고른 묶음을 만든다. product는 각 자리에 후보를 반복해서 배치한 결과를 만든다. 두 도구는 비슷해 보여도 중복 선택과 순서를 다루는 방식이 다르다.

minimum_roles의 names = sorted(roles)는 사전의 역할 이름을 정렬한 리스트로 만든다. 이어지는 range(len(names) + 1)은 0부터 역할 전체 개수까지 검사한다. 0을 포함하므로 필수 권한이 비어 있는 경우 빈 조합을 반환할 수 있다.

chosen은 선택한 이름을 순서대로 담은 튜플이다. 튜플은 이 코드에서 내용을 바꾸지 않는 묶음으로 사용한다. granted.update(...)는 역할의 권한을 현재 집합에 합친다. 중복된 읽기 권한이 여러 번 들어와도 집합에는 한 번만 남는다.

required <= granted가 참인 첫 조합을 반환한다. 모든 크기를 검사해도 답이 없으면 None을 반환한다. 빈 튜플은 “역할을 고를 필요가 없다”이고 None은 “가능한 조합이 없다”이므로 의미가 다르다. 호출하는 쪽에서도 이 둘을 구별해야 한다.

기다리는 작업 수를 줄이는 줄 읽기

dependency_order의 첫 반복은 선행 작업 이름이 실제 작업 이름 집합 안에 있는지 확인한다. 차집합 parents - names에는 입력에 없는 이름만 남는다. 이 집합이 비어 있지 않으면 raise ValueError로 정상적인 결과 반환을 중단하고 입력 오류를 알린다.

remaining은 아직 기다리는 선행 작업 수를, following은 해당 작업이 끝나면 영향을 받는 후속 작업들을 저장한다. 두 자료는 같은 관계를 다른 목적으로 표현한다. 하나는 실행 가능 여부를 빠르게 확인하고, 다른 하나는 완료 후 갱신할 대상을 찾는다.

ready를 만드는 괄호 안 표현은 조건을 만족하는 작업 이름을 하나씩 내놓는다. 이를 생성기 표현식(generator expression)이라고 부른다. 여기서는 remaining[task] == 0인 이름만 골라 sorted에 넘긴다. 같은 표현을 빈 리스트와 for, if, append로 풀어 써도 된다.

ready.pop(0)은 이름순 첫 작업을 꺼낸다. 후속 작업의 남은 수를 줄여 0이 되면 준비 목록에 넣는다. 반복이 끝날 때마다 다시 정렬하므로 새로 준비된 작업도 다음 선택에 반영된다. 리스트 앞에서 꺼내기와 반복 정렬에는 비용이 든다. 이 구현은 흐름을 확인하기 쉬운 작은 예제용이며, 작업이 많으면 최소 원소를 효율적으로 꺼내는 자료구조를 검토할 수 있다.

마지막 길이 비교는 입력한 모든 작업을 처리했는지 확인한다. 실패하면 미처리 작업 이름을 정렬해 오류로 전달한다. 순환을 구성하는 정확한 경로를 찾는 함수는 아니므로 그 경로를 반환한다고 해석해서는 안 된다.

분수 계산과 검산 줄 읽기

collision_probability는 후보 수와 발급 횟수로 정수를 받는 함수다. 첫 조건은 후보 수가 0 이하이거나 발급 횟수가 음수인 입력을 거부한다. 이어서 후보보다 많이 발급하는 경우를 처리한다. 이 순서 덕분에 잘못된 후보 수를 확률 1로 처리하지 않는다.

no_collision은 곱셈을 시작할 값인 1이다. used는 앞에서 서로 다르게 고른 값의 수다. 매 반복에서 아직 쓰지 않은 후보 비율을 곱한다. 발급 횟수가 0이면 반복을 한 번도 하지 않으므로 충돌 없는 확률은 그대로 1이고, 반환하는 충돌 확률은 0이다.

enumerate_collision_probability는 같은 문제를 다른 방식으로 푼다. 발급 과정에서 중복을 제거한 길이가 원래 길이보다 짧으면 충돌이 있다. product는 발급 횟수가 0일 때 빈 과정 하나를 만들므로 전체 경우의 수가 0이 되지 않는다. 이 함수의 경우의 수는 후보 수의 발급 횟수 제곱이어서 작은 검산에만 쓴다.

assert는 뒤의 조건이 거짓이면 실행을 중단하는 확인문이다. main에서는 기대한 역할 조합, 빈 입력, 불가능한 요구, 충돌 확률을 검사한다. try와 except는 예상한 오류가 발생했을 때 이어서 실행할 코드를 지정한다. 오류가 발생하지 않은 경우에는 else에서 검산 실패를 알린다.

마지막 이중 반복은 후보 수 1부터 4, 발급 횟수 0부터 4까지 두 계산을 대조한다. 유한한 검산이 모든 입력에 대한 증명을 대신하지는 않는다. 다만 빈 입력과 작은 중복 사례에서 구현이 식의 의도와 일치하는지 확인한다. 마지막 조건문은 이 파일을 직접 실행할 때 main()을 호출한다.

실행 결과

터미널에서 파일을 저장한 디렉터리로 이동한 뒤 실행한다. 선택한 역할과 권한, 의존성 오류, 두 방식으로 계산한 확률이 다음과 같이 나온다.

python3 main.py

권한 조합: ['auditor', 'editor']
확보 권한: ['audit', 'read', 'write']
추가 권한: ['read']
실행 순서: collect -> archive -> clean -> report
의존성 오류: 순환으로 미처리 작업: ['a', 'b', 'c']
충돌 확률: 5/8 = 0.625000
전체 열거: 5/8
후보보다 많이 발급: 1
검산: 통과

보관이 정리보다 먼저 나온 이유는 두 작업이 모두 수집만 기다리고, 준비된 이름 중 archive가 먼저이기 때문이다. 이 순서가 보관을 먼저 해야 한다는 새 제약을 뜻하지는 않는다. 오류 출력의 C는 순환에 묶인 B를 기다려 처리하지 못한 작업이다.

실무에서 자주 틀리는 것

교집합으로 여러 역할의 권한을 합친다

다음 코드는 두 역할이 공통으로 가진 권한만 남긴다. 수정 역할과 검토 역할을 함께 주어도 읽기만 남는 반례가 생긴다.

editor = {"read", "write"}
auditor = {"read", "audit"}
granted = editor & auditor
print(sorted(granted))  # ['read']

함께 부여해서 얻는 권한은 합집합으로 계산한다. 반대로 두 역할 모두 허용하는 권한을 구하는 요구라면 교집합이 맞다. 연산 기호보다 먼저 질문을 확인해야 한다.

editor = {"read", "write"}
auditor = {"read", "audit"}
granted = editor | auditor
print(sorted(granted))  # ['audit', 'read', 'write']

정렬한 작업 이름을 실행 순서로 사용한다

이름 정렬은 선행 관계를 검사하지 않는다. 다음 입력에서는 이름순 첫 작업이 선행 작업보다 먼저 나온다.

dependencies = {
    "build": {"fetch"},
    "fetch": set(),
}
order = sorted(dependencies)
print(order)  # ['build', 'fetch']

완성 코드의 함수를 사용해 실행 가능한 작업 안에서만 이름순으로 고른다. 결과는 선행 조건을 지킨다.

dependencies = {
    "build": {"fetch"},
    "fetch": set(),
}
order = dependency_order(dependencies)
print(order)  # ['fetch', 'build']

각 쌍의 충돌 확률을 더해 정확한 값이라고 한다

네 후보를 세 번 고를 때 비교할 쌍은 세 개다. 각 쌍의 충돌 확률 1/4을 더하면 3/4이지만, 세 값이 모두 같은 경우가 여러 번 포함된다.

wrong = 3 * Fraction(1, 4)
print(wrong)  # 3/4

여사건을 이용하면 겹치는 충돌을 따로 분류하지 않아도 된다. 쌍별 확률의 합은 다른 용도로 활용할 수 있지만, 여기서 구하는 정확한 확률과 같지는 않다.

correct = collision_probability(4, 3)
print(correct)  # 5/8

답이 없는 경우와 빈 답을 같은 값으로 취급한다

빈 튜플도 조건문에서 거짓으로 평가된다. 따라서 다음 코드는 필수 권한이 없는 정상적인 요청을 실패로 표시한다.

chosen = minimum_roles({"viewer": {"read"}}, set())
if not chosen:
    print("해결 불가")  # 빈 조합인데 실패로 표시한다

불가능함을 나타내기로 약속한 값인 None만 검사한다. 그러면 빈 조합을 정상적인 결과로 출력할 수 있다.

chosen = minimum_roles({"viewer": {"read"}}, set())
if chosen is None:
    print("해결 불가")
else:
    print("선택:", list(chosen))  # 선택: []

한눈에 보기

문제의 표현과 구현, 작은 반례를 함께 기억한다

문제의 신호	수학 구조	코드의 핵심	먼저 확인할 반례
모두 포함해야 한다	부분집합, 합집합	required <= granted	필수 권한이 비어 있다
가장 적게 선택한다	조합의 크기	작은 크기부터 열거	가능한 선택이 없다
먼저 끝나야 한다	방향 그래프	남은 선행 작업 수를 감소	서로 기다리는 두 작업
한 번이라도 겹친다	여사건의 확률	1에서 비충돌 확률을 뺌	후보보다 많이 발급한다

실무에서 만나는 곳

권한 집합은 기능 접근 제어와 자료 필터를 검토할 때 만난다. 이번 예의 추가 권한 출력은 최소 역할 수를 골랐어도 필요 이상의 권한이 생길 수 있음을 보여 준다. 허용 권한의 범위까지 제한해야 한다면 필수 권한 집합과 별도로 최대 허용 권한 집합을 두어 검사해야 한다.

의존성 그래프는 파일 생성 순서, 배치 처리, 배포 준비 작업에서 나타난다. 이 장의 함수는 순서만 정한다. 작업의 실행 시간이나 동시에 실행할 수 있는 수를 계산하지는 않는다. 순서가 존재한다는 결론을 실행 시간이 짧다는 결론으로 확장하면 안 된다.

충돌 확률은 유한한 후보 공간에 식별자나 해시 결과를 배치할 때 사용한다. 해시는 입력을 정해진 범위의 값으로 바꾸는 계산이다. 여기의 확률을 적용하려면 출력이 후보들에 고르게 퍼지고 선택들이 독립적이라는 모델이 적절해야 한다. 충돌 검출 뒤 다시 발급하는 절차가 있다면 최종 저장 결과와 발급 시도의 충돌은 서로 다른 질문이다.

코딩 테스트에서도 같은 기준을 쓸 수 있다. 중복을 없애야 하면 집합을, 선행 관계가 있으면 그래프를 먼저 떠올린다. 이어서 입력 크기를 보고 전체 열거가 가능한지 판단한다. 문제 이름에 익숙한 단어가 보인다는 이유만으로 도구를 고르지 말고, 정답의 조건과 반례를 코드로 적어 선택을 확인한다.

연습 문제

1. 역할에 "operator": {"read", "write", "audit", "delete"}를 추가하라. 필수 권한이 그대로일 때 최소 역할 조합과 추가 권한을 예측한 뒤 확인하라. 추가 권한 중 delete를 허용하지 않으면 어떻게 검사해야 하는지도 적어라.
2. 작업 입력을 {"a": {"b"}, "b": {"a"}, "c": {"b"}, "d": set()}로 바꾸라. 완료할 수 있는 작업과 미처리 작업을 구별하고, 미처리 작업 전체를 순환의 구성원이라고 부르면 안 되는 이유를 설명하라.
3. 후보가 5개이고 3번 발급할 때 충돌 확률을 분수로 구하라. 완성 코드의 두 확률 함수를 사용해 결과가 같은지 확인하라.
4. 성공한 실행 순서가 모든 선행 관계를 지키는지 검사하는 함수를 작성하라. 각 작업의 순서상 위치를 저장하고, 선행 작업의 위치가 후속 작업보다 작은지 검사하라. 작업 누락이나 중복도 거부하라.

정답과 해설

역할 수 최소화와 권한 제한은 다른 조건이다

새 역할 하나가 필수 권한을 모두 포함하므로 최소 조합은 ("operator",)다. 추가 권한은 이름순으로 ['delete', 'read']다. 삭제 권한을 금지한다면 첫 답을 구한 뒤 거절하는 것만으로 끝내지 않고, 후보 검사 단계에서 금지 권한을 가진 조합을 건너뛰어 다음 답을 찾아야 한다.

roles = {
    "viewer": {"read"},
    "editor": {"read", "write"},
    "auditor": {"read", "audit"},
    "operator": {"read", "write", "audit", "delete"},
}
required = {"write", "audit"}
assert minimum_roles(roles, required) == ("operator",)

forbidden = {"delete"}
names = sorted(roles)
answer = None
for size in range(len(names) + 1):
    for chosen in combinations(names, size):
        granted = set()
        for name in chosen:
            granted.update(roles[name])
        if required <= granted and not (granted & forbidden):
            answer = chosen
            break
    if answer is not None:
        break

assert answer == ("auditor", "editor")

이 코드는 완성 코드의 함수 정의 아래에서 실행할 수 있다. 최소화할 대상은 여전히 역할 수지만, 허용할 후보의 조건이 하나 늘었다. 허용 조건을 바꾸면 정답도 바뀐다.

순환의 영향은 바깥 작업까지 이어진다

D는 선행 작업이 없으므로 처리된다. A와 B는 서로 기다리고, C는 B가 끝나지 않아 기다린다. 따라서 오류에 담기는 미처리 작업은 A, B, C다. 순환을 직접 이루는 것은 A와 B이며 C는 그 영향으로 막힌다.

assert dependency_order({"d": set()}) == ["d"]

try:
    dependency_order({
        "a": {"b"},
        "b": {"a"},
        "c": {"b"},
        "d": set(),
    })
except ValueError as error:
    assert str(error) == "순환으로 미처리 작업: ['a', 'b', 'c']"
else:
    raise AssertionError("순환을 발견하지 못했다")

현재 함수는 실패하면 부분 순서를 반환하지 않는다. 부분적으로 완료 가능한 작업까지 보고해야 하는 요구라면 반환 형식에 완료 목록과 미처리 목록을 함께 담도록 설계를 바꿀 수 있다.

후보 다섯 개에서 세 번 발급하기

충돌 없는 확률은 1 × 4/5 × 3/5 = 12/25다. 따라서 충돌 확률은 13/25다. 전체 125개 과정 중 충돌이 없는 과정은 60개이고, 충돌이 있는 과정은 65개다.

exact = collision_probability(5, 3)
counted = enumerate_collision_probability(5, 3)
assert exact == counted == Fraction(13, 25)

두 함수의 답이 같은 것은 유용한 검산이다. 다만 전체 열거를 큰 후보 수에 적용하면 경우의 수가 빠르게 늘어난다. 실제 계산에는 곱셈 공식을 사용하고 전체 열거는 작은 입력에 남겨 둔다.

정답을 만드는 코드와 검사하는 코드 나누기

작업 이름의 집합만 비교하면 같은 작업이 두 번 들어간 순서를 놓칠 수 있다. 길이와 집합을 함께 검사한 뒤 각 선행 관계를 확인한다. 아래 함수는 존재하지 않는 선행 작업도 거부한다.

def valid_order(dependencies, order):
    if len(order) != len(dependencies):
        return False
    if set(order) != set(dependencies):
        return False

    position = {}
    for index, task in enumerate(order):
        position[task] = index

    for task, parents in dependencies.items():
        for parent in parents:
            if parent not in position:
                return False
            if position[parent] >= position[task]:
                return False
    return True


sample = {"fetch": set(), "build": {"fetch"}}
assert valid_order(sample, ["fetch", "build"])
assert not valid_order(sample, ["build", "fetch"])
assert not valid_order(sample, ["fetch", "fetch"])
assert not valid_order(sample, ["fetch"])

enumerate는 리스트의 위치 번호와 원소를 함께 꺼내는 내장 함수다. 이 검사는 특정한 이름순 결과를 강제하지 않는다. 작업이 빠짐없이 한 번씩 나오고 모든 선행 조건을 지키면 유효한 답으로 인정한다. 문제를 푸는 절차와 답이 맞는 조건을 나누어 적으면, 구현을 바꾸더라도 같은 기준으로 결과를 확인할 수 있다.