아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.
12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5
5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.
N number return 설명
5 12 4
2 11 3 11 = 22 / 2
// nCr, n개중 r개를 선택
// n! / r!(n-r)!
// - n!? n개를 모두 나열하는 경우의 수
// - r!로 나눈다? 선택된 r개를 모두 나열하는 경우의 수를 제거
// - (n-r)!로 나눈다? 선택되지 않은 나머지를 모두 나열하는 경우의 수를 제거
// 즉 뽑기만 하면 되고, 순서는 필요없다
function k_combination_dfs(arr, to_select, combs, result) {
if (!Array.isArray(arr)) return null;
if (combs.length == to_select) {
result.push(combs);
return null;
}
if (combs.length + arr.length < to_select) return null; // 조합을 담으려는 comb의 개수와 남은 요소 수를 합쳐도 선택하려는 수만큼 안 되면 체크할 필요가 없다
for (let i = 0; i < arr.length; i++) {
k_combination_dfs(
arr.slice(i + 1, arr.length),
to_select,
[...combs, arr[i]], // js에서 파라미터로 넘어온 변수를 재사용하면 같은 메모리 주소의 변수에 계속 접근하게 된다
result
);
}
return result;
}
// 결과를 관리할 배열을 같이 넘겨준다
console.log(k_combination_dfs([1, 2, 3], 2, [], []));
console.log(k_combination_dfs([1, 2, 3], 1, [], []));
console.log(k_combination_dfs([1, 2, 3], 3, [], []));
head와 tail로 조합할 앞부분과 뒷부분을 따로 구해서 합치는 방식// head + tail 방식의 조합 구하는 방법
// https://medium.com/nerd-for-tech/july-2-generating-k-combinations-with-recursion-in-javascript-71ef2b90b44b
const combinations = (collection, combinationLength) => {
let head,
tail,
result = [];
if (combinationLength > collection.length || combinationLength < 1) {
return [];
}
if (combinationLength === collection.length) {
return [collection];
}
if (combinationLength === 1) {
return collection.map((element) => [element]);
}
for (let i = 0; i < collection.length - combinationLength + 1; i++) {
head = collection.slice(i, i + 1);
tail = combinations(collection.slice(i + 1), combinationLength - 1);
for (let j = 0; j < tail.length; j++) {
result.push(head.concat(tail[j]));
}
}
return result;
};
분할 정복과 같은 접근 방식. 단, 중복되는 부분 문제들이 있고, 그 공유되는 결과를 캐시해둔다는 점이 다르다referential transparent function)에만 적용 가능