(ㄴ'0'ㄱ) 조합수 : Memoization

내 풀이 - 무지성 재귀

function solution(n, r) {
  function comb(p, q) {
    if (q === 0) return 1;
    else if (q === 1 || p - q === 1) return p;

    return comb(p - 1, q - 1) + comb(p - 1, q);
  }
  answer = comb(n, r);
  return answer;
}

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

정확히 내가 푼 이 무지성 풀이의 비효율성을 해결하기 위해
Memoization을 사용하는 것!

Solution 풀이

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

console.log(solution(33, 19));
</script>

좀 많이 낯설었다.
Memoization에 대해 알고 익혀두자!