조합의 경우수(Memoization)

위와 같은 공식을 재귀함수를 사용하여 구현할 때 재귀가 뻗어나가는 과정에서 중복된 계산이 존재한다.

 

예를 들어 5C2 = 4C2 + 4C3 = 3C1 + 3C2 + 3C2 + 3C3 으로 표현되는데 3C2처럼 동일한 계산이 중복되는 경우가 항상 있다. 

 

계산하는 숫자가 커질경우 위와 같이 하나하나 다 계산을 하게 된다면 처리하는 속도가 현저히 느려지게 된다.

 

이 때 우리는 메모이제이션이라는 걸 활용할 수가 있다.

 

미리 만들어 둔 2차원 빈 배열에 처음 계산한 값을 저장해두고 다음에도 똑같은 계산이 나올경우 메모이제이션에서 불러와서 값을 바로 할당하는 것이다.

 

이를 코드로 구현하면 다음과 같다.

 

function solution(n, r) {
  let answer = 0;
  let memoization = Array.from({ length: n + 1 }, () =>
    Array.from({ length: r + 1 })
  );
  function DFS(n, r) {
    if (memoization[n][r]) return memoization[n][r];
    if (r === 0 || r === n) return 1;
    return (memoization[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r));
  }
  answer = DFS(n, r);
  return answer;
}