DFS - 조합 경우의 수

문제

재귀를 이용해 조합수를 구해주는 프로그램을 작성하세요.

 

▣ 입력설명

첫째 줄에 자연수 n(3<=n<=33)과 r(0<=r<=n)이 입력됩니다.

 

▣ 출력설명

첫째 줄에 조합수를 출력합니다.

 

▣ 입력예제 1

5 3

 

▣ 출력예제 1

10

 

▣ 입력예제 2

33 19

 

▣ 출력예제 2

818809200

---

문제에서 다음의 공식을 이용해서 조합 경우의 수를 구하라고 하고 있다.

먼저 이 공식에 대한 이해를 해보자.

그림과 같이 5개 중에 3개를 뽑는 조합의 수를 구하려고 한다면 맨 마지막 요소인 5를 기준으로 5를 포함해서 3개를 뽑거나 5를 포함하지 않고 3개를 뽑는 경우의 수를 구할 수 있다. 5를 포함한다면 4개 중에 2개를 뽑아야하며 5를 포함하지 않는다면 4개중에 3개를 뽑아야한다. 이 두 경우를 합친 것이 5개 중에 3개를 뽑는 경우의 수가 된다.

이 과정을 반복한다면 다음과 같이 재귀 트리의 형태로 그릴 수 있다.

이때 n combi m 일때, m이 0이거나 n=m 인 경우에는 경우의 수가 1이므로 1을 리턴하면 된다.

코드로 구현해보자.

let [n, m] = require('fs').readFileSync('input.txt').toString().trim().split(' ').map(Number);
let ret = 0;

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

function solution() {
  let ret = solve(n, m);
  return ret;
}

console.log(solution());

기저조건을 만나면 다시 가지를 타고 올라가면서 최종적으로 모든 경우의 수를 반환하게 된다.

 

그런데 하나의 스킬이 더 필요하다.

입력예제가 33 19로 주어졌을 때는 어마어마하게 재귀함수가 가지를 뻗기 시작한다. 경우의 수를 구해보아도 8억이 넘어가는 수이다.

따라서 메모이제이션 즉, 메모를 해둬야한다. 왜 이런 원리를 사용해야하는지 알아보자.

트리를 그려보았다. 지금 연한 녹색과 초록색으로 그린 부분의 연산이 동일한 것을 파악할 수 있다.

이렇게 동일한 연산이 반복되기 때문에 비용이 많이 들 수 밖에 없다.

메모이제이션을 활용해서 한번 연산을 완료한 것은 반복해서 연산하지 않도록 해야한다. 그렇다면 연산량을 줄일 수 있다.

그렇다면 어떻게 메모이제이션을 만들까?n combi m 이 연산이 되었으면 이차원 배열 dy[n][m]에 연산된 값을 넣어준다. 그리고 이미 연산된 값이 있다면 dy에서 연산된 값을 찾아 반환하도록 하면 된다. 코드로 살펴보자.

let [n, m] = require('fs').readFileSync('input.txt').toString().trim().split(' ').map(Number);
let ret = 0;
let dy = Array.from({ length: n + 4 }, () => Array.from({ length: m + 4 }).fill(0));

function solve(n, m) {
  if (dy[n][m]) return dy[n][m];
  if (m === 0 || n === m) return 1;
  else {
    return (dy[n][m] = solve(n - 1, m - 1) + solve(n - 1, m));
  }
}

function solution() {
  let ret = solve(n, m);
  return ret;
}

console.log(solution());