코딩테스트 with JS/자바스크립트 알고리즘 문제풀이(인프런)
조합의 경우수(메모이제이션)
5_hyun
2022. 12. 23. 18:13
반응형
코드
function solution(n, r) {
let answer = [];
let dy = Array.from(Array(34), () => Array(34).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));
}
answer = DFS(n, r);
return answer;
}
해결 방법
이 풀이는 n = 5, r = 3로 가정한 풀이이다.
조합은 n === r 이거나 r이 1이면 값이 1이라 1을 반환해주면 된다.
n !== r이나 r !== 1이면 DFS(n-1, r-1) + DFS(n-1, r)을 하여 반환해줘야 한다. 하지만 n의 값이 커지면 시간이 오래 걸려서 메모이제이션을 해야한다. 그렇기에 dy에 값을 저장해둔다. 만약 DFS(n, r)을 이미 구했던 것이면 dy[n][r]의 값이 0보다 커서 그 값을 그대로 가져와 주면 속도를 개선시켜준다.
반응형