재귀함수(DFS)
재귀함수
자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지를 출력하는 프로그램을 작성하세요.
▣ 입력설명
첫 번째 줄은 정수 N(3<=N<=10)이 입력된다.
▣ 출력설명
첫째 줄에 출력한다.
▣ 입력예제 1 3
▣ 출력예제 1 123
function solution(n) {
function DFS(L) {
if (L == 0) return;
// return;은 함수를 종료한다는 의미
else {
DFS(L - 1);
console.log(L);
}
}
DFS(n);
}
solution(3);재귀함수를 이용한 이진수 출력
10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하세요. 단 재귀함수를 이용 해서 출력해야 합니다.
▣ 입력설명
첫 번째 줄에 10진수 N(1<=N<=1,000)이 주어집니다.
▣ 출력설명
첫 번째 줄에 이진수를 출력하세요.
▣ 입력예제 1 11
▣ 출력예제 1 1011
function solution(n) {
let answer = "";
function DFS(n) {
if (n == 0) return;
else {
DFS(parseInt(n / 2));
answer += String(n % 2);
}
}
DFS(n);
return answer;
}이진트리 순회(깊이우선탐색)
전위순회 출력 : 1 2 4 5 3 6 7
중위순회 출력 : 4 2 5 1 6 3 7
후위순회 출력 : 4 5 2 6 7 3 1
전위순회
function solution(n) {
let answer = "";
function DFS(v) {
if (v > 7) return;
else {
// 전위순회
answer += v + " ";
DFS(v * 2);
DFS(v * 2 + 1);
}
}
DFS(n);
return answer;
}중위순회
function solution(n) {
let answer = "";
function DFS(v) {
if (v > 7) return;
else {
// 중위순회
DFS(v * 2);
answer += v + " ";
DFS(v * 2 + 1);
}
}
DFS(n);
return answer;
}후위순회
function solution(n) {
let answer = "";
function DFS(v) {
if (v > 7) return;
else {
// 후위순회
DFS(v * 2);
DFS(v * 2 + 1);
answer += v + " ";
}
}
DFS(n);
return answer;
}부분집합 구하기(DFS)
자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램 을 작성하세요.
▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
▣ 출력설명
첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다. 단 공집합은 출력하지 않습니다.
▣ 입력예제 1 3
▣ 출력예제 1
1 2 3
1 2
1 3
1
2 3
2
3
function solution(n) {
let answer = [];
//let ch = Array.from({ length: n + 1 }, () => 0);
let obj = {};
function DFS(v) {
if (v === n + 1) {
let tmp = "";
for (let i = 1; i <= n; i++) {
if (obj[i] === 1) tmp += i + " ";
}
if (tmp.length > 0) answer.push(tmp.trim());
} else {
obj[v] = 1;
DFS(v + 1);
obj[v] = 0;
DFS(v + 1);
}
}
DFS(1);
return answer;
}합이 같은 부분집합(DFS: 아마존 인터뷰)
N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.
둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다.
예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.
▣ 입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않으며, 그 크기는 1,000,000 이하입니다.
▣ 출력설명
첫 번째 줄에 “YES" 또는 ”NO"를 출력한다.
▣ 입력예제 1
6
1 3 5 6 7 10
▣ 출력예제 1
YES
function solution(n) {
let answer = "NO";
let tot = arr.reduce((a, b) => a + b, 0);
let tmp = 0;
function DFS(L, sum) {
if (tmp) return;
if (L === arr.length) {
if (tot - sum === sum) {
answer = "YES";
tmp = 1;
}
} else {
DFS(L + 1, sum);
DFS(L + 1, sum + arr[L]);
}
}
DFS(0, 0);
return answer;
}
let arr = [1, 3, 5, 6, 7, 10];
console.log(solution(arr));바둑이 승차(DFS)
철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태 울수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.
N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.
▣ 입력설명
첫 번째 줄에 자연수 C(1<=C<=100,000,000)와 N(1<=N<=30)이 주어집니다. 둘째 줄부터 N마리 바둑이의 무게가 주어진다.
▣ 출력설명
첫 번째 줄에 가장 무거운 무게를 출력한다.
▣ 입력예제 1
259 5
81
58
42
33
61
▣ 출력예제 1
242
function solution(c, arr) {
let answer = Number.MIN_SAFE_INTEGER;
let n = arr.length;
function DFS(L, sum) {
if (sum > c) return;
if (L === n) {
answer = Math.max(answer, sum);
} else {
DFS(L + 1, sum + arr[L]);
DFS(L + 1, sum);
}
}
DFS(0, 0);
return answer;
}
let arr = [81, 58, 42, 33, 61];
console.log(solution(259, arr));최대점수 구하기(DFS)
이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩 니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)
▣ 입력설명
첫 번째 줄에 문제의 개수N(1<=N<=20)과 제한 시간 M(10<=M<=300)이 주어집니다.
두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.
▣ 출력설명
첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.
▣ 입력예제 1
5 20
10 5
25 12
15 8
63 74
▣ 출력예제 1
41
function solution(m, ps, pt) {
let answer = Number.MIN_SAFE_INTEGER;
let n = ps.length;
function DFS(L, sum, time) {
if (time > m) return;
if (L === n) {
answer = Math.max(answer, sum);
} else {
DFS(L + 1, sum + ps[L], time + pt[L]);
DFS(L + 1, sum, time);
}
}
DFS(0, 0, 0);
return answer;
}
let ps = [10, 25, 15, 6, 7];
let pt = [5, 12, 8, 3, 4];
console.log(solution(20, ps, pt));