8-12. 조합의 경우 수 (메모이제이션) (DFS)

n과r이 같거나 r이 0일 때 재귀함수가 끝남. ( 5C3이 왜 4C2와 4C3으로 나뉘냐면 만약 5의 입장에서 바라보았을 때 5가 들어가 있고 나머지 2개만 선택되면 되어서 4C2 그리고 5가 안들어가 있는 조합 4C3으로 나눌 수 있습니다.

 

n과 r이 같거나 r이 0일 때 재귀 함수가 끝남. ( 5C3이 왜 4C2와 4C3으로 나뉘냐면 만약 5의 입장에서 바라보았을 때 5가 들어가 있고 나머지 2개만 선택되면 되어서 4C2 그리고 5가 안 들어가 있는 조합 4C3으로 나눌 수 있습니다.

 

문제

풀이

function solution(n, r) {
  let answer = [];

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

console.log(solution(5, 3));

 

메모이제이션이란?

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.

 

쉽게 말하면 중복된 계산을 막아주어서 계산 속도를 늘릴 수 있는 방법이다.

 

function solution(n, r) {
  let answer = [];
  let dy = Array.from(Array(35), () => Array(35).fill(0));
  function DFS(n, r) {
    if (dy[n][r] > 0) return dy[n][r];
    if (r === 0 || n === r) return 1;
    else {
      return (dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r));
    }
  }
  answer = DFS(n, r);
  return answer;
}

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

 

배열에 행과 열을 만들어 계산한 값을 해당하는 x , y 값에 넣어 이미 데이터가 존재한다면 그 데이터를 이용하는 방식이다.