dfs
-
[프로그래머스/JavaScript] 네트워크 (Feat. DFS, 조금씩 이해된다...)IT Study/프로그래머스 2023. 12. 13. 16:32
📊 1. 나만의 테스트 케이스 만들기 (많을수록 좋음) 아래와 같이 연결된 네트워크가 있다고 가정해봅시다. 0 / 1 ----/------- 4 \ / \ / 2 3 테스트 케이스 n = 5 computers = [[1, 0, 1, 0, 0], [0, 1, 1, 0, 1], [1, 1, 1, 0, 0], [0, 0, 0, 1, 0], [0, 1, 0, 0, 1]] 그래프의 형태로 나타내면 아래와 같을 것 같군요. (연결 상태 확인하기) 0 : [2] 1 : [2, 4] 2 : [0, 1] 3 : [] 4 : [1] 이 경우에는 "0, 1, 2, 4"와 "3"가 개별 네트워크로 연결되어, return(결과값)은 2여야 합니다. 🤔 2. 사고하기 (1) 0을 확인한다. (0) (2) 0에 연결된 아이는 2이..
-
[프로그래머스/JavaScript] 타겟 넘버 (Feat. DFS.. 재귀함수.. 너 뭔데)IT Study/프로그래머스 2023. 12. 1. 14:01
이 문제를 처음 봤을 때에는 어떻게 접근해야 할지 도무지 감이 오지 않았습니다. DFS, BFS를 제 손으로 구현해본 적이 없었기에 더욱 주춤하게 되는 문제였는데요. 문제를 풀어낸 과정에 대해 블로그 글로 정리하고자 합니다. 1. 무지성으로 들이대기 function solution(numbers, target) { var answer = 0; // 1. total (numbers 합계) 구하기 const total = numbers.reduce((accVal, curVal) => { return accVal + curVal; }) // 2. purpose ((total - target) / 2) 구하기 const purpose = (total - target) / 2; // 3. numbers 내에서 합..
-
[알고리즘] DFS, BFS 탐색 알고리즘 (Feat. JavaScript로 구현하기)IT Study/FE 2023. 11. 7. 16:07
탐색 알고리즘이란? 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘입니다. ⭐️ DFS(깊이 우선 탐색)이란? 시작점부터 갈 수 있는 정점까지 깊이있게 파고 드는 탐색 알고리즘 DFS 장단점 장점 1. 직관적인 코드, 구현이 용이 단점 1. 깊이가 깊어질수록 예측하기 어려운 메모리 비용 2. 최단 경로 파악 불가 DFS의 원리 *스택 (LIFO) push() : 배열 끝에 새로운 요소 추가 및 새로운 길이 반환 pop(): 배열의 마지막 요소 제거 및 그 요소 반환 A B D E F C G H I J 순으로 깊이를 기준으로 먼저 탐색하는 알고리즘입니다. 위 그림을 기준으로 DFS의 원리를 확인해보도록 하겠습니다. (1) A를 시작 정점으로, 스택에 A를 넣습니다. (스택 : A) (2) A를..