문제 보기 · Level 2 · 2019 KAKAO BLIND RECRUITMENT · 정답률 43% · 푼 사람 11,981명 (2026-09-30 기준)1
문제
릴레이션(표)이 2차원 문자열 배열로 주어진다. 후보 키는 모든 행을 구별할 수 있으면서(유일성), 속성을 하나라도 빼면 구별할 수 없게 되는(최소성) 속성 집합이다. 후보 키의 개수를 돌려준다.
- 열 1~8개, 행 1~20개
- 같은 행은 없다
풀이
막히면 한 단계씩 펼친다2.
필요한 개념
- 완전탐색: 열의 모든 부분집합(최대 2⁸ = 256개)을 확인한다.
- 비트 연산과 비트마스크: 부분집합과 “이미 찾은 키를 품었나”를 다루는 방법.
- 함수의 성질과 집합의 크기: 유일성은 “행 → 고른 열 값” 함수가 단사(서로 다른 행이 서로 다른 값으로 감)라는 뜻이다. 행 수가 유한하니 값의 종류 수가 행 수와 같은지만 보면 된다.
- 집합: 최소성은 “진부분집합 가운데 모든 행을 구별하는 것이 없다”는 뜻이다. 열을 더 넣어도 유일성은 깨지지 않으니, 문제의 “하나라도 빼면 구별 못 함”과 같은 말이다.
1단계 · 작은 예로 손으로 풀기
열이 [번호, 이름, 학과]이고 행이 (1, kim, A), (2, lee, A), (3, kim, B)라고 하자.
- {번호}: 모두 다르다 → 유일. 더 뺄 것이 없다 → 후보 키
- {이름}: kim이 두 번 → 구별 못 함
- {학과}: A가 두 번 → 구별 못 함
- {이름, 학과}: (kim, A), (lee, A), (kim, B) 모두 다르다 → 유일. 하나를 빼면 구별 못 함 → 후보 키
- {번호, 이름}: 유일하지만 {번호}만으로도 된다 → 최소성 탈락
답은 2다.
2단계 · 가장 단순한 방법과 그 속도
열이 최대 8개라 부분집합은 2⁸ − 1 = 255개다. 하나를 확인하는 데 행 20개를 튜플로 만들어 집합에 넣으면 되니, 모두 수천 번이다. 모두 해 봐도 된다.
3단계 · 핵심 아이디어
- 유일성: 고른 열만 뽑아 행마다 튜플로 만든다. 튜플들의 집합 크기가 행 수와 같으면 모든 행이 구별된다.
- 최소성: 부분집합을 크기가 작은 것부터 본다. 이미 찾은 후보 키를 통째로 품은 집합은 건너뛴다. 크기 순으로 보면, 어떤 집합의 더 작은 부분집합이 유일하다면 그것(또는 그 안의 키)이 이미 키로 뽑혀 있기 때문에 이 규칙만으로 최소성이 지켜진다. 후보 키는 유일한 열 집합들 가운데 부분집합 관계로 더 작은 것이 없는 원소(극소 원소)이고, 크기 순은 이 관계를 거스르지 않는 줄 세우기(선형 확장)다(부분순서와 위상 정렬).
4단계 · 코드 흐름
- 찾은 키 목록을 비워 둔다.
- 크기 1부터 열 수까지, 그 크기의 열 조합마다:
- 찾은 키 중 하나라도 이 조합에 모두 들어 있으면 건너뛴다.
- 유일하면 키 목록에 넣는다.
- 키 목록의 길이를 돌려준다.
5단계 · 파이썬 코드
from itertools import combinations
def solution(relation):
rows, cols = len(relation), len(relation[0])
keys = []
for size in range(1, cols + 1):
for combo in combinations(range(cols), size):
if any(set(k) <= set(combo) for k in keys): # 이미 찾은 키를 품으면 탈락
continue
seen = {tuple(row[c] for c in combo) for row in relation}
if len(seen) == rows: # 모든 행이 구별된다
keys.append(combo)
return len(keys)
combinations(range(cols), size): 열 번호 size개를 고르는 모든 경우다.set(k) <= set(combo): k의 열이 모두 combo에 들어 있는지(부분집합인지) 본다.tuple(row[c] for c in combo): 한 행에서 고른 열 값만 뽑아 튜플로 만든다. 튜플이라 집합에 넣을 수 있다.
비트마스크로 쓰면 조합을 수 하나로 다룬다. 키 k가 조합 m 안에 있는지는 k & m == k다(비트마스크). 다만 크기 순으로 돌기 위해 sorted(range(1, 1 << cols), key=lambda m: bin(m).count("1"))처럼 켜진 자리 수로 정렬해야 한다.
6단계 · 실행 추적
문제의 예시(열: 학번, 이름, 전공, 학년 / 행 6개)
| 크기 | 조합 | 결과 |
|---|---|---|
| 1 | {학번} | 유일 → 키 |
| 1 | {이름}, {전공}, {학년} | 겹침 있음 |
| 2 | {학번, …} | 학번을 품어서 건너뜀 |
| 2 | {이름, 전공} | 유일 → 키 |
| 2 | {이름, 학년}, {전공, 학년} | 겹침 있음 |
| 3 | {이름, 전공, 학년} | {이름, 전공}을 품어서 건너뜀 |
답은 2다.
7단계 · 복잡도와 흔한 실수
부분집합 2ᶜ개마다 행 R개 × 열 C개를 보니 \(O(2^C \cdot R \cdot C)\)다(C ≤ 8, R ≤ 20).
- 최소성을 문자열 포함으로 검사한다. 키 “13”(열 1, 3)이 조합 “123”에 들어 있는지
"13" in "123"로 보면 거짓이 나온다. 집합이나 비트마스크로 본다. - 크기 순이 아닌 순서로 보면, 큰 집합을 먼저 키로 뽑은 뒤 그 안의 작은 키를 나중에 찾게 된다.
검증: 문제의 예시를 통과했고, 무작위 표 2,000개에서 “모든 부분집합마다 유일한지, 그리고 한 열을 뺀 부분집합이 모두 유일하지 않은지”를 정의 그대로 확인하는 풀이와 결과가 같았다 — 16_pg42890_p1.py