문제:

풀이방법:

 컬럼의 길이가 최대 8이므로 가능한 모든 경우의 조합을 다 따져보아도 문제가 없을 것이라고 생각했다.(최대 2^8=256개이기 때문이다.) 따라서 우선 check 함수를 통해서 유일성을 만족하는지 파악을 했다.

 유일성을 만족하는 조합을 기준으로 서로 비교하면서 최소성을 만족하는지 확인하였다. 이들을 집합이라고 생각한다면 (1)은 (1,2)의 부분집합이 되게 된다. 따라서 set에서 부분집합인지 확인해주는 내장함수는 issubset을 사용해서 부분집합인지 확인하였다. 그리고 해당하는 조합이 있다면 remove를 통해서 제거해줬다.

 그리고 남은 answer의 길이를 구함으로써 후보키의 갯수를 얻을 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def check(columns,tuples,relation):
    sets=set()
    for rel in relation:
        tup=''
        for col in columns:
            tup+=rel[col]
        sets.add(tup)
    if len(sets)==tuples:
        return True
    else:
        return False
 
 
def solution(relation):
    answer=[]
    import itertools
    columns=list(range(len(relation[0])))
    tuples=len(relation)
    for i in range(1,len(columns)+1):
        candidate=list(itertools.combinations(columns,i))
        for candi in candidate:
            if check(list(candi),tuples,relation):
                answer.append(list(candi))
    for i in answer[:]:
        for j in answer[:]:
            if i==j:
                continue
            if set(i).issubset(set(j)):
                answer.remove(j)
    return len(answer)
cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/42890

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1890. 점프  (0) 2019.10.04
[Programmers]2017 Kakao.다트 게임  (0) 2019.10.02
[Programmers]2018 Kakao.실패율  (0) 2019.09.30
[Programmers]2018 Kakao. 오픈채팅방  (0) 2019.09.29
[Programmers]2017 Kakao.비밀지도  (0) 2019.09.28

릴레이션의 특성

릴레이션은 동일한 튜플이 두 개 이상 존재하지 않는다. 또한 한 튜플의 각 애트리뷰트는 원자값을 가진다. 즉 리스트, 집합, 튜플 값이 들어갈 수 없는 것이다.

 

릴레이션의 키

각 투플을 고유하게 식별할 수 있는 하나 이상의 애트리뷰트들의 모임이다. 

슈퍼 키

한 릴레이션 내의 특정 투플을 고유하게 식벽하는 하나의 애트리뷰트 또는 애트리뷰트 집합이다. 예를 들면 신용카드 회사에서 고객 릴레이션에서 (신용카드번호, 주소) 또는 (주민등록번호)가 해당 된다. 하지만 투플들을 고유하게 식별하는데 꼭 필요하지 않은 애트리뷰트들을 포함할 수 있다.

 

후보 키 

각 투플을 고유하게 식별하는 최소한의 애트리뷰트들의 모임이며 앞으로 추가될 값도 생각해야 한다. 모든 릴레이션에는 최소한 한 개 이상의 후보 키가 있다. 

 

기본 키

한 릴레이션에 후보 키가 두 개 이상 있으면 설계자 혹은 데이터베이스 관리자가 이들 중에서 하나를 기본 키로 선정 한다. 만약 자연스러운 기본 키를 찾을 수 없다면 인덱스 번호와 같이 인위적인 키를 추가할 수 있다.

 

대체 키

기본 키가 아닌 후보키를 뜻한다.

 

외래 키

어떤 릴레이션의 기본 키를 참조하는 애트리뷰트이다. 여기서 어떤 릴레이션은 다른 릴레이션일수도 있고, 자신의 릴레이션일수도 있다. 관계 데이터베이스에서 릴레이션들 간의 관계를 나타내기 위해서 사용된다.

 

 

+ Recent posts