문제 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프 로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6 가지입니다. 풀이 function solution(n, arr) { let ch = Array.from({ length: n + 1 }, () => 0); let graph = Array.from({ length: n + 1 }, () => []); let answer = 0; for (let [a, b] of arr) { graph[a] = [...graph[a], b]; } console.log(graph); function DFS(v) { if (v === n) answer += 1; else { for (let i..
문제 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 && sum % m === 0) answer += 1; else { for (let i = s; i < n; i++) { DFS(L + 1, i + 1, sum + arr[i]); } } } DFS(0, 0, 0); return answer; } 1..
문제 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요. 풀이 조합의 경우는 간단하게 아래로 가지를 뻗을 때 현재 숫자 뒤부터 확인한다고 생각하면 된다. 조합에서는 현재까지 포함한 숫자를 다음 경우를 생각할 때 모두 제외하는 것이 중요하기 때문에 DFS 함수는 각 레벨을 나타내는 L과 각 L 자리에 들어갈 요소를 모두 확인하는 for문의 시작점인 start를 매개변수로 넘겨준다. 즉, for문을 돌 때 초기값인 start를 넘겨주어 이전에 사용한 값을 다시 사용하지 않도록 한다. function solution(n, r) { let c = Array.from({ length: r }); let answer = []; function DFS(L, s..
문제 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼 의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이그려진다. 3 1 2 4 4 3 6 7 9 16 N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다. 풀이 #1 function countCombs(n, r) { let memo = Array.from({ length: n + 1 }, () => Array.from({ length: r + 1 }, () => 0) ); funct..
문제 다음 공식을 사용하여 재귀를 이용해 조합수를 구해주는 프로그램을 작성하세요. nCr = n-1Cr-1 + n-1Cr 🤔 이 공식은 어떻게 성립하는 걸까? 예를 들어, 5C3 = 4C2 + 4C3을 살펴보자. 5C3은 {1, 2, 3, 4, 5} 중 3가지를 뽑는 경우의 수이다. 이것을 5의 기준에서 살펴보자면, (1) 5 자기 자신을 포함하는 경우와 (2) 5를 포함하지 않는 경우로 나눌 수 있다. (1)의 경우 이미 {⬜, ⬜, 5} 의 상태이므로 빈 자리에 {1, 2, 3, 4} 중 2개만 뽑으면 된다 → 4C2 (2)의 경우 {⬜, ⬜, ⬜} 세 자리 모두 비었으므로 {1, 2, 3, 4} 중 3개를 뽑는다. → 4C3 따라서 5C3 = 4C2 + 4C3 이다. 풀이 #1 function so..
문제 자연수 N을 입력하면 N!값을 구하세요. N! = n(n-1)(n-2).....21입니다. 만약 N=5라면 5!=5432*1=120입니다. 풀이 팩토리얼과 같이 값을 전달해야 하는 문제의 경우, 재귀를 돌 때 return을 통해 각 DFS가 값을 전달하고 이를 통해 구해진 하나의 값을 반환하여 해결한다. #1 function solution(n) { let answer = 1; function DFS(L, fact) { if (L === 1) { answer = fact; } else { DFS(L - 1, fact * (L - 1)); } } DFS(n, n); return answer; } #2 function solution(n) { function DFS(n) { if (n === 1) re..
문제 다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. 풀이 L은 각 동전을 사용할 때마다 1씩 증가하므로 사용된 동전의 개수와 동일하다. 또한 최소 개수가 구해진 상태에서 해당 L보다 더 깊이 탐색할 필요가 없기 때문에 L >= minCoinCnt인 경우는 바로 리턴한다.(Edge cutting) function solution(change, arr) { let minCoinCnt = Number.MAX_SAFE_INTEGER; const n = arr.length; function DFS(L, sum) { if (L >= minCoinCnt) return; if (sum > change) ret..
문제 10 이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 풀이 이전 중복 순열과 풀이는 매우 유사하지만 중복을 허용하지 않기 위해 ch 배열이 필요하다. function solution(m, arr) { const n = arr.length; let permutations = []; let ch = Array.from({ length: n }, () => 0); let picked = Array.from({ length: m }, () => 0); function DFS(L) { if (L === m) { let copy = [...picked]; permutations = [...permutations, copy]; } else { for (let i = ..
