티스토리 뷰
들어가기 전에, 아주 짧은 요약을 해 보자면
BFS는 해당 노드 주변을 중심으로 조사하고
DFS는 해당 노드의 끝까지 파고드는 느낌으로 생각하시면 좋습니다.
다음은 아래의 글을 번역했습니다.
When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)?
I understand the differences between DFS and BFS, but I'm interested to know when it's more practical to use one over the other? Could anyone give any examples of how DFS would trump BFS and vice...
stackoverflow.com
- 그렇게 깊지 않고 해답이 트리의 뿌리에서 그닥 떨어져 있지 않다는걸 알면 BFS를 쓰세요.
- 트리의 깊이가 상당히 깊은데 해답이 몇 개 없다면 DFS를 사용하는 방법은 깊이를 전부 다 서치하므로 시간이 엄청나게 걸릴거라 BFS가 낫습니다.
- 트리가 깊다기보다 엄청나게 넓으면 BFS의 사용은 메모리를 상당히 잡아먹을 것 입니다. 때문에, BFS의 사용은 실용적이지 못할 거에요.
- 해답들이 많지만 트리의 깊숙한 곳에 있다면 BFS는 실용적이지 못할 것 입니다.
- 트리가 엄청 깊으면 깊이를 제한하는 것도 필요할 것 입니다.
물론 말이 그렇다는거지 일단 경험해보셔야 알 겁니다.
결국 결론은
1. 해당 트리가 깊은가
2. 해당 트리가 넓은가
에서 나뉘는 것 같네요.
DFS와 BFS를 접하고 개념의 감을 잘 잡게 해 준 것 같습니다.
'Basic_Studies > 알고리즘 이론' 카테고리의 다른 글
[알고리즘] 선택정렬 (w/파이썬) (0) | 2021.07.29 |
---|---|
[알고리즘] 버블정렬(w/python) (0) | 2021.07.29 |
[자료구조] 해시 테이블(Hash Table)(w/파이썬) (0) | 2021.07.24 |
[자료구조] Linked-List(연결리스트) 기초 (python) (0) | 2021.07.14 |
[알고리즘 이론] 그리디 알고리즘(탐욕법) (0) | 2020.10.10 |
- Total
- Today
- Yesterday
- css 글래스모피즘
- 리액트 스크롤
- 화이팅
- 움직이는 글래스모피즘
- 리액트
- 리액트 파라미터 넘기기
- 글래스모피즘 애니메이션 구현
- bs4 크롤링
- 파이썬 크롤링
- 파이썬 flask
- getserversideprops redirect
- dvd 효과
- next.js 리다이렉트
- nextjs 스크롤
- 카페음료테스트
- 리액트 컴포넌트
- 리액트 라우터
- Til
- 글래스모피즘 구현
- vscode venv
- css marquee
- NextJS
- 백준 10989 파이썬
- 자바스크립트
- nextjs 파라미터 넘기기
- react router
- 10989 파이썬
- nuxt 공식문서
- nuxt 공식문서 한글
- 파이썬 정렬
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |