[ALGORITHM NINJA] 프로그래머스DFS 1번 타겟넘버
DFS
스택과 재귀
- 깊게 탐색 하는 것이다.
- 계속 내려가다 더 이상 갈 수 없게되면 다시 가장 가까운 갈림길로 돌아온다
- 사용하는 경우 : 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.
- BFS보다 간단하다.
- BFS에 비해서 느리다
BFS
큐를 사용
- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어진 정점을 나중에 방문하는 순회방법이다.
- 넓게 탐색
- 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택(모든 노드 아닌)
DFS VS BFS
큐를 사용
- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어진 정점을 나중에 방문하는 순회방법이다.
- 넓게 탐색
- 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택(모든 노드 아닌)
DFS VS BFS
- DFS 는 스택(혹은 재귀) , BFS 는 큐를 사용한다.
- BFS는 재귀적으로 동작하지 않는다.
최단 거리 문제를 푼다면 BFS를 사용합니다.
이동할 때마다 가중치가 붙어서 이동한다거나 이동 과정에서 여러 제약이 있을 경우 DFS로 구현하는 것이 좋습니다.
Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
구현
다음과 같은 로직을 생각하고 구현하였다.
add
-div
함수를 나누어 구현
function solution(numbers, target) {
let answer = 0;
let count = 0;
function add(number, count) {
if (numbers.length - 1 === number) {
if (count === target) {
answer++;
}
return;
}
add(number + 1, count + numbers[number + 1]);
div(number + 1, count - numbers[number + 1]);
}
function div(number, count) {
if (numbers.length - 1 === number) {
if (count === target) {
answer++;
}
return;
}
add(number + 1, count + numbers[number + 1]);
div(number + 1, count - numbers[number + 1]);
}
add(0, count + numbers[0]);
div(0, count - numbers[0]);
return answer;
}
solution([1, 1, 1, 1, 1], 3);
- 한개의 함수로 구현
사실 두개의 함수로 구현하는 경우 각 함수에서 더하기 빼기 작업을 해야함.
다음은 더하기 빼기 작업을 한 후 인자로 보내는 방식( 하나의 함수로 구현 )
function func(number, count) {
if (numbers.length - 1 === number) {
if (count === target) {
answer++;
}
return;
}
func(number + 1, count + numbers[number + 1]);
func(number + 1, count - numbers[number + 1]);
}
func(0, +numbers[0]);
func(0, -numbers[0]);
Reference
Author And Source
이 문제에 관하여([ALGORITHM NINJA] 프로그래머스DFS 1번 타겟넘버), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@rat8397/TIL-210510-DFS-타겟넘버
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
Author And Source
이 문제에 관하여([ALGORITHM NINJA] 프로그래머스DFS 1번 타겟넘버), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@rat8397/TIL-210510-DFS-타겟넘버저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)