[프로그래머스] 타겟 넘버(feat. DFS)

쿼카쿼카·2023년 2월 25일
0

알고리즘

목록 보기
41/67

코드

function solution(numbers, target) {
  // dfs를 이용한 풀이
//     let ans = 0;
  
//     dfs(0, 0)
  
//     function dfs(index, sum) {
//         if(index === numbers.length) {
//             if(sum === target) {
//                 ans++;
//             }
//             return;
//         }
      
//         dfs(index+1, sum + numbers[index]);
//         dfs(index+1, sum - numbers[index]);
//     }
  
//     return ans;
  
  // 더 직관적인 코드
  
  let ans = 0;
  
  dfs(0, 0)
  
  function dfs(index, sum) {
      if(index < numbers.length) {
          dfs(index+1, sum+numbers[index]);
          dfs(index+1, sum-numbers[index]);
      }
      else {
          if(sum === target) ans++
      }
  }
  
  return ans;
}

DFS(깊이우선탐색)

  • 어떤 알고리즘인지도 알고, 코드도 아는데 활용을 어떻게 하는지 항상 몰랐어요! 하지만 이제 알았쬬오오오오오!!! 이 문제 솔직히 못 풀었는데 배웠다는 것만으로도 구글이 바라는 인재가 아닐까요?^__^
  • 깊이우선 탐색은 root 노드부터 시작해 왼쪽 끝까지 들어갔다가 올라오고 다시 끝까지 들어가고? 암튼 한 번 들어갔다간 끝장보며 탐색하는 알고리즘이에요. 암튼 난 이해했음~
  • 주어진 숫자를 모두 더하거나 빼야하는데 그 경우의 수를 깊이우선 탐색 알고리즘으로 짰다.
  • index와 sum을 0부터 시작하는 dfs(0, 0) 그 다음부터 numbers 숫자들을 파고 들어가요!

재귀함수

  • dfs에서는 재귀함수를 사용하여 탐색을 해요!
  • index가 numbers.lnegth와 같아지고 sum과 target이 같아지면 ans를 ++ 해준다.

참고 사이트

profile
쿼카에요

0개의 댓글