2019 KAKAO BLIND RECRUITMENT 후보키

1. 문제 정의: 후보 키란 무엇인가?

후보 키는 데이터베이스에서 유일하게 각 행(row)을 식별할 수 있는 최소한의 속성(attributes) 집합을 의미합니다. 예를 들어, 학생 데이터베이스에서 학번 필드는 학생 개개인을 식별할 수 있는 후보 키가 될 수 있습니다. 이 포스팅에서는 후보 키를 찾는 문제를 파이썬으로 해결하는 방법을 설명하겠습니다.

2. 접근 방법: 효율적인 후보 키 찾기 전략

후보 키를 찾기 위해서는 두 가지 조건을 만족해야 합니다.

1. 유일성: 특정 속성 집합으로 모든 레코드를 유일하게 식별할 수 있어야 합니다.
2. 최소성: 후보 키 집합에서 하나의 속성을 제거하면 유일성을 잃어야 합니다.

효율적으로 후보 키를 찾기 위해 모든 속성의 조합을 만들고, 각 조합이 위 두 조건을 만족하는지 확인해야 합니다. 여기서는 비트마스크를 사용해 각 속성 조합을 빠르게 생성하고 확인하는 방식을 사용합니다.

3. 코드 설명
후보 키 유일성 검사 (is_unique 함수)
우선, 속성의 조합이 유일성을 만족하는지 확인하는 is_unique 함수를 구현했습니다. 각 속성 조합을 키로 사용하여 튜플을 생성하고, 이 튜플이 중복되는지 검사합니다.

def is_unique(relation,attribute):
    check = set()
    for Tuple in relation:
        key = tuple(Tuple[i] for i in attribute)
        if key in check:
            return False
        check.add(key)
    return True

1. 주어진 속성 attribute로 튜플을 만들고, 집합(set)에 추가합니다.
2. 만약 이미 같은 키가 존재한다면 유일성이 깨지므로 False를 반환합니다.
3. 모든 키가 유일하다면 True를 반환하여 유일성을 만족한다고 판단합니다

후보 키 최소성 검사 및 비트마스크 활용

후보 키의 최소성을 만족하려면, 후보 키 목록에 이미 포함된 속성 집합의 부분 집합이 되어서는 안 됩니다. 비트마스크를 사용하면 속성 조합을 효율적으로 표현하고, 각 조합의 부분 집합 여부를 빠르게 확인할 수 있습니다

def solution(relation):
    candidate = []
    degree = len(relation[0])
    for i in range(1,  1 << degree):
        attribute = [idx for idx in range(degree) if i & (1 << idx)]
        if any(set(c).issubset(attribute) for c in candidate):
            continue
        
        if is_unique(relation, attribute):
            candidate.append(attribute)
            
    return len(candidate)

• 비트마스크: 1 << degree를 사용하여 degree 길이의 모든 조합을 생성합니다. i & (1 << idx)를 통해 비트가 1로 설정된 위치의 속성만 선택합니다.
• 최소성 검사: any(set(c).issubset(attribute) for c in candidate)를 통해, 이미 선택된 후보 키의 부분 집합인지 확인합니다.
• 유일성 검사: is_unique(relation, attribute) 함수를 통해 속성 조합이 유일성을 만족하는지 검사합니다.