[코딩테스트] 조합의 경우의 수(메모이제이션)

1. 문제.

 

우선 nCr = n-1Cr-1 + n-1Cr 공식이 어떻게 성립하는지부터 알아보자.

n개의 서로 다른 원소 중 r개를 선택하는 경우의 수를 찾을 땐, 두 가지 경우가 발생한다.

 

하나는 선택된 원소를 포함하는 경우이고, 하나는 포함하지 않는 경우이다.

특정 원소를 이미 선택했다고 가정하면, 남은 n-1개의 원소 중, r-1개를 더 선택해야 하므로 경우의 수는 n-1Cr-1이 된다.

 

반대로 선택하지 않은 경우라면, n-1개의 원소 중, r개를 선택해야 하므로 경우의 수는 n-1Cr이 된다.

따라서 n개의 원소 중 r개를 선택하는 경우의 수는, 두 경우의 수를 합한 n-1Cr-1 + n-1Cr가 된다. 

 

 

2. 문제 풀이

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(n === r || r === 0) return 1
    else return dy[n][r]=DFS(n-1, r-1) + DFS(n-1, r);
  }
}

console.log(solution(5, 3))

 

우선 메모이제이션은 제외하고 다른 부분부터 살펴보자. 

 

nCr = n-1Cr-1 + n-1Cr를

nCr를 하나의 재귀함수라고 생각하면 된다.

 

이를 구현하면 아래와 같이 호출 스택에 쌓이게 된다. 

 

binomialCoefficient(5, 3)
  -> binomialCoefficient(4, 2) + binomialCoefficient(4, 3)
    -> (binomialCoefficient(3, 1) + binomialCoefficient(3, 2)) + (binomialCoefficient(3, 2) + binomialCoefficient(3, 3))
      -> ((binomialCoefficient(2, 0) + binomialCoefficient(2, 1)) + (binomialCoefficient(2, 1) + binomialCoefficient(2, 2))) + ((binomialCoefficient(2, 1) + binomialCoefficient(2, 2)) + binomialCoefficient(3, 3))
        -> (((1 + binomialCoefficient(1, 0) + binomialCoefficient(1, 1)) + (binomialCoefficient(1, 0) + binomialCoefficient(1, 1)) + 1)) + ((binomialCoefficient(1, 0) + binomialCoefficient(1, 1)) + 1) + 1))
          -> (((1 + (1 + 1)) + ((1 + 1) + 1)) + (((1 + 1) + 1) + 1))
          -> (((1 + 2) + (2 + 1)) + ((2 + 1) + 1))
          -> ((3 + 3) + (3 + 1))
          -> (6 + 4)
          -> 10

 

여기서 2C0은 2개의 원소 중, 0개를 선택하는 상황을 의미한다.

원소를 하나도 선택하지 않는 방법은 언제가 한 가지뿐이기 때문에 해당 값은 1이 된다. 

 

3C3의 경우도 마찬가지이다.

원소를 모두 선택하는 방법은 언제가 한 가지 뿐이기 때문에 해당 값은 1이 된다.

따라서 if문을 통해 위 경우를 종료시점으로 잡아준다.

 

 

 

이제 메모이제이션 부분에 대해 알아보자. 

 

해당 재귀함수가 호출되는 것을 보면, 위처럼 겹치는 부분이 있다.

값이 겹치는 경우, 원래있던 값을 리턴하도록 만들어주면 속도가 훨씬 빨라진다. 

 

 

let dy=Array.from(Array(35), ()=>Array(35).fill(0)) //메모이제이션

 

이차원 배열을 만들어 해당 좌표에 값을 넣고, 값이 있다면 기존값이 리턴되도록 하면 된다.

 

Array.from을 통해 이차원 Array 배열을 만들어주고 fill을 통해 값을 0으로 초기화해준다.

이때, 자연수는 33보다 크지 않기 때문에 넉넉히 35칸을 만들어준다.

 

 

if(dy[n][r] > 0) return dy[n][r]

 

그 후, 해당 좌표의 값이 0보다 크다면 이미 값이 존재하는 것이므로 기존의 값을 return 해준다.