조합 nCr 구하기.

코딩테스트에서도 쓰는 경우가 종종 있기도하고.. 그 때마다 어버버 하는것도 싫어서, 직접 기록합니다.

조합 nCr 플로우

1. const storage = [1,1]를 만든다.

  1)[1, 1]로 만든 이유는 0! 에서 대응이 가능하고, 인덱스와, 팩토리얼n의 n이 일치하기에 편하게 하기 위해

  2)storage를 따로 선언한 이유는 nCr의 같은경우에, 팩토리얼이 무려 3개가 사용되기 때문에 재활용을 하기 위해서

2. storage n번째가 없다면, storage의 마지막 값에 마지막 값+1을 곱한 값을 곱한후 다시 팩토리얼 함수를 실행한다. 

  if (!storage[n]) {
    storage.push(storage.length * storage[storage.length - 1]);
    fact(n);
  } else {
    return storage[n];
  }

그렇다면, n!이 생성될 때까지 팩토리얼 함수를 재귀함수시킨다.  지금 여기까지 쓴다면, 이전에 값이 저장된 팩토리얼이라면 문제없이 실행이된다. 

3. 마지막으로 없는 값의 팩토리얼을 추출하기 위해서 return storage[storage.length-1]을 실행한다.

4. combination의 공식인 f(n)/f(r)/f(n-r)을 넣는다.

최종

const storage = [1, 1];
const fact = (n) => {
  if (!storage[n]) {
    storage.push(storage.length * storage[storage.length - 1]);
    fact(n);
  } else {
    return storage[n];
  }

  return storage[storage.length - 1];
};
const combination = (n, r) => {
  console.log(fact(4), fact(1));
  return fact(n) / fact(r) / fact(n - r);
};

아이디어가 어렵거나 식이 어렵진 않다. 단지, 재귀함수를 사용하 였을때, 어느 것이 언제 어느 값을 주느냐가 헷갈릴수있다. 만일 잘못 식을 넣었다면 undefined를 마주하게 된다. ;ㅁ;!