문제 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 = ..
문제 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 풀이 function solution(n, m) { let answer = []; let picked = Array.from({ length: m }, () => 0); function DFS(L) { if (L === m) { let copy = [...picked]; answer = [...answer, copy]; } else { for (let i = 1; i
문제 철수는 그의 a들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태 울수가 없다. 철수는 C를 넘지 않으면서 그의 a들을 가장 무겁게 태우고 싶다. N마리의 a와 각 a의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요. 풀이 a를 태울지 말지를 결정하는 부분집합 문제이다. 이전 문제와 유사하지만 최대값을 구할 때 초기값은 안전하게 가능한 최소값인 Number.MIN_SAFE_INTEGER으로 초기화하도록 유의해야겠다. function solution(C, N, arr) { let answer = Number.MIN_SAFE_INTEGER; function DFS(L, sum) { if (sum > C) return; if (L ..
