최소성 : 여러 속성을 조합해 만든 키가 유일성을 가질 때, 한 속성을 제외해도 유일성이 유지되면 최소성을 만족하지 않는다.
어떻게 검사할까 찾아보다가 비트마스크 방법으로 조합과 유일성 최소성 검사를 하는게 직관적이라는 것을 알게 되었다.
조합
각 열을 하나의 비트로 나타내면, 비트마스크의 각 비트는 열의 포함 여부를 나타낼 수 있다.
예를 들어, 열이 3개인 경우:
000: 아무 열도 포함하지 않음
001: 첫 번째 열만 포함
010: 두 번째 열만 포함
011: 첫 번째와 두 번째 열 포함
100: 세 번째 열만 포함
101: 첫 번째와 세 번째 열 포함
110: 두 번째와 세 번째 열 포함
111: 모든 열 포함
이런식으로 표현할 수 있다.
이 방법을 통해 조합을 생성하려면 2^열의 수로 순회하면 된다.
조합
// 모든 가능한 속성 조합을 생성
for (int comb = 1; comb < (1 << columns); comb++) {
// 유일성과 최소성 검사
if (isUnique(relation, columns, comb) && isMinimal(comb, candidateKeys)) {
// 유일성과 최소성을 만족하는 경우 후보키로 추가
candidateKeys.push_back(comb);
}
}
유일성 검사
유일성 검사또한 비트마스크를 통해 열 포함여부를 검사해준다.
// 유일성을 검사하는 함수
bool isUnique(vector<vector<string>>& relation, int columns, int comb) {
set<string> uniqueCheck;
for (int i = 0; i < relation.size(); i++) {
string key = "";
for (int j = 0; j < columns; j++) {
// comb의 각 비트를 확인하여 해당 열을 포함하는지 검사
if (comb & (1 << j)) {
key += relation[i][j] + " ";
}
}
// 유일성 검사: 이미 존재하는 키라면 false 반환
if (uniqueCheck.find(key) != uniqueCheck.end()) {
return false;
}
uniqueCheck.insert(key);
}
return true;
}
이때 직접적인 검사는 if (comb & (1 << j)) 부분에서 이루어진다.
comb & (1 << j) 이 부분에서 어떻게 계산이 이루어지는지는 예시를 통해 알아보자
comb의 j번째 비트가 1인지 검사하려면, 1 << j를 사용하여 j번째 비트만 1인 숫자를 만든다.
comb & (1 << j)를 수행하면, comb의 j번째 비트가 1일 때만 결과가 1이 됩니다. 그렇지 않으면 결과가 0이 된다.
comb = 5 (0101)
열의 개수 columns = 4
j = 0:
1 << 0는 0001
comb & 0001은 0101 & 0001이므로 결과는 0001 (참)
j= 1:
1 << 1은 0010
comb & 0010은 0101 & 0010이므로 결과는 0000 (거짓)
j = 2:
1 << 2은 0100
comb & 0100은 0101 & 0100이므로 결과는 0100 (참)
j = 3:
1 << 3은 1000
comb & 1000은 0101 & 1000이므로 결과는 0000 (거짓)
j = 0과 j = 2에서 조건이 참이므로, 첫 번째와 세 번째 열의 값이 key에 추가
최소성 검사
기존 후보키로 만들어진 것이 현재 조합의 부분집합에 포함된다면 후보키가 아니다.
// 최소성을 검사하는 함수
bool isMinimal(int comb, vector<int>& candidateKeys) {
// 기존의 후보키들에 대해 검사
for (int key : candidateKeys) {
// 기존의 후보키가 현재 조합에 포함되는지 검사
if ((comb & key) == key) {
// 기존 후보키가 현재 조합의 부분집합이면 최소성 만족하지 않음
return false;
}
}
// 모든 기존 후보키가 현재 조합의 부분집합이 아니면 최소성 만족
return true;
}
전체코드
#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;
// 유일성을 검사하는 함수
bool isUnique(vector<vector<string>>& relation, int columns, int comb) {
set<string> uniqueCheck;
// 각 튜플(행)에 대해 검사
for (int i = 0; i < relation.size(); i++) {
string key = "";
// comb의 각 비트를 확인하여 해당 열을 포함하는지 검사
for (int j = 0; j < columns; j++) {
if (comb & (1 << j)) {
// comb의 j번째 비트가 1이면 해당 열을 key에 추가
key += relation[i][j] + " ";
}
}
// 유일성 검사: 이미 존재하는 키라면 false 반환
if (uniqueCheck.find(key) != uniqueCheck.end()) {
return false;
}
// 새로운 키를 set에 추가
uniqueCheck.insert(key);
}
// 모든 튜플에 대해 유일성을 만족하면 true 반환
return true;
}
// 최소성을 검사하는 함수
bool isMinimal(int comb, vector<int>& candidateKeys) {
// 기존의 후보키들에 대해 검사
for (int key : candidateKeys) {
// 기존의 후보키가 현재 조합에 포함되는지 검사
if ((comb & key) == key) {
// 기존 후보키가 현재 조합의 부분집합이면 최소성 만족하지 않음
return false;
}
}
// 모든 기존 후보키가 현재 조합의 부분집합이 아니면 최소성 만족
return true;
}
int solution(vector<vector<string>> relation) {
int rows = relation.size(); // 튜플(행)의 개수
int columns = relation[0].size(); // 속성(열)의 개수
vector<int> candidateKeys; // 후보키를 저장할 벡터
// 모든 가능한 속성 조합을 생성
for (int comb = 1; comb < (1 << columns); comb++) {
// 유일성과 최소성 검사
if (isUnique(relation, columns, comb) && isMinimal(comb, candidateKeys)) {
// 유일성과 최소성을 만족하는 경우 후보키로 추가
candidateKeys.push_back(comb);
}
}
// 후보키의 개수 반환
return candidateKeys.size();
}
int main() {
vector<vector<string>> relation = {
{"100", "ryan", "music", "2"},
{"200", "apeach", "math", "2"},
{"300", "tube", "computer", "3"},
{"400", "con", "computer", "4"},
{"500", "muzi", "music", "3"},
{"600", "apeach", "music", "2"}
};
cout << solution(relation) << endl; // 출력: 2
return 0;
}
for (int i = 0; i < 4; i++) {
price[cnt].first = (100 - dis[i]) * emoticons[cnt] / 100; // 할인된 가격
price[cnt].second = dis[i]; // 할인율
dfs(cnt + 1, n, users, emoticons);
}
한 할인율을 이모티콘들에 다 적용했을 때의 이윤계산
if (cnt == n) { // 모든 이모티콘에 할인율을 대입했을 때
int plus = 0, sum = 0;
for (int i = 0; i < users.size(); i++) {
int tmp = 0;
for (int j = 0; j < n; j++)
if (users[i][0] <= price[j].second) // 원하는 할인율 이상이면 구매
tmp += price[j].first;
if (tmp >= users[i][1]) // 구매값이 정해진 가격 이상이면 이모티콘플러스 가입
plus++;
else
sum += tmp; // 이윤++
}
if (plus > answer[0]) { // 가입자수가 더 많으면
answer[0] = plus;
answer[1] = sum;
} else if (plus == answer[0] && sum >= answer[1])
answer[1] = sum; // 가입자수가 같고 이윤이 크면
return;
}
전체코드
#include <string>
#include <vector>
using namespace std;
int dis[4] = {40, 30, 20, 10}; // 할인율
vector<pair<int, int>> price(7, {0, 0}); // 할인된 가격, 할인율
vector<int> answer(2, 0);
void dfs(int cnt, int n, vector<vector<int>> users, vector<int> emoticons) {
if (cnt == n) { // 모든 이모티콘에 할인율을 대입했을 때
int plus = 0, sum = 0;
for (int i = 0; i < users.size(); i++) {
int tmp = 0;
for (int j = 0; j < n; j++)
if (users[i][0] <= price[j].second) // 원하는 할인율 이상이면 구매
tmp += price[j].first;
if (tmp >= users[i][1]) // 구매값이 정해진 가격 이상이면 이모티콘플러스 가입
plus++;
else
sum += tmp; // 이윤++
}
if (plus > answer[0]) { // 가입자수가 더 많으면
answer[0] = plus;
answer[1] = sum;
} else if (plus == answer[0] && sum >= answer[1])
answer[1] = sum; // 가입자수가 같고 이윤이 크면
return;
}
for (int i = 0; i < 4; i++) {
price[cnt].first = (100 - dis[i]) * emoticons[cnt] / 100; // 할인된 가격
price[cnt].second = dis[i]; // 할인율
dfs(cnt + 1, n, users, emoticons);
}
}
vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
dfs(0, emoticons.size(), users, emoticons);
return answer;
}
이 상자를 순회하면서 문제에서 주어진 방식대로 상자 안의 숫자로 계속 상자를 방문처리하면서 그룹을 나누고 만약 그룹이 2개보다 작다면 0점이고 아니라면 그룹 수 중에 제일 많은 수와 그 다음으로 많은 수를 곱해서 반환해주면 된다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 특정 시작점에서 그룹의 크기를 찾는 함수
int find_group(int start, vector<int>& cards, vector<bool>& visited) {
int group_size = 0; // 그룹 크기 초기화
int current = start; // 현재 상자를 시작 상자로 설정
while (!visited[current]) { // 현재 상자가 방문되지 않은 동안 반복
visited[current] = true; //방문처리
current = cards[current] - 1; // 상자 안의 숫자를 통해 다음 상자 선택
group_size += 1; // 그룹 크기를 증가시킴
}
return group_size;
}
int solution(vector<int> cards) {
int n = cards.size(); // 상자의 수
vector<bool> visited(n, false); // 방문 여부를 저장
vector<int> group_sizes; // 각 그룹의 크기를 저장
// 모든 상자에 대해 그룹을 찾음
for (int i = 0; i < n; ++i) {
if (!visited[i]) { // 현재 상자가 방문되지 않았다면
int group_size = find_group(i, cards, visited); // 그룹의 크기를 찾음
group_sizes.push_back(group_size); // 그룹 크기를 벡터에 추가
}
}
// 그룹 크기를 내림차순으로 정렬
sort(group_sizes.rbegin(), group_sizes.rend());
// 최대 점수를 계산
if (group_sizes.size() < 2) { // 그룹이 2개 미만이면
return 0; // 점수는 0
} else {
return group_sizes[0] * group_sizes[1]; // 가장 큰 두 그룹의 크기를 곱한 값이 최대 점수
}
}
