[ 자바스크립트(JavaScript) ] section08 - 12 - 조합의 경우 수(메모이제이션)

📍 section08 - 12 - 조합의 경우수 (메모이제이션)

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

 

 

조합의 경우의 수를 구하는 문제는 n의 범위가 20정도 넘으면 메모이제이션으로 풀어야 한다. 왜냐하면 연산 시간이 오래 걸리기 때문이다. 메모이제이션을 하는 이유는 동일한 계산을 반복하지 않기 위함인데, 이전에 한창 지식인 답변 활동을 했을 때 피보나치 수열의 합계를 구하는 질문에서 답했었다. 문제에 주어진 공식으로 풀 때 메모이제이션을 적용하는 이유도 마찬가지다.

 

그런데 기존에 알던 공식을 사용해도 되는데 새로운 공식을 사용하는 이유는 뭘까?(이 공식을 나는 처음 봤다 😅 😅) 예를 들어 5[1, 2, 3, 4, 5]개 중 3개를 뽑는 경우의 수(5C3)를 구한다고 했을 때 다음과 같이 풀 수 있다.

 

1. 자신은 현재 뽑는 값에 포함하고, 나머지 값에서 r-1개를 뽑는 방법(이미 내가 뽑혔으니 나머지 2개를 뽑아야 한다.)
2. 자신은 현재 뽑는 값에 제외시키고, 나머지 값에서 r개를 뽑는 방법(나는 안 뽑힌다고 가정하고 나머지 값들 중에서 3개를 뽑는다.)

 

이렇게 재귀적으로 이어나가는데, 종료 조건은 n===r || r===0일 때 1을 리턴한다. n과 r이 같다면 숫자에 상관없이 1 이고(1C1=1) r이 0이면 1(1C0=1)이기 때문이다. 메모이제이션으로 풀 때는 2차원 배열을 선언하는데 다음과 같이 저장된다. (코드에서는 memo 변수에 할당)

 

 

 

문제의 흐름을 그림으로 그렸다.

 

 

 

 

728x90

 

 

코드는 다음과 같다.

 

let n = 5;
let r = 3;

console.log(solution(n, r));

function solution(n, r){
  let answer;
  let memo = Array.from(Array(35), () => Array(35).fill(0));

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

  answer = DFS(n, r);
  return answer;
}

 

여담으로 memoization을 사용했을 때와 사용하지 않았을 때의 실행시간을 비교했는데 memo를 사용할 때는 0.003초, memo를 사용하지 않았을 때는 3.3초가 걸렸다.

 

 

 

 

let n = 33;
let r = 19;

// 메모이제이션 사용 코드
let memo = Array.from(Array(35), ()=> (Array(35).fill(0)));

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

console.log(DFS(n,r));
👉🏽 471435600

// 메모이제이션 미사용 코드
function DFS(n, r){
    if (n === r || r === 1) return 1;
    else return DFS(n-1, r-1) + DFS(n-1, r); 
  }

console.log(DFS(n, r));
👉🏽 471435600