👨‍💻 사건

순열 조합을 공식사용하지 않고 구현하기

을 해결하는 과정에서, n 과 r 이 커지게 되면 엄청난 시간이 걸리는 것을 알수있다. 조금 더 효율적인 방법을 고안하기 위해 메모이제이션 기법을 활용해 보았다.

✅ 해결

메모이제이션을 통해 문제에 나와있는 범위(n과r) 를 커버가능한 2차원 배열을 생성하여, 해당 nCr 의 값을 저장해두었다. 이 방법은 이미 계산된 조합의 값을 바로 불러다가 사용이 가능하기 때문에 불필요한 탐색을 줄일수있다.

이를 통하여 구현한 코드는 아래와 같다.

function solution(number, range) {
  let answer = [];
  let dy = Array.from(Array(34), () => Array(34).fill(0));
  function DFS(n, r) {
    if (dy[n][r] > 0) return dy[n][r];
    // 위와 같은 메모이제이션을 활용하여 효율적으로 계산가능하다.
		// 0으로 초기화 시켜둔 dy 에 0이 아닌 값이 들어가있다면 그 값을 return 하는 형식이다.    
    
		if (r === 0 || n === r) {
      return 1;
    } else {
      return (dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r));
    }
  }
  answer = DFS(number, range);
  return answer;
}