SELECT b.ANIMAL_ID, b.NAME
FROM ANIMAL_INS a RIGHTJOIN ANIMAL_OUTS b on a.ANIMAL_ID = b.ANIMAL_ID
WHERE a.ANIMAL_ID ISNOTNULLAND a.DATETIME > b.DATETIME
ORDERBY a.DATETIME
기존에 후보키였던 것을 포함한다면, 지금 검사하는 칼럼의 인덱스는 최소성을 만족하지 못하므로 return
기존에 후보키였던 것을 포함하지 않는다면,
vector<vector<string>> relation의 모든 레코드에 대해 칼럼의 인덱스의 값들을 추출해서, 한 vector<string>으로 잡는다. 잡은 vector<string>을 vector<vector<string>>에 넣는다.
모두 넣고, 일일히 대조해서 처음부터 끝까지 일치하는지 확인한다.
일치하는게 있다면, 후보키가 되지 못하므로 return
일치하는게 없다면, 후보키가 될 수 있다.
조금 말이 어려운데, 코드를 보면서 이해해보자.
아래 코드는 후보키의 가짓수를 토대로 dfs를 돌리는 함수다.
vector<vector<string>> rel;
// answer는 후보키의 vector를 저장한다.
vector<vector<int>> answer;
int col, row, arr[21];
intsolution(vector<vector<string>> relation){
row = relation.size();
col = relation[0].size();
rel = relation;
// i는 후보키의 가짓수for(int i = 1; i <= col; i++){
// arr은 칼럼의 인덱스를 저장할 예정.memset(arr, 0, sizeof(arr));
dfs(i, 0, -1);
}
return answer.size();
}
아래 코드는 조합을 시행하는 dfs다.
// 벡터 a와 벡터 b가 모두 같은 원소를 가지고 있는지 판단하는 함수다.boolvector_is_equal(vector<string> a, vector<string> b){
int vec_size = a.size();
for(int i = 0; i < vec_size; i++){
if(a[i] != b[i]) returnfalse;
}
returntrue;
}
// goal : 나는 인덱스를 goal개 만큼 집기로 했다.// cnt : 나는 인덱스를 cnt개 만큼 집었다.// idx : 나는 인덱스를 idx까지 골랐었다.voiddfs(int goal, int cnt, int idx){
// 조합을 통해 모두 집었다면,if(goal == cnt){
// 기존에 찾아놓은 후보키를 포함하고 있는 지 검사for(auto i : answer){
int ans_idx = 0;
for(int j = 0; j < goal; j++){
if(i[ans_idx] == arr[j]) ans_idx++;
if(ans_idx >= i.size()) break;
}
if(ans_idx >= i.size()) return;
}
// 후보키가 될 수 있는지 검사할 예정// vector<vector<string>> relation에서 골라놓은 인덱스를 저장해놓은 arr에 존재하는 인덱스대로 하나의 tmp 벡터를 만들고, 이를 cmp 벡터에 넣어준다.
vector<vector<string>> cmp;
for(int i = 0; i < row; i++){
vector<string> tmp;
for(int j = 0; j < goal; j++)
tmp.push_back(rel[i][arr[j]]);
cmp.push_back(tmp);
}
// 비교하는 과정for(int i = 0; i < row; i++){
for(int j = i + 1; j < row; j++){
// 벡터가 하나라도 같은 게 있으면 후보키가 되지 못함if(vector_is_equal(cmp[i], cmp[j])) return;
}
}
// 벡터가 모두 다르므로 후보키가 될 수 있다.
vector<int> answer_temp;
for(int i = 0; i < goal; i++)
answer_temp.push_back(arr[i]);
answer.push_back(answer_temp);
}
// 다음 조합 진행else {
for(int i = idx + 1; i < col; i++){
arr[cnt] = i;
dfs(goal, cnt + 1, i);
}
}
}
코드
#include<bits/stdc++.h>usingnamespace std;
vector<vector<string>> rel;
vector<vector<int>> answer;
int col, row, arr[21];
boolvector_is_equal(vector<string> a, vector<string> b){
int vec_size = a.size();
for(int i = 0; i < vec_size; i++){
if(a[i] != b[i]) returnfalse;
}
returntrue;
}
voiddfs(int goal, int cnt, int idx){
if(goal == cnt){
for(auto i : answer){
int ans_idx = 0;
for(int j = 0; j < goal; j++){
if(i[ans_idx] == arr[j]) ans_idx++;
if(ans_idx >= i.size()) break;
}
if(ans_idx >= i.size()) return;
}
vector<vector<string>> cmp;
for(int i = 0; i < row; i++){
vector<string> tmp;
for(int j = 0; j < goal; j++)
tmp.push_back(rel[i][arr[j]]);
cmp.push_back(tmp);
}
for(int i = 0; i < row; i++){
for(int j = i + 1; j < row; j++){
if(vector_is_equal(cmp[i], cmp[j])) return;
}
}
vector<int> answer_temp;
for(int i = 0; i < goal; i++)
answer_temp.push_back(arr[i]);
answer.push_back(answer_temp);
}
else {
for(int i = idx + 1; i < col; i++){
arr[cnt] = i;
dfs(goal, cnt + 1, i);
}
}
}
intsolution(vector<vector<string>> relation){
row = relation.size();
col = relation[0].size();
rel = relation;
for(int i = 1; i <= col; i++){
memset(arr, 0, sizeof(arr));
dfs(i, 0, -1);
}
return answer.size();
}
나는 이런 문제에 약한 것 같다. 날짜와 데이터가 섞여서 최적의 결과를 나타내는 문제들. 연습을 좀 해야겠다.
본론
dates와 supplies를 묶어서 관리하기 위해 새로운 구조체 Data를 하나 선언한다.
structData{int date;
int supply;
Data(int a, int b): date(a), supply(b) {}
};
밀가루를 공급받기 위해 판단의 기준이 되는 우선순위 큐 pq 하나와, 밀가루를 공급받기 위한 날짜의 후보를 넣어두는 큐 q 하나를 선언한다.
우선순위 큐
priority_queue<Data, vector<Data>, cmp> pq;
큐
queue<Data> q;
for(int i = 0; i < dates.size(); i++)
q.push(Data(dates[i], supplies[i]));
후보들은 q에서 대기하고 있다가, pq에 넣어질 수 있는 조건이 충족되면 그때서야 pq에 넣어진다.
조건
내가 가지고 있는 밀가루 양보다 q.front().date가 작아야 한다.
why : 공장의 운영이 끊기면 안된다. 밀가루 양 current가 current일까지 공장이 운영될 수 있는 날이고, 밀가루는 미리 받아놓거나 (current > q.front().date인 경우) 밀가루가 떨어진 바로 다음날 새벽 (current = q.front().date인 경우) 에 받을 수 있기 때문에, 다음과 같은 식이 성립될 때 pq에 넣을 수 있다.
current>= q.front().date
pq에 넣어진 것들은 supply가 가장 큰 순서대로 나열된다. 이는 밀가루를 greedy하게 골라 다른 날짜에서 밀가루를 또 받는 일을 방지한다.
structcmp{booloperator()(Data a, Data b){
return a.supply < b.supply;
}
};
pq의 top에 있는 것이 공장이 받을 밀가루가 되므로, current += pq.top().supply;
코드
#include<bits/stdc++.h>usingnamespace std;
structData{int date;
int supply;
Data(int a, int b): date(a), supply(b) {}
};
structcmp{booloperator()(Data a, Data b){
return a.supply < b.supply;
}
};
intsolution(int stock, vector<int> dates, vector<int> supplies, int k){
int answer = 0;
int current = stock;
priority_queue<Data, vector<Data>, cmp> pq;
queue<Data> q;
for(int i = 0; i < dates.size(); i++)
q.push(Data(dates[i], supplies[i]));
while(current < k){
while(!q.empty() && current >= q.front().date){
pq.push(q.front());
q.pop();
}
current += pq.top().supply;
pq.pop();
answer++;
}
return answer;
}
