문제 설명
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항
주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
각 숫자는 1 이상 50 이하인 자연수입니다.
타겟 넘버는 1 이상 1000 이하인 자연수입니다.
입출력 예
| numbers | target | return |
|---|---|---|
| [1, 1, 1, 1, 1] | 3 | 5 |
| [4, 1, 2, 1] | 4 | 2 |
이 분 블로그를 참조했습니다!
해당 문제는 깊이 우선 탐색 즉 DFS 를 사용하는 문제입니다.
우선 왜 DFS를 써야하는지 부터 이해해 봅시다!
그전에 DFS에 대해서 이해하고 넘어갑시다
DFS 당신은 누구입니꺼
말 그대로 깊이 우선 탐색입니다. 그래프에서 다른 노드를 방문하기 전에 하나의 노드를 깊게 파고들며 순회하는 검색 알고리즘입니다.
BFS랑 모가 다른덱..?
이렇게 둘을 비교해서 보면 더 쉽게 이해가 됩니다.
BFS는 보는 것처럼 인접한 노드들을 우선 방문하는 것을 확인할 수 있습니다. 쉽게 말하자면 그냥 가까운 노드들을 우선적으로 방문한다고 보면 됩니다.
DFS는 보면 앞선 설명과 같이 깊게 파고들며 순회하는 것을 확인할 수 있습니다. 이 친구는 자식을 우선적으로 탐색하는 친구입니다.
DFS BFS 언제 써야할까?!!?
DFS
-> 검색 대상 그래프가 큰 경우 (정점과 간선의 개수가 많음)
-> 경로의 특징을 저장해둬야 하는 문제
ex) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는 데 경로에 같은 숫자가 있으면 안된다는 문제 (BFS는 경로의 특징을 가지지 못함)
BFS
-> 미로찾기 등 최단거리를 구해야 할 경우 (DFS는 처음으로 발견되는 해답이 최단거리 라는 것이 보장이 안된다. 반면 BFS는 현재 노드에서 가까운 곳부터 찾기 때문에 경로 탐색 시 첫번째로 찾아지는 해답이 곧 최단거리이다.)
DFS BFS 둘 다 적합한 경우
-> 단순히 모든 정점을 방문하는 것이 중요한 문제인 경우 어떤 것을 택해도 된다.
풀이
우리는 문제에서 주어진 모든 숫자에 + 혹은 - 연산을 하게 됩니다. 각 숫자들이 가질 수 있는 경우의 수는 2가지가 됩니다.
두 알고리즘을 모두 사용할 수 있으나 조사해보니 BFS를 사용한 경우 시간 초과가 나온다고 합니다.(참조)
DFS는 재귀함수를 이용해서 구현합니다.
function solution(numbers, target) {
var answer = 0;
dfs(0,0);
function dfs(index,sum){
if(index === numbers.length){
if(sum === target){
answer++;
}
return;
}
dfs(index+1, sum + numbers[index]);
dfs(index+1, sum - numbers[index]);
}
return answer;
}코드를 설명하자면 index는 조사하는 노드의 index 번호를 뜻합니다. sum은 숫자를을 더해서 나온 값을 의미합니다. 노드 탐색은 0부터 할 것이므로 처음엔 index, sum 둘 다 0으로 시작합니다. 모든 노드를 탐색했을 경우 sum이 문제에서 주어진 target 값과 동일한지 확인하고 맞다면 정답에 1을 더해줍니다. 우리가 원하는 것은 타겟 넘버를 만드는 방법의 수이기 때문입니다! 조건문에 맞지 않는 경우는 계속해서 탐색을 해야 하므로 자식노드를 탐색하게 됩니다. 이때 +인 경우 -인 경우 2가지가 있기 때문에 함수가 2번 호출된 것을 확인할 수 있습니다.
알고리즘은 언제 봐도 어려워!! 사실 아직도 언제 적절하게 써야하는지가 조금 헷갈리지만.. 앞으로 꼐속 하다보면 알게 될거라....믿...는.....다!
출처
