동전교환

동전 최소로 나오게 하는 갯수 구하기

  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;
}

조합수

메모이제이션 적용하지 않은 코드

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);
}