문제 가장 윗줄에 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 ..
문제 이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.) 풀이 문제를 풀지 말지를 하나씩 담아보면서 가능한 최대 점수를 찾는 이진트리의 부분집합 문제였다. 부분 집합을 구해서 풀어야하는 문제들은 우선 재귀함수를 이용한 DFS로 푼다. 만약 검사해야하는 항목의 수가 많아지면 그때는 깊이가 너무 깊어지기 때문에 시간이 너무 오래 걸린다. 그 때는 DP를 사용한다. function solution(m, ps, pt) {..
