[프로그래머스] Lv 2. 타켓 넘버 - Javascript 풀이

💡 유형: DFS/BFS

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

구현

주어진 숫자를 적절히 더하고 빼서 타켓 넘버를 만드는 방법의 수

-> 주어진 숫자를 모든 경우의 수로 조합하고, 그 값 === target이면 답에 +1

각 숫자에는 +, - 두 가지 경우가 존재한다.

각 숫자마다 두 가지 경우 중 하나를 선택하고, 또 두 가지 경우 중 하나를 선택하는 것을 반복 => DFS

풀이

function solution(numbers, target) {
    let count = 0;
    
    const dfs = (index, sum) => {
        if(index === numbers.length){ //모든 숫자를 사용한 경우
            if(sum === target) count++;
            return;
        }
        
        dfs(index+1, sum + numbers[index]);
        dfs(index+1, sum-numbers[index]);
    }
    
    dfs(0,0);
    return count;
}

 

1. DFS 탐색 수행
   • index를 이용하여 현재 탐색 중인 숫자의 위치를 추적한다.
   • sum을 현재까지의 합으로 유지하여, 최종적으로 target과 비교한다.
   • 모든 숫자를 탐색한 후 sum === target이면 경우의 수를 증가시킨다.
2. 재귀 호출
   • 각 숫자에 대해 +와 -의 두 가지 선택을 적용하며 DFS 탐색을 수행한다.

 

재귀 함수를 생각해내는 것이 아직 좀 어려운 것 같다.

 

dfs, bfs에 대한 개념은 아래의 블로그를 보면서 정리했다.

https://velog.io/@sean2337/Algorithm-DFS%EC%99%80-BFS%EC%9D%98-%EC%89%AC%EC%9A%B4-%EA%B0%9C%EB%85%90-JavaScript-%EA%B5%AC%ED%98%84-%EB%B0%A9%EB%B2%95

[Algorithm] DFS와 BFS의 쉬운 개념 + JavaScript 구현 방법