코딩테스트에서 자주나오는 BFS, DFS 는 둘 다 그래프 탐색 알고리즘이지만, 탐색하는 방법에서 차이가 있다.
그래프 탐색 알고리즘 대표적인 문제 유형
1. 경로탐색 유형 (최단거리, 시간)
2. 네트워크 유형 (연결)
3. 조합 유형 (모든 조합 만들기)
BFS (Breadth First Search) : 너비 우선 탐색
- 구현 방법: 큐(Queue), 연결리스트(Linked List)
장점
최단 경로를 보장한다.
단점
메모리를 많이 사용한다.
DFS (Depth First Search) : 깊이 우선 탐색
- 탐색에 있어 '경로'에 대한 정보가 필요할 때 사용한다.
- 코딩테스트에서 가장 많이 나오는 문제
- 구현 방법: 재귀함수, 스택(Stack)
- 초기화, 실행 부분을 따로 만들어주는 것이 중요하다.
장점
적은 메모리를 사용한다.
BFS 보다 빠르다.
단점
빠를수도있고 탐색을 다 해야할경우 느릴수도 있다.
정답에 도착하면 탐색을 종료하기 때문에 최단거리라는 보장이 없다.
참고
[알고리즘] 탐색 BFS, DFS _ 백준 1260 파이썬
○ 탐색 알고리즘 코딩테스트 단골 문제 BFS, DFS 흔히 BFS, DFS + 재귀 문제만 잘 풀어도 코딩테스트에 통과할 수 있다고 하는데요. 그만큼 단골문제로 등장하는 BFS(너비 우선 탐색), DFS(깊이 우선 탐
ebbnflow.tistory.com
3. 이코테 - DFS BFS 개요 (메인 코드)
Stack 사용 시 그냥 list를 활용stack = \[]stack.append(4)stack.pop() Queue 사용 시 라이브러리 활용 <중요>from collections import dequequeue = deque() - q
velog.io
DFS BFS 핵심 설명 (중요)
링크 : https://covenant.tistory.com/132링크 : https://velog.io/@taehyeon96/3.-%EC%9D%B4%EC%BD%94%ED%85%8C-DFS-BFS-%EA%B0%9C%EC%9A%94-%EB%A9%94%E
velog.io
[알고리즘] BFS with Python
💡 BFS 알고리즘 Breath-First Search, 그래프에서 가까운 부분을 우선적으로 탐색하는 알고리즘이다. 너비 우선 탐색이라고도 한다. 데이터가 N개 있을때 O(N)시간 복잡도를 가진다. 일반적인 경우
doing7.tistory.com
파이썬(python) 알고리즘 - DFS, BFS
DFS (깊이 우선 탐색) 깊이를 우선으로 탐색하는 알고리즘 시작 노드에서 방문하지 않은 인접 노드를 큐에 삽입 (방문 했음을 표시) 더 이상 방문할 수 없는 경우 탐색 중단하고 이전 상태로 되돌
11001.tistory.com
'개발공부' 카테고리의 다른 글
| CDN 이란? purdge (0) | 2022.10.24 |
|---|---|
| 서버리스(serverless) 란? (0) | 2022.10.21 |
| 릴리즈 노트란? 그리고 작성하는 방법과 Tip (0) | 2022.08.18 |
| Technical Writer 테크니컬 라이터란? (0) | 2022.08.16 |
| Git 브랜치 전략 (0) | 2022.07.10 |
댓글