1. 문제
<조합의 경우수(메모이제이션)>
: 아래와 같은 공식을 사용하여 재귀를 이용해 조합수를 구해주는 프로그램을 작성한다.
nCr = n-1Cr-1 + n-1Cr
(첫 번째 줄에 자연수 n(3<=n<=33)과 r이 입력된다.)
2. 해결 방법
- 원래 5C3 = 라고 계산하지만, 위의 공식대로 5C3 = 4C2 + 4C3 로 해서 재귀로 뻗어나가보자.
위의 공식을 추가설명하자면, 만약 {1,2,3,4,5}라는 5개의 집합 중 3개를 뽑는다.
그렇다면 {5}의 기준에서, {5}가 속했을 때 혹은 속하지 않았을 때 총 2가지로 나눌 수 있다.
{ , , 5} 혹은 { , , }. 그러므로 앞일 경우엔 4C2 / 뒤일 경우엔 4C3이다. (5을 이미 뽑는다고 가정했으므로, 4개 중 2개만 뽑으면 됨 / 5을 이미 뽑지 않는다고 가정했으므로 4개 중 3개만 뽑으면 됨)- 이런 식으로 재귀가 뻗어 나가다보면 이미 구해진 값들을 두 번 구하는 경우가 있을텐데, 이렇게 되면 효율적이지가 않으므로, 메모이제이션을 쓴다. 메모이제이션은 미리 메모해놓는다는 뜻인데, 이미 구해진 값들을 2차원 배열에 기록하면 된다.
- 재귀로 뻗어나가는 것을 그림그려보자. 그러면 종착점(=어떤 곳에서 끝나는지)을 알 수 있는데, xC0 혹은 xCx에서 끝난다. 고딩수학개념을 다시 잡고 보면 바로 이해가 갈 듯하다. 저 값이 나올 경우에 답은 1이므로 return 1을 해주면 된다.
! 추가개념
- Array.from(Array(3),()=>Array(5).fill(0)) //3행 5열이 만들어지고, 0으로 초기화된다.
3. 정답
<html> <head> <meta charset="UTF-8"> <title>출력결과</title> </head> <body> <script> function solution(n, r){ let answer; let dy = Array.from(Array(35),()=>Array(35).fill(0)) //자연수 n이 33까지 들어온다고 했으므로. function DFS(n,r){ if(dy[n][r]>0) return dy[n][r]; //메모이제이션!(값이 있으면 0보다 클것이므로) 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(5, 3)); </script> </body> </html><script> //메모이제이션이 없을 경우. function solution(n, r){ let answer=[]; function DFS(n,r){ if(n===r || r===0) return 1; //종착점 else return DFS(n-1, r-1)+DFS(n-1,r); } answer=DFS(n,r); return answer; } console.log(solution(5, 3)); </script>
아자아자 파이띵굥!