문제 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) {..
문제 N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요. 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다. 풀이 다음에 유의하여 풀었다. reduce를 사용할 때는 항상 안전하게 초기값을 정해주자. 부분 집합을 구할 시, 모든 원소를 포함할 것인지, 포함하지 않을 것인지를 확인하면서 끝까지(L===n) ..
문제 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램 을 작성하세요. 풀이 #1처럼 재귀 함수의 매개변수로 누적값을 전달하는 경우, 콜스택에서 최상단 함수 실행 컨텍스트가 제거 되었을 때 이전 함수 실행 시의 값을 기억하고 있기 때문에 각 재귀를 돌기 전에 해당 값을 포함할 지의 여부를 결정해주지 않아도 된다. 그렇지 않은 경우, #2과 같이 부분집합에 어떤 값을 포함할지의 여부를 체크하는 배열을 이용할 수 있다. #1 function solution(n) { function DFS(L, res) { if (L === n + 1) console.log(res); else { DFS(L + 1, res + " " + L); // 부분집합에 포함 O DFS(L + ..
