21.05.06 13:31 작성
·
283
0
질문 그대로 입니다. 두 부분집합이 서로소 인 경우는 최대공약수가 1인 경우인데요.
처음 찾은 부분집합이[1,3,5,7] - [6,10]이면 상관없는데 [1,5,10] - [3,6,7] 일경우 서로소 집합이 아닌데도(10 - 6은 서로소가 아니므로 서로소집합이 아니라고 생각합니다) 바로 빠져나가버려서 서로소집합이 아닌 경우에도 yes가 출력될 수 있습니다.
따라서 ,부분 집합의 합이 서로 같을 경우에 그 다음으로 서로소를 판별하는 과정이 있어야 한다고 생각합니다.
그래서 조금은 길지만 코드를 짜보았습니다!
function subsetSum(arrLength, set) {
let result = [];
let answer = [];
let tmpArr = [];
let found = false;
let sum = set.reduce((a, b) => a + b);
function compareTwoNum(a, b) {
let smaller = a > b ? b : a;
for (let i = 2; i < smaller; i++) {
let conditionOne = a % i === 0;
let conditionTwo = b % i === 0;
if (conditionOne && conditionTwo) {
return false;
}
}
return true;
}
function isRelativePrimeSets(arr, arr2) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr2.length; j++) {
if (compareTwoNum(arr[i], arr2[j])) continue;
else return false;
}
}
return true;
}
function dfs(num, set) {
if (found) return;
if (num > arrLength - 1) {
for (let i = 0; i < result.length; i++) {
if (result[i] === 1) tmpArr.push(set[i]);
}
// console.log(tmpArr);
if (
tmpArr.length > 0 &&
tmpArr.reduce((a, b) => a + b) * 2 === sum
) {
let theOther = set.filter(function (e) {
return this.indexOf(e) < 0;
}, tmpArr);
if (isRelativePrimeSets(tmpArr, theOther)) {
answer.push(tmpArr);
found = true;
}
}
// if (tmpArr.length > 0) answer.push(tmpArr);
tmpArr = [];
return;
} else {
result[num] = 1;
dfs(num + 1, set);
result[num] = 0;
dfs(num + 1, set);
}
}
dfs(0, set);
return answer;
}
subsetSum(6,[ 1, 3, 5, 6, 7, 10]) // [1, 3, 5, 7]
정말 말그대로 isrelativePrimeSets()을 통해서 하나하나 다 판별한다음 모두 서로소이면 탐색중지(found = true) 아님 계속 탐색하는 식으로 코드를 짜보았습니다!
예를들어 [ 1, 3, 4, 6, 7, 13] 가 주어진 경우 선생님 코드로 실행하게 되면 [1,3,6,7]-[4,13] 이 나오지만 제 코드로 실행하면 [1,3,13]-[4,6,7] 이 나오게 됩니다.
답변 2
0
0
2021. 05. 07. 05:18
안녕하세요^^
문제에서 제가 말한 서로서 집합은 각 원소끼로 서로소가 아니라 둘로 나뉜 두 집합사이의 관계가 서로소집합(두 집합 사이에 공통원소가 없는 경우)이란 뜻이었습니다. 컴퓨터 알고리즘에서 말하는 Disjoint Set 을 말한 것이었습니다.