습관처럼
programmers [C++] : 2019 KAKAO BLIND RECRUITMENT 후보키 본문
programmers [C++] : 2019 KAKAO BLIND RECRUITMENT 후보키
dev.wookii 2020. 6. 26. 16:49programmers.co.kr/learn/courses/30/lessons/42890
문제 설명
인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다.
후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.
관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
- 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
- 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.
학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라.
접근 방식
처음 잘못 접근했을 때에는 단하나의 속성만으로 최소성 유일성을 갖는 단일 후보키를 제외합니다. 조합을 통해서 2개, 3개...(단일 후보키를 제외하고 만들 수 있는 최대 후보키 크기만큼)로 구성되는 후보키 조합을 만들어 각각 최소성과 유일성을 만족할때 다음 크기의 후보키에서 해당 후보키에 속한 column을 모두 제외하고 탐색을 진행했습니다. 하지만 한번에 성공하는 법이 없네요....
뭐가 잘못되었는지 몰랐는데 예외가 있더라구요~ 예를 들어 보죠 {1,2,3} 으로 이루어진 후보키가 있다고 가정해보죠 하지만 {1,2,4,5}가 후보키가 될 수 있죠..저는 여기서 {1,2}을 제외하고 탐색을 진행했으니 ^^;;;; 올바른 방법을 설명해드리겠습니다.
1. 단일 후보키를 제외하는 것까지는 동일하게 진행한다.
2. 조합을 선정할때 모든 조합을 먼저 구한다.
3. *** 조합에 대한 후보키 적합도를 판단할때 후보키가 된다면 조합 중에서 후보키의 일부가 아닌 모든 요소가 다 들어가 있는 조합을 제외합니다.
코드
[오류 코드]
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int row,col;
int answer = 0;
vector<int>v;
int cnt=1;
void isCandinate(vector<int>combi,vector<vector<string>> relation){
vector<string>temp;
for(int i=0;i<row;i++){
string a="";
for(int j=0;j<combi.size();j++){
a+=relation[i][combi[j]];
a+=" ";
}
temp.push_back(a);
}
sort(temp.begin(),temp.end());
temp.erase(unique(temp.begin(),temp.end()),temp.end());
vector<int>v1;
if(temp.size()==row){
answer++;
for(int i=0;i<v.size();i++){
int flag=0;
for(int j=0;j<combi.size();j++){
if(combi[j]==v[i]){
flag=1;
break;
}
}
if(flag==0)v1.push_back(v[i]);
}
v.clear();v=v1;
}
}
void combination(int c,vector<int>v1,vector<vector<string>> relation){
vector<int>combi;
vector<int>temp;
for(int i=0;i<c;i++)temp.push_back(1);
for(int i=0;i<v1.size()-c;i++)temp.push_back(0);
sort(temp.begin(),temp.end());
do{
combi.clear();
for(int i=0;i<temp.size();i++){
if(temp[i]==1){
combi.push_back(v1[i]);
}
}
isCandinate(combi,relation);
}while(next_permutation(temp.begin(),temp.end()));
cnt++;
cout<<cnt<<" "<<v.size()<<"\n";
if(v.size()==0||v.size()<cnt)return;
else{
combination(cnt,v,relation);
}
}
int solution(vector<vector<string>> relation) {
row=relation.size();
col=relation[0].size();
vector<string>temp,temptemp;
for(int i=0;i<col;i++){
temp.clear();temptemp.clear();
for(int j=0;j<row;j++){
temp.push_back(relation[j][i]);
}
temptemp=temp;
sort(temptemp.begin(),temptemp.end());
temptemp.erase(unique(temptemp.begin(),temptemp.end()),temptemp.end());
if(temptemp.size()==row){answer++;continue;}
else{
v.push_back(i);
}
}
cnt++;
if(v.size()==0)return col;
else{
combination(cnt,v,relation);
}
return answer;
}
[바른 코드]
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
int row,col;
int answer = 0;
vector<int>v;
vector<string>combi;
int cnt=1;
bool compare(string a,string b){
if(a.length()!=b.length())return a.size()<b.size();
return a<b;
}
void isCandinate(vector<vector<string>> relation){
vector<string>temp;
for(int k=0;k<combi.size();k++){
if(combi[k].compare("-")==0)continue;
temp.clear();
for(int i=0;i<row;i++){
string a="";
for(int j=0;j<combi[k].size();j++){
a+=relation[i][int(combi[k][j])-48];
a+=" ";
}
temp.push_back(a);
}
sort(temp.begin(),temp.end());
temp.erase(unique(temp.begin(),temp.end()),temp.end());
if(temp.size()==row){
answer++;
int Size=combi.size();
for(int i=0;i<Size;i++){
if(i==k)continue;
int count=0;
for(int l=0;l<combi[i].size();l++){
for(int m=0;m<combi[k].size();m++){
if(combi[i][l]==combi[k][m])count++;
}
}
if(count==combi[k].size()){
combi[i]="-";
}
}
}
}
}
void combination(int c,vector<int>v1,vector<vector<string>> relation){
vector<int>temp;
for(int i=c;i<=v1.size();i++){
temp.clear();
for(int j=0;j<i;j++)temp.push_back(1);
for(int j=0;j<v1.size()-i;j++)temp.push_back(0);
sort(temp.begin(),temp.end());
do{
string s="";
for(int k=0;k<temp.size();k++){
if(temp[k]==1){
s+=to_string(v1[k]);
}
}
combi.push_back(s);
}while(next_permutation(temp.begin(),temp.end()));
}
sort(combi.begin(),combi.end(),compare);
isCandinate(relation);
}
int solution(vector<vector<string>> relation) {
row=relation.size();
col=relation[0].size();
vector<string>temp,temptemp;
//단일제거
for(int i=0;i<col;i++){
temp.clear();temptemp.clear();
for(int j=0;j<row;j++){
temp.push_back(relation[j][i]);
}
temptemp=temp;
sort(temptemp.begin(),temptemp.end());
temptemp.erase(unique(temptemp.begin(),temptemp.end()),temptemp.end());
if(temptemp.size()==row){answer++;continue;}
else{
v.push_back(i);
}
}
if(v.size()==0)return col;
else combination(cnt+1,v,relation);
return answer;
}
funny algorithm0_<
'Algorithms > programmers' 카테고리의 다른 글
programmers [C++] : 2018 KAKAO BLIND RECRUITMENT 압축 (0) | 2020.06.29 |
---|---|
programmers [C++] : 2018 KAKAO BLIND RECRUITMENT 방금그곡 (0) | 2020.06.27 |
programmers [C++] : 2019 KAKAO BLIND RECRUITMENT 오픈채팅방 (0) | 2020.06.24 |
programmers [C++] : 2018 KAKAO BLIND RECRUITMENT 캐시 (0) | 2020.06.24 |
programmers [C++] : 2018 KAKAO BLIND RECRUITMENT 프렌즈 블록 (0) | 2020.06.23 |