N으로 표현
N으로 표현
문제
아래와 같이 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은 1 이상 9 이하입니다.
- $1 \le N \le 9$
- number는 1 이상 32,000 이하입니다.
- $1 \le number \le 32,000$
- 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
- 최솟값이 8보다 크면 -1을 return 합니다.
예제
N number return 설명
5 12 4
2 11 3 11 = 22 / 2
해결
1st
- 경우의 수를 구해야 할 거 같다
- 다이나믹 프로그래밍이 필요할 거 같다
- 두 개를 조합하면 될까?
경우의 수
- 경우의 수를 구하려면? 순서가 상관있다면 순열을, 순서가 상관없다면 조합을 사용.
// 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;
};
다이나믹 프로그래밍
- 최적 부분 구조?
- 부분 문제에 대한 최적 해결 방법으로 전체 문제의 최적 해결 방법을 찾을 수 있다
- 부분 문제를 계산한 값이 항상 일정하다는 사실을 이용
- 부분 문제들로 나눠서 계산하여 원래 문제의 답을 계산하는
분할 정복과 같은 접근 방식. 단, 중복되는 부분 문제들이 있고, 그 공유되는 결과를 캐시해둔다는 점이 다르다
- 방식?
- 타뷸레이션(bottom-up)
- 메모이제이션(top-down): 결과 값이 입력 값에 의해서만 결정되는 참조적 투명 함수(
referential transparent function)에만 적용 가능