일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 29 | 30 | 31 |
Tags
- Python
- git
- 대학원
- SQL
- 컴퓨터비전
- 다시풀기
- 컨트리뷰톤
- level1
- Github
- 어렵다
- D3
- 내휴학생활중의아주큰일
- 프로그래머스
- SWEA
- java
- 대학원일기
- build
- WebOS
- LEVEL2
- BFS
- 자바
- MSBuild
- py
- 휴학
- level4
- Matrix Factorization
- 파이썬
- 안드로이드스튜디오
- level3
- androidstudio
Archives
- Today
- Total
목록DFS (2)
bit가 눈 앞에서 왔다갔다
DFS, BFS 판단 기준
DFS : 현재 정점에서 갈 수 있는 점들까지 (끝까지) - 모든 노드를 방문해야할 때 - 경로에 특징을 저장해둬야 하는 문제 - 검색 대상 그래프가 클 경우 - (BFS보다 간단하지만 느림) BFS : 현재 정점에서 연결된 가까운 점들부터 - 재귀적으로 동작하지 않음 - 최단거리, 임의의 경로 문제 - 규모가 작고 원하는 대상이 멀지 않을때 - 큐 사용, FIFO 원칙 둘 다 - 어떤 노드를 방문했는지 여부 검사 반드시! (or 무한루프,,)
Algorithm/Concept
2022. 2. 4. 17:40
py) BFS, DFS
DFS(Depth First Search) 깊이 우선 탐색: 시작 노드를 방문처리 하고 방문처리 되지 않은 노드로 진행 선택된 노드는 방문처리 되고 새로운 시작 노드가 되어 같은 방법을 반복하다가 방문처리 되지 않은 노드가 없을 경우 되돌아 감 BFS(Breadth First Search) 너비 우선 탐색: 시작 노드로부터 가까운 노드를 먼저 방문하고 멀리 떨어져 있는 노드를 나중에 방문. 시작 노드에서 인접한 노드들을 방문하고 그 노드들과 인접한 노드들을 방문 DFS-구현 가능한 방법 또는 활용하는 자료구조: 1. 순환호출(재귀함수) 2. 스택(Stack)- 순환호출 이용 def dfs(graph, v, visited): visited[v] =True print(v, end=' ') for i in g..
Algorithm/Concept
2021. 2. 11. 21:31