[알고리즘/인프런] 조합의 경우의 수(메모이제이션)

문제 

다음 공식을 사용하여 재귀를 이용해 조합수를 구해주는 프로그램을 작성하세요.

nCr = n-1Cr-1 + n-1Cr

 

🤔 이 공식은 어떻게 성립하는 걸까?

 

예를 들어, 5C3 = 4C2 + 4C3을 살펴보자.

5C3은 {1, 2, 3, 4, 5} 중 3가지를 뽑는 경우의 수이다.

이것을 5의 기준에서 살펴보자면, (1) 5 자기 자신을 포함하는 경우와 (2) 5를 포함하지 않는 경우로 나눌 수 있다.

(1)의 경우 이미 {⬜, ⬜, 5} 의 상태이므로 빈 자리에 {1, 2, 3, 4} 중 2개만 뽑으면 된다 → 4C2

(2)의 경우 {⬜, ⬜, ⬜} 세 자리 모두 비었으므로 {1, 2, 3, 4} 중 3개를 뽑는다. → 4C3

따라서 5C3 = 4C2 + 4C3 이다.

 

풀이

#1

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

  return DFS(n, r);
}

이 문제는 가능한 조합의 수를 구하는 문제이다. 위의 공식에 따르면 5C3 = 4C2 + 4C3 = (3C1 + 3C2) + (3C1 + 3C3) + ... 와 같다. nC0과 nCn은 항상 1이므로 해당 경우가 종착점이 된다. 그렇지 않은 경우, 위의 공식을 활용해 더해준 값을 계속해서 return해 최종 값을 구한다.

이처럼 이전 값을 활용해 다음 값을 구하는 문제는 DFS가 반환하는 값을 리턴하여 최종값을 구한다.

 

#2 풀이 with 메모이제이션

function solution(n, r) {
  let memo = Array.from({ length: n + 1 }, () =>
    Array.from({ length: r + 1 }, () => 0)
  );

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

  return DFS(n, r);
}

n과 r이 커질 경우 시간이 몇 초씩 걸리게 된다. 이를 해결하기 위해 메모이제이션을 사용할 수 있다. 메모이제이션은 이전에 구해둔 값이 있다면 재귀를 중단하고 이미 구해둔 값을 사용하는 것으로 시간복잡도를 줄일 수 있다.

위 문제에서는 (n+1)행 (r+1)열인 2차원 배열을 만들어 n개 중 r개를 뽑는 조합 경우의 수를 이미 구한 경우 저장해두고 활용할 수 있도록 했다.