재귀함수와 완전탐색(DFS: 깊이 우선 탐색) 문제풀이 (3번~ 6번)
🙋♀️이진트리?
부모노드에서 자식노드 두개씩 (왼쪽, 오른쪽)아래로 뻗어나가는 형태.
각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.
🙋♀️깊이우선탐색(DFS)?
시작 정점에서부터 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식을 의미한다. 더 방문할 정점이 존재하지 않으면 다시 뒤로 돌아가 다른 경로를 찾아간다. 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
👉 깊이우선탐색 종류
✏️ 전위순회 : 부모 - 왼쪽 - 오른쪽 순으로 출력한다. (1 2 4 5 3 6 7)
✏️ 중위순회 : 왼쪽 - 부모 - 오른쪽 순으로 출력한다. (4 2 5 1 6 3 7)
✏️ 후위순회 : 왼쪽 - 오른쪽 - 부모 순으로 출력된다. (4 5 2 6 7 3 1)
3. 이진트리 순회(DFS : 깊이우선탐색)
1~7 숫자를 전위순회, 중위순회, 후위순회 모두 이용하여 출력하기.(위 그림 참고)
참고) v: 정점
function solution(v) {
let answer;
function DFS(v) {
if (v > 7) return;
else {
// 1. 전위 순회
// console.log(v); // 부모
// DFS(v * 2); // 왼쪽
// DFS(v * 2 + 1); // 오른쪽
//2. 중위순회
// DFS(v * 2);
// console.log(v);
// DFS(v * 2 + 1);
//3. 후위순회
DFS(v * 2);
DFS(v * 2 + 1);
console.log(v);
}
}
DFS(v);
return answer;
}
console.log(solution(1));
//전위 순회 출력 : 1 2 4 5 3 6 7
//중위 순회 출력 : 4 2 5 1 6 3 7
//후위 순회 출력 : 4 5 2 6 7 3 1
4. 부분 집합 구하기(DFS)
자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램 작성하기.
function solution(n) {
let answer = [];
let ch = Array.from({ length: n + 1 }, () => 0); //체크배열 만들기
function DFS(v) {
if (v === n + 1) {
let tmp = "";
for (let i = 1; i <= n; i++) {
if (ch[i] === 1) tmp += i + " "; //ch[i] 가 1인것만 포함 tmp에 포함시킨다.
}
if (tmp.length > 0) answer.push(tmp.trim());
} else {
ch[v] = 1; // 집합에 포함시킨다.
DFS(v + 1);
ch[v] = 0; // 집합에 포함시키지 않는다.
DFS(v + 1);
}
}
DFS(1);
return answer;
}
console.log(solution(3));
//123
//12
//13
//1
//23
//2
//3
위의 문제는 아래와 같은 이진트리가 만들어진다.
5. 합이 같은 부분집합 (DFS : 아마존 인터뷰)
N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하기.
예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.
function solution(arr) {
let answer = "NO";
let total = arr.reduce((a, b) => a + b, 0);
let n = arr.length;
let flag = 0;
function DFS(L, sum) {
//불필요한 재귀함수 부르는 것 멈추기 위해
if(flag) return;
//부분집합이 완성된 경우
if (L === n) {
if (total - sum === sum) {answer = "YES";
flag = 1;
}
} else {
DFS(L + 1, sum + arr[L]);
DFS(L + 1, sum);
}
}
DFS(0, 0);
return answer;
}
let arr = [1, 3, 5, 6, 7, 10];
console.log(solution(arr)); //"YES"
6. 바둑이 승차(DFS)
철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울 수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.
N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하기.
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)); //242
느낀 점
이진트리가 끝까지 뻗쳤을 때와 뻗치지 않았을 때를 나누어서 로직을 짠다는 점 유의하기! 재귀의 가짓수를 줄여주기 위해 해당 범위에서 벗어난 경우의 조건들은 return해주자!
Author And Source
이 문제에 관하여(재귀함수와 완전탐색(DFS: 깊이 우선 탐색) 문제풀이 (3번~ 6번)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hoje15v/재귀함수와-완전탐색DFS-깊이-우선-탐색-문제풀이-3번-6번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)