[JavaScript/section 8] 12 - 조합의 경우 수

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

nCr = n! / (n - r)!r! 로 계산한다. 하지만 이 공식을 쓰지 않고 다음 공식을 사용하여 재귀를 이용해 조합 수를 구하는 문제이다.

입력설명
첫째 줄에 자연수 n(3<=n<=33)과 r(0<=r<=n)이 입력된다.
출력설명
첫째 줄에 조합수를 출력한다.

입력예제 1
5 3
출력예제 1
10

입력예제 2
33 19
출력예제 2
818809200

조합의 특징
먼저 조합이란❓ 서로 다른 n개의 원소를 가지는 어떤 집합에서 순서에 상관없이 r개의 원소를 선택하는 것
ex 1) n = 3, r = 3
1️⃣ 3개 중에서 3개를 뽑는 경우의 수는 1가지이므로 n과 r이 같을 경우의 조합 수는 1이다.
ex 2) n = 3, r = 0
2️⃣ 3개 중에서 0개를 뽑는 경우의 수는 1가지이므로 r이 0일 경우의 조합 수는 1이다.

🤔 나의 풀이 방법
공식 그대로 재귀를 이용해 문제 해결.. 하지만 n과 r의 크기가 커질수록 속도가 많이 느려지는 문제점이 발생한다.

• 조합의 특징에 의해 r이 0이거나 n과 같을 경우 1을 return 한다.

function solution(n, r) {
  let answer;

  function DFS(n, r) {
    if (r === 0 || n === r) return 1;
    else return DFS(n - 1, r - 1) + DFS(n - 1, r));
  }

  answer = DFS(n, r);
  return answer;
}

console.log(solution(33, 19));

👍 강사님 풀이 방법
강사님은 속도가 느려지는 문제점을 메모이제이션을 이용해 해결😊 2차원 배열에 n과 r에 대한 조합 수를 저장해놓고 재귀를 돌면서 n과 r에 대한 조합 수가 배열에 이미 저장되어 있다면 재귀를 멈추고 배열에서 해당 조합 수를 가져오는 방식이다. 다음 그림을 보면 이해하기 수월할 것이다❗

파란색을 보면 n이 2이고 r이 1인 경우가 이미 앞에서 한 번 나왔기 때문에 배열의 n 행 r 열에 조합 수가 저장되어 있다. 그러므로 더 이상 재귀를 돌지 않고 배열에서 값을 가져오면 속도 측면에서 많이 향상된다.

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

  function DFS(n, r) {
    if (dy[n][r] > 0) return dy[n][r];
    if (r === 0 || n === r) 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));