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

문제 : 조합의 경우수(메모이제이션)

문제 설명

조합 즉 서로 다른 n개중에 r개를 선택하는 경우의 수를 구할 때 nCr = n! / ((n-r)! * r!) 다음과 같은 공식으로 계산합니다. 이 공식을 쓰지 않고 다음 공식을 사용하여 재귀를 이용해 조합 수를 구해주는 프로그램을 작성하세요.

nCr = (n-1)C(r-1) + (n-1)Cr

▣ 입력설명

첫째 줄에 자연수 n(3<=n<=33)과 r(0<=r<=n)이 입력됩니다.

▣ 출력설명

첫째 줄에 조합 수를 출력합니다.

▣ 입력예제 1

5 3

▣ 출력예제 1

10

▣ 입력예제 2

33 19

▣ 출력예제 2

818809200

코드

※ 풀지 못하여 정답지를 참고해 정리한 코드

// 정답지 코드
// 재귀 함수가 값을 리턴받는 형태
// 재귀 함수에서 현재 조합의 경우의 수를 이중 배열에 저장해 재귀적으로 조합의 경우의 수를 저장해두고 재활용
function solution(n, r) {
  let answer;
  // 메모지에이션을 위한 2차원 배열 생성
  let dy = Array.from(Array(35), () => Array(35).fill(0));

  function DFS(n, r) {
    // 이미 특정 n 과 r 의 조합의 경우의 수를 구한 경우 dy[n][r] 값을 반환
    if (dy[n][r] > 0) return dy[n][r];
    // 경우의 수가 1 개일 수 밖에 없는 경우(n 개중에 n 개를 뽑는 경우 or 아무것도 뽑지 않은 경우) 1 을 반환
    if (n === r || r === 0) return 1;
    // 특정 두 조합의 경우의 수를 더한 값을 `dy` 배열에 `n` 번째 배열의 `r` 번째 위치에  저장 후 반환
    else return (dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r));
  }
  console.log(dy);
  answer = DFS(n, r);
  return answer;
}

풀이

1. 메모지에이션을 위한 2차원 배열 dy 생성
2. 다른 n 개 중 r 개를 뽑을 조합의 경우의 수를 구할 때 사용할 숫자 n, r 을 인자로 가지는 재귀함수 DFS 선언
3. 수식에서 사용되는 특정 두 조합의 경우의 수를 더한 값을 dy 배열에 n 번째 배열의 r 번째 위치에 저장 후 반환
4. 경우의 수가 1 개일 수 밖에 없는 경우에는(n 개중에 n 개를 뽑는 경우 or 아무것도 뽑지 않은 경우) 따로 재귀 함수를 호출하지 않고 1 을 반환
5. 만약 n 번째 배열의 r 번째 위치에 이미 값이 있는 경우(현재 n 과 r 값으로 조합의 경우의 수를 구한 경우) 따로 재귀 함수를 호출하지 않고 dy[n][r] 값을 반환

오답 노트

※ 잘못된 시도 코드

function solution(n, r) {
  let answer;

  // 매개변수에 값을 더해가며 최종 답을 리턴하는 방식을 시도
  function recursion(nn, rr, total = 1) {
    if (rr > 0) {
      answer += total;
      return;
    }

    for (let i = 1; i <= n - r; i++) {
      total = total * i;
    }

    recursion(nn - 1, rr - 1, total);
    recursion(nn - 1, rr, total);
  }
  return answer;
}

이 문제의 경우 조합의 경우의 수를 구하기 위해 특정 두 조합의 경우의 수를 더해야 하고 특정 두 조합의 경우의 수 역시 재귀 함수처리할 경우 재귀적으로 함수를 호출해가면서 현재까지의 경우의 수를 더해가면서 쌓는 방식으로 구현할 수 없었다.

즉 이전까지 자주 사용하던 재귀 함수의 매개변수에 계산 값을 쌓아가는 방식으로 처리 할 수 없었다.

---

참고

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard