재귀함수와 완전탐색(DFS : 깊이 우선 탐색) 문제풀이(11번~15번) feat)조합

11. 팩토리얼

자연수 N을 입력하면 N!값을 구하기.

  N! = n*(n-1)*(n-2)*.....*2*1
  만약 N=5라면 5!=5*4*3*2*1=120

  //나의 풀이
  function solution(n) {
    let answer;
    let tmp = 1;
    function DFS(L) {
      if (L === 1) {
        answer = tmp;
      } else {
        tmp *= L;
        DFS(L - 1);
      }
    }
    DFS(n);
    return answer;
  }

 // 선생님 풀이
  function solution(n) {
    let answer;
    function DFS(n) {
      if (n === 1) return 1;
      else return n * DFS(n - 1);
    }
    answer = DFS(n);
    return answer;
  }
  console.log(solution(5)); //120

👉 answer에 최종값 DFS(n)을 할당하는 방식

12. 조합의 경우수 (메모이제이션)

🙋‍♀️메모이제이션?

컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다
👉 중복해서 계산하는 것을 방지하기 위해 미리 메모해놓기 때문에 시간복잡도를 줄여준다.

다음 공식을 이용하여 조합의 수를 구하는 프로그램을 작성하기. 자연수 n수 n(3<=n<=33)과 r(0<=r<=n)을 인자로 받는다.

  function solution(n, r) {
    let answer;
    let dy = Array.from(Array(35), () => Array(35).fill(0)); // 35행 35열

    function DFS(n, r) {
      if (dy[n][r] > 0) return dy[n][r]; // 기록이 이미 된 경우
      if (n === r || r === 0) return 1;
      else return (dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r)); 
    }
    answer = DFS(n, r);
    return answer;
  }
  console.log(solution(5, 3)); //10

⭐️ 중요포인트) 조합 이진트리의 끝은 반드시 n === r 또는 r === 0 이기 때문에 이때 1이라는 값을 return하여 위로 올라가며 합을 더해주어 root node의 값을 구해주는 로직

⭐️ dy 라는 행렬 내에 이미 구한 조합의 값들 메모해둠으로써 중복 계산을 막아주기

✏️ 참고로 알아두기) 5C3 = 4C2 + 4C3 (5라는 자기 자신이 포함되는 경우의 수 + 포함되지 않는 경우의 수)!

위 문제는 아래와 같은 이진트리의 형태를 갖는다.

13. 수열 추측하기

가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼 의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다.
아래와 같은 형태.

N과 가장 밑에 있는 숫자(16)가 주어져 있을 때 가장 윗줄에 있는 숫자(3, 1, 2, 4)를 구하는 프로그램을 작성하기.
단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.

✏️ 파스칼의 삼각형 형태
1부터 4까지의 합일 경우 각 자리의 수가 1, 3, 3, 1 씩 합해진다.

👉 3C0 3C1 3C2 3C3 (n-1C0 ~ n-1Cn-1)** 즉 총 합을 구할 때 1 x 3C0 + 2 x 3C1 + 3 X 3C2 + 4 X 3C3으로 계산해야한다는 점 유념하기!

👉 조합의 수로 이루어진 배열, 1~4 로 이루어진 배열 각 자리수마다 더해주면 총 합을 구할 수 있다. 이 때 총 합이 f와 같은지 확인하여 답을 도출해낼 것!

  function solution(n, f) {
    let answer,
      flag = 0;
    let dy = Array.from(Array(11), () => Array(11).fill(0));
    let ch = Array.from({ length: n + 1 }, () => 0); //중복 확인
    let p = Array.from({ length: n }, () => 0); //구하고자 하는 최종 배열
    let b = Array.from({ length: n }, () => 0); // 조합으로 이루어진 배열 (n-1C0 ~ n-1Cn-1)
    function combi(n, r) {
      if (dy[n][r] > 0) return dy[n][r];
      if (n === r || r === 0) return 1;
      else return (dy[n][r] = combi(n - 1, r - 1) + combi(n - 1, r));
    }
    function DFS(L, sum) {
      if (flag) return;
      if (L === n && sum === f) {
        answer = p.slice();
        flag = 1;
      } else {
        for (let i = 1; i <= n; i++) {
          if (ch[i] === 0) {
            ch[i] = 1;
            p[L] = i;
            DFS(L + 1, sum + b[L] * p[L]);
            ch[i] = 0;
          }
        }
      }
    }
    for (let i = 0; i < n; i++) {
      b[i] = combi(n - 1, i);
    }
    DFS(0, 0);
    return answer;
  }
  console.log(solution(4, 16)); // 3 1 2 4

14. 조합 구하기 (중요)

1부터N까지 번호가 적힌 구슬이 있다.이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하기.

참고) m개를 뽑는 방법의 수와 같은 문제는 무조건 조합 문제이다.

  function solution(n, m) {
    let answer = [];
    let tmp = Array.from({ length: m }, () => 0);
    function DFS(L, s) {
      //조합 노드가 완성된 지점
      if (L === m) {
        answer.push(tmp.slice());
      } else {
        // s부터 n까지의 가지가 뻗어나가야 한다.
        // i = 뽑는 숫자
        for (let i = s; i <= n; i++) {
          tmp[L] = i;
          DFS(L + 1, i + 1);
        }
      }
    }
    DFS(0, 1);
    return answer;
  }

  console.log(solution(4, 2));
  [1, 2]
  [1, 3]
  [1, 4]
  [2, 3]
  [2, 4]
  [3, 4]

⭐️ s부터 n까지 가지가 뻗어나가야하는 이유
👉 1이 tmp[0]의 값이 된 경우 tmp[1]로 될 수 있는 값은 2,3,4이다. tmp[0]가 2가 되었을 때 tmp[1]로 될 수 있는 값은 3,4이다. 조합의 결과를 중복되지 않게끔 하기 위해서 s값을 설정해주었다.

15. 수들의 조합

N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수 는 몇 개가 있는지 출력하는 프로그램을 작성하기.
예를 들면 5개의 숫자 2 4 5 8 12가 주어지고, 3개를 뽑은 조합의 합이 6의 배수인 조합을 찾으면 4+8+12 2+4+12로 2가지가 있다.

  function solution(n, k, arr, m) {
    let answer = 0;
    function DFS(L, s, sum) {
      if (L === k) {
        if (sum % m === 0) answer++;
        else return;
      } else {
        for (let i = s; i < n; i++) {
          DFS(L + 1, i + 1, sum + arr[i]);
        }
      }
    }

    DFS(0, 0, 0);

    return answer;
  }

  let arr = [2, 4, 5, 8, 12];
  console.log(solution(5, 3, arr, 6)); //2