2022/03/31) 6. 바둑이 승차 [재귀함수와 완전탐색(DFS:깊이우선탐색)]
1. 문제
<바둑이 승차>
: 철수는 그의 바둑이를 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울 수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성한다.
2. 해결 방법
- 이전에 배운대로 태울 것인가(포함) 태우지 않을 것인가(불포함)으로 따지면 된다. 다만 다른 점은 sum이 트럭무게를 넘느냐 안넘느냐를 확인해야 하고, 최대sum을 구해야 한다는 점이다.
- 흐름을 보기 위해서 코드를 순차적으로 올렸다. 콘솔창에서 어떤 순서로 출력되는지를 확인하라.
맨 마지막게 정답이다.
3. 정답
<script> function solution(c, arr){ let answer = 0; let n = arr.length; function DFS(L, sum){ if(L===n){ //L이 n일 때, 부분집합 하나가 완성된다. console.log(sum); 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)); </script>
<script> function solution(c, arr){ let answer = 0; let n = arr.length; function DFS(L, sum){ if(sum>c) return; if(L===n){ console.log(sum); 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)); </script>
<script> function solution(c, arr){ let answer = 0; let n = arr.length; function DFS(L, sum){ if(sum>c) return; //가지치기!! 밑에 if-else문에 못감! 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)); </script>
4. 내 코드와 비교 그리고 반성
이제 좀 감이 온다. 포함인지 불포함인지가 핵심인 거 같다. 이제 어떻게 줄기가 이어나가는지만 확실히 이해해서, if문만 잘 작성하면 된다. 그리고 ! 왜 L===n인지 이해못했었는데 이제 이해했다! 포함이든 불포함이든 모든 인덱스를 돌아서 0혹은 X를 해줘야 하기 때문이다. L===n일 때, 부분집합 하나가 완성되는 것이다!
Author And Source
이 문제에 관하여(2022/03/31) 6. 바둑이 승차 [재귀함수와 완전탐색(DFS:깊이우선탐색)]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@7lo9ve3/20220331-6.-바둑이-승차-재귀함수와-완전탐색DFS깊이우선탐색저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)