dfs 2

[프로그래머스/자바] 타겟 넘버_43165

문제 및 코드 1. 생각 // 생각 // numbers를 돌면서 가지치기 하면서 양수 음수로 나누어 numbers 끝까지 경우를 구한 후 수 다 더하면 되는데.. // 깊이 탐색하면 되니까 dfs인듯 // 구현 // numbers의 맨 첫 원소를 기준으로 dfs 돌기 // dfs // 들어온 원소의 인덱스, 지금까지의 합, numbers 배열을 매개변수로 받는다 // 들어온 인덱스 다음부터 다시 dfs를 돈다 // 이때 음수 양수로 나누어 dfs를 돌게 해야 한다 // 들어온 인덱스가 numbers의 길이와 같으면 // 지금까지의 합이 target과 같은지 비교한 후 답을 1 증가 ---- // 생각 // numbers 각각을 돌 때 플러스 마이너스 각각을 붙여가며 가지치기해서 결과를 확인해야 함 \ /..

코딩테스트 2023.07.19

[알고리즘] DFS(깊이 우선 탐색)

1. 개념 주어진 어떤 정점을 출발하여 체계적으로 그래프의 모든 정점들을 순회하는 것을 그래프 순회라고 한다. DFS는 그래프를 순회하는 방법 중 하나이다. DFS는 시작 노드부터 출발해서, 시작 노드와 인접한 것 중 하나를 방문한다. 그리고 그 방문한 것과 인접한 것을 또 방문한다. 이렇듯 시작 노드부터 인접한 것을 따라 계속 그걸 방문해나가는 방법이다. 마치 아래 방향으로 쭉 깊이있게 탐색하는 것 같다. 만약, 더 이상 방문할 것이 없다면 이전 노드로 돌아와서 이전 노드와 인접해 있지만 아직 방문하지 않은 노드를 방문해 나간다. 2. 예시 위와 같은 그래프를 DFS로 방문하면 다음과 같다. 같은 단계일 경우 오름차순으로 노드를 방문한다. 1 -> 2 -> 6 -> 8 -> 3 -> 5 -> 4 -> ..

알고리즘 2023.04.03