[21/08/06 KATA NINJA] 동전교환 & 순열구하기 & 팩토리얼 & 조합수(메모이제이션)
동전교환
동전 최소로 나오게 하는 갯수 구하기
let answer = Number.MAX_SAFE_INTEGER;
function DFS(sum, count) {
if (m < sum) return;
// count값이 answer보다 같거나 크면 뒤에서도 가망 없으니깐 끝내줘야함 이거안해주면 328402번 돌고 이거해주면 2539번 돈다.
if (count >= answer) return;
if (m === sum) {
answer = Math.min(answer, count);
}
for (let i = 0; i < arr.length; i++) {
DFS(sum + arr[i], count + 1);
}
}
DFS(0, 0);
return answer;
- DFS cutting임 이미 값보다 크거나 같으면 절대 값이 될 수 없으므로 끝내주는 것이 중요하다.
순열구하기
줄인코드
function solution(m, arr) {
let answer = [];
function DFS(visited, curPer) {
// depth는 curPer의 갯수가 되므로 필요없는 인자이다.
if (curPer.length === m) {
answer.push(curPer);
return;
}
for (let check = 0; check < arr.length; check++) {
//여기가 키포인트인데, 위 스코프에서 포문안돌려도된다는걸인지하자
if (!visited.includes(check)) {
DFS([...visited, check], [...curPer, arr[check]]);
}
}
}
DFS([], []);
return answer;
}
긴 코드
function solution(m, arr) {
let answer = [];
function DFS(cur, visited, depth, curPer) {
if (depth === m) {
answer.push(curPer);
return;
}
// 굳이 여기서 방문 찍을 이유없다 보내기전에 찍고 보내도댐
visited.push(cur);
for (let check = 0; check < arr.length; check++) {
if (!visited.includes(check)) {
// 여기서 방문배열에 넣고 보내면된다. 현재 값 넣는 것 처럼
DFS(check, [...visited], depth + 1, [...curPer, arr[check]]);
}
}
}
for (let check = 0; check < arr.length; check++) {
// 여기서 포문 돌릴필요가없음
DFS(check, [], 1, [arr[check]]);
}
return answer;
}
팩토리얼
function solution(n) {
let answer = 1;
function DFS(number) {
if (number === 1) return;
answer = answer * number;
DFS(number - 1);
}
DFS(n);
return answer;
}
조합수
function solution(m, arr) {
let answer = [];
function DFS(visited, curPer) {
// depth는 curPer의 갯수가 되므로 필요없는 인자이다.
if (curPer.length === m) {
answer.push(curPer);
return;
}
for (let check = 0; check < arr.length; check++) {
//여기가 키포인트인데, 위 스코프에서 포문안돌려도된다는걸인지하자
if (!visited.includes(check)) {
DFS([...visited, check], [...curPer, arr[check]]);
}
}
}
DFS([], []);
return answer;
}
function solution(m, arr) {
let answer = [];
function DFS(cur, visited, depth, curPer) {
if (depth === m) {
answer.push(curPer);
return;
}
// 굳이 여기서 방문 찍을 이유없다 보내기전에 찍고 보내도댐
visited.push(cur);
for (let check = 0; check < arr.length; check++) {
if (!visited.includes(check)) {
// 여기서 방문배열에 넣고 보내면된다. 현재 값 넣는 것 처럼
DFS(check, [...visited], depth + 1, [...curPer, arr[check]]);
}
}
}
for (let check = 0; check < arr.length; check++) {
// 여기서 포문 돌릴필요가없음
DFS(check, [], 1, [arr[check]]);
}
return answer;
}
function solution(n) {
let answer = 1;
function DFS(number) {
if (number === 1) return;
answer = answer * number;
DFS(number - 1);
}
DFS(n);
return answer;
}
조합수
메모이제이션 적용하지 않은 코드
33 19라고 가정하면 매우 값이 커지겠지 ?
function solution(n, r) {
function DFS(n, r) {
if (r === 1) return n;
if (n === r) {
return 1;
}
return DFS(n - 1, r - 1) + DFS(n - 1, r);
}
return DFS(n, r);
}
메모이제이션 적용 코드
이미 구한 값들은 기억해둔다.
function solution(n, r) {
// object에 이미 계산한 값을 저장한다.
let object = {};
function DFS(n, r) {
if (object[`${n}${r}`]) return object[`${n}${r}`];
if (r === 1) return n;
if (n === r) {
return 1;
}
return (object[`${n}${r}`] = DFS(n - 1, r - 1) + DFS(n - 1, r));
}
return DFS(n, r);
}
Author And Source
이 문제에 관하여([21/08/06 KATA NINJA] 동전교환 & 순열구하기 & 팩토리얼 & 조합수(메모이제이션)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@rat8397/210806-KATA-NINJA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)