Skip to main content

타겟 넘버

Solution​

function solution(numbers, target) {
  let answer = 0;
  const numberLength = numbers.length;

  (function loopSum(idx, sumValue) {
    if (idx < numberLength) {
      const nextIdx = idx + 1;
      const curNumber = numbers[idx];

      // 해당 숫자를 더하는 경우의 수
      loopSum(nextIdx, sumValue + curNumber);
      // 해당 숫자를 빼는 경우의 수
      loopSum(nextIdx, sumValue - curNumber);
    } else if (sumValue === target) {
      answer += 1;
    }
  })(0, 0);

  return answer;
}

Review​

BFS vs DFS

DFS와의 가장 큰 차이로, 여러 갈래 중 무한한 길이를 가지는 경로가 존재하고 탐색 목표가 다른 경로에 존재하는 경우 DFS로 탐색할 시에는 무한한 길이의 경로에서 영원히 종료하지 못하지만, BFS의 경우는 모든 경로를 동시에 진행하기 때문에 탐색이 가능하다는 특징이 있다. ex) 네비게이션

트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 대표적으로 백트래킹에 사용한다. 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 스택 오버플로우를 유의해야 한다.

자동 미로 생성에 많이 사용되는 알고리즘이기도 하다. 방향은 무작위로 해서 계속 뚫다가 막혀서 못 뚫으면 뚫을 수 있는 곳이 발견될 때까지 되돌아가서 다시 뚫고, 또 막히면 되돌아가고 이런 식으로 무한히 반복하다 보면 생긴다. 게다가 이 방식으로 미로를 만들면 빠져나가는 경로 또한 단 하나만 생긴다.

References​