[메모이제이션]조합의 경우수

문제

 

 

문제풀이

문제를 풀기 전 해당 공식이 어떻게 성립이 되는지 살펴 보자. 예를 들어 5개의 경우수 중 3개를 뽑는다고 가정해 보자.

 

이때 가장 큰 값인 5(n)를 기준으로 봤을 때, 조합을 구할 수 있는 경우의 수는 크게 5를 포함한 경우와 5를 포함하지 않을 경우인 2가지로 나뉜다.

 

5를 포함할 경우에는 남은 4개의 경우수 중 나머지 자리 2개(r-1)를 뽑고 5를 포함하지 않을 경우에는 남은 4개 경우수 중 나머지 3개(r)개를 뽑은 것이다.

---

조합수

 

코드

function solution(n, r) {
  let answer = 0;
  
  function DFS(n , r) {
    if(n === r || r === 0) return 1; //나올 수 있는 가장 작은 경우수 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 = 0;
  let dy = Array.from(Array(35), () => Array(35).fill(0)); //메모이제이션을 위해 각 조합수를 저장하기 위한 2차원 배열 생성
  
  function DFS(n , r) {
    if(dy[n][r] !== 0) return dy[n][r]; //만약에 해당 조합이 이전 탐색에서 구했을 경우에는 더는 탐색을 하지 않고 배열에 저장되어 있는 값을 반환
    if(n === r || r === 0) 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));