.png)
11. 팩토리얼
자연수 N을 입력하면 N!값을 구하기.
N! = n*(n-1)*(n-2)*.....*2*1
만약 N=5라면 5!=5*4*3*2*1=120 //나의 풀이
function solution(n) {
let answer;
let tmp = 1;
function DFS(L) {
if (L === 1) {
answer = tmp;
} else {
tmp *= L;
DFS(L - 1);
}
}
DFS(n);
return answer;
}
// 선생님 풀이
function solution(n) {
let answer;
function DFS(n) {
if (n === 1) return 1;
else return n * DFS(n - 1);
}
answer = DFS(n);
return answer;
}
console.log(solution(5)); //120👉 answer에 최종값 DFS(n)을 할당하는 방식
12. 조합의 경우수 (메모이제이션)
🙋♀️메모이제이션?
컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다
👉 중복해서 계산하는 것을 방지하기 위해 미리 메모해놓기 때문에 시간복잡도를 줄여준다.
다음 공식을 이용하여 조합의 수를 구하는 프로그램을 작성하기. 자연수 n수 n(3<=n<=33)과 r(0<=r<=n)을 인자로 받는다.
function solution(n, r) {
let answer;
let dy = Array.from(Array(35), () => Array(35).fill(0)); // 35행 35열
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(5, 3)); //10⭐️ 중요포인트) 조합 이진트리의 끝은 반드시 n === r 또는 r === 0 이기 때문에 이때 1이라는 값을 return하여 위로 올라가며 합을 더해주어 root node의 값을 구해주는 로직
⭐️ dy 라는 행렬 내에 이미 구한 조합의 값들 메모해둠으로써 중복 계산을 막아주기
✏️ 참고로 알아두기) 5C3 = 4C2 + 4C3 (5라는 자기 자신이 포함되는 경우의 수 + 포함되지 않는 경우의 수)!
위 문제는 아래와 같은 이진트리의 형태를 갖는다.
13. 수열 추측하기
가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼 의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다.
아래와 같은 형태.
N과 가장 밑에 있는 숫자(16)가 주어져 있을 때 가장 윗줄에 있는 숫자(3, 1, 2, 4)를 구하는 프로그램을 작성하기.
단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.
✏️ 파스칼의 삼각형 형태
1부터 4까지의 합일 경우 각 자리의 수가 1, 3, 3, 1 씩 합해진다.
👉 3C0 3C1 3C2 3C3 (n-1C0 ~ n-1Cn-1)** 즉 총 합을 구할 때 1 x 3C0 + 2 x 3C1 + 3 X 3C2 + 4 X 3C3으로 계산해야한다는 점 유념하기!
👉 조합의 수로 이루어진 배열, 1~4 로 이루어진 배열 각 자리수마다 더해주면 총 합을 구할 수 있다. 이 때 총 합이 f와 같은지 확인하여 답을 도출해낼 것!
function solution(n, f) {
let answer,
flag = 0;
let dy = Array.from(Array(11), () => Array(11).fill(0));
let ch = Array.from({ length: n + 1 }, () => 0); //중복 확인
let p = Array.from({ length: n }, () => 0); //구하고자 하는 최종 배열
let b = Array.from({ length: n }, () => 0); // 조합으로 이루어진 배열 (n-1C0 ~ n-1Cn-1)
function combi(n, r) {
if (dy[n][r] > 0) return dy[n][r];
if (n === r || r === 0) return 1;
else return (dy[n][r] = combi(n - 1, r - 1) + combi(n - 1, r));
}
function DFS(L, sum) {
if (flag) return;
if (L === n && sum === f) {
answer = p.slice();
flag = 1;
} else {
for (let i = 1; i <= n; i++) {
if (ch[i] === 0) {
ch[i] = 1;
p[L] = i;
DFS(L + 1, sum + b[L] * p[L]);
ch[i] = 0;
}
}
}
}
for (let i = 0; i < n; i++) {
b[i] = combi(n - 1, i);
}
DFS(0, 0);
return answer;
}
console.log(solution(4, 16)); // 3 1 2 414. 조합 구하기 (중요)
1부터N까지 번호가 적힌 구슬이 있다.이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하기.
참고) m개를 뽑는 방법의 수와 같은 문제는 무조건 조합 문제이다.
function solution(n, m) {
let answer = [];
let tmp = Array.from({ length: m }, () => 0);
function DFS(L, s) {
//조합 노드가 완성된 지점
if (L === m) {
answer.push(tmp.slice());
} else {
// s부터 n까지의 가지가 뻗어나가야 한다.
// i = 뽑는 숫자
for (let i = s; i <= n; i++) {
tmp[L] = i;
DFS(L + 1, i + 1);
}
}
}
DFS(0, 1);
return answer;
}
console.log(solution(4, 2));
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]⭐️ s부터 n까지 가지가 뻗어나가야하는 이유
👉 1이 tmp[0]의 값이 된 경우 tmp[1]로 될 수 있는 값은 2,3,4이다. tmp[0]가 2가 되었을 때 tmp[1]로 될 수 있는 값은 3,4이다. 조합의 결과를 중복되지 않게끔 하기 위해서 s값을 설정해주었다.
15. 수들의 조합
N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수 는 몇 개가 있는지 출력하는 프로그램을 작성하기.
예를 들면 5개의 숫자 2 4 5 8 12가 주어지고, 3개를 뽑은 조합의 합이 6의 배수인 조합을 찾으면 4+8+12 2+4+12로 2가지가 있다.
function solution(n, k, arr, m) {
let answer = 0;
function DFS(L, s, sum) {
if (L === k) {
if (sum % m === 0) answer++;
else return;
} else {
for (let i = s; i < n; i++) {
DFS(L + 1, i + 1, sum + arr[i]);
}
}
}
DFS(0, 0, 0);
return answer;
}
let arr = [2, 4, 5, 8, 12];
console.log(solution(5, 3, arr, 6)); //2