문제
각 숫자의 배열이 주어지고 목표 숫자가 주어진다.
배열안의 숫자를 활용하여 목표숫자를 만드는 것이다.
더하고 빼서 목표숫자를 만들면 된다. 이렇게 조합한 배열의 개수를 리턴하는 문제이다.
문제 도전
문제에 DFS,BSF 라고 되어 있어서 이를 활용해보도록 노력하고자 하였다.
하지만 DFS ? BSF? 처음듣는 말이었다..
그래서 간략하게 검색해본 결과를 정리해본다.
DFS
depth First Search
깊이 우선 탐색이라는 뜻이다. 그래프 알고리즘에서 단골로 사용된다고 한다.
그물망 처럼 생긴 알고리즘이 있을것이다. 검색해보면 이미지가 많이 나온다.
DFS 는 일단 깊이 한우물먼저파고 다음으로 넘어가는 것이다.
부모 노드 부터 쭉 자식 노드 까지 보고 완료 될경우 옆의 노드로 이동하여 탐색을 한다.
DFS는 스택을 이용하면 된다고한다.
BSF
Breadth Frist Search 로 너비 우선탐색이다.
가로로 검색을 한다고 생각하면된다. DFS와 반대이다.
넓게 넓게 너비로 탐색한다.
옆의 노드를 검색하고 깊게 내려간다.
BSF는 큐를 활용한다고한다.
이렇게 까지 알고 문제를 봤다.
더하고 빼고 더하고 빼고 하면서 목표 숫자와 맞는 경우를 리턴하면 된다.
힌트로 DFS방법을 활용하면 된다고 했는데 어떻게 해야 하는지 몰라서 힌트를 더찾아봤다.
추가 힌트로는 재귀함수를 활용하는것..
재귀함수는 근데 몇번봐도 정말 모르겠다.. 너무 어렵다
또 시도해보다가 무한루프가 걸려서.. 해답을찾아볼수 밖에 없었다.
function solution(numbers, target) {
let answer = 0;
dfs(0, 0);
function dfs(index, sum) {
if(index === numbers.length) {
if (sum === target) {
answer++;
}
console.log(index,sum)
return;
}
dfs(index + 1, sum + numbers[index]);
dfs(index + 1, sum - numbers[index]);
}
return answer;
}답 로직이다. 해설로는 1인덱스부터 끝인덱스 까지 쭉 내려가면서 더하고
index === numbers.length 여기를 거치면 아래 로직인
dfs(index + 1, sum - numbers[index]);를 수행한다고 한다.
해설을 봐도 잘모르겠어서 직접 대입해보았다.
벨로그나 블로그에 많은사람들이 문제 풀이를 했는데 다 확실히 이해하셔서그런지
명확히 설명한게 없었다.
아무리 인덱스와 numbers.length가 같더라도 return으로 함수가 끝날텐데 어떻게
전체를 도는 지 확실히 잘 모르겠다.
계속 대입해보니 조금을 알것 같다.. 이해한 만큼 적어보도록하겠다.
solution([4, 1, 2, 1], 4) 이 문제로 대입을 해보았다.
주관적 해석
주관적 해석이고 완벽하게 이해하지못해서 맞지 않을수도 있다.
처음 함수를 돌때
dfs(0, 0); 을 대입하여 함수가 처음 돈다.
그리고 if 조건에 맞지 않아서 dfs(index + 1, sum + numbers[index]);여기로 다시 한번 함수가 돈다 이때 함수는 dfs(1,4) 일것이다.
이때 아랫줄에 dfs(index + 1, sum - numbers[index]); 는 실행하지 않고 스택에 저장해둔다.
여기서는 정리하기 쉽게 스택에 저장되면 스택갯수로 늘려보겠다.
함수 실행, 스택
함수 실행 / 스택 (dfs(index + 1, sum - numbers[index]);)
dfs(0,0) / 0
dfs(1,4) / 1
dfs(2,5) / 2
dfs(3,7) / 3
dfs(4.8)
이부분에서 if조건에 걸린다. 하지만 sum === target 여기에 걸리지 않아서 일단 리턴 된다.
그러면 아랫줄인 dfs(index + 1, sum - numbers[index]);을 실행한다.
dfs(4,7) 이렇게 실행될 것이다. if조건에 걸리지만 마찬가지로 sum === target 여기에 걸리지 않아서 일단 리턴 된다.
여기서 함수가 종료 된다고 생각될텐데 스택에 쌓인게 이때부터 실행이된다.
dfs(3,7) 여기 부분에서 저장되있던 스택이 실행되어서
dfs(4,6) 으로 실행될것이고 리턴 되고 함수가 끝나고 다음 스택의 함수가 실행된다.
다음 스택은 dfs(2,5) 여기 부분이다. 여기 부분에서 dfs(index + 1, sum - numbers[index]); 여기 부분을 타면
dfs(3,4) 이렇게 함수가 실행되는데 if조건에 걸리지 않아서 다시 루프를 돌것이다.
이런 형식으로 DFS가 실행되는것 같다.
이렇게 글로 정리하니 조금 나도 이해가 된 느낌이다.
이해는 했어도 이걸 어떻게 머리속으로 계산하고 로직을 짠건지 진짜 대단하신 분들이다..
글로 적어야 이해가 조금 되었지만 도대체 어느정도 로직을 공부해야지 이런 것도 척척 푸는지
잘모르겠다. ㅠㅠ
그래도 열심히 해봐야 겠다.
