[데브코스 Day6] 2022.10.14

📖오늘 배운  것

 

"DFS와 BFS"

 

https://seing.tistory.com/29

 

---

 

깊이 우선 탐색(DFS)

---

그래프 탐색 알고리즘으로 최대한 깊이 내려간 뒤 더 이상 내려갈 곳이 없으면 옆으로 이동한다. 

 

• 길을 정해서 갈 수 있는 한 최대한 깊이 갔다가 더 이상 길이 없음면 가장 최근 분기점의 다른 길로 가보는 것이다.
• 모든 노드를 방문 할 수 있다.

 

 

특징

1. stackdmf 이용해서 구현할 수 있다.
2. v가 정점의 수이고 E가 간선의 수일 때 BFS의 시간 복잡도는 O(V+E)이다.

 

 

• 관련 알고리즘 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43162

프로그래머스

 

 

너비 우선 탐색(BFS)

---

그래프 탐색 알고리즘으로 인접한 노드를 먼저 방문한다.

https://seing.tistory.com/29

• 최단 경로를 찾고 싶을 때 너비 우선 탐색을 이용한다.

 

 

특징

1. queue를 이용하여 구현할 수 있다.
2. v가 정점의 수, E가 간선의 수일 때 BFS의 시간 복잡도는 O(V+E)이다.

 

 

💭배운 점

오늘은 자료구조 실습 위주로 진행했다. 어떻게 사용하는지 이해는 되는데 아직 문제에 적용하기엔 실력이 부족한 것 같다. 문제를 많이 풀어보고 관련된 코드들을 많이 보고 해석해보는 연습이 필요할 것 같다.

 

 

 

💻앞으로 배우고 싶은 것

-자료구조 연습하기

 

 

참고자료

프로그래머스 데브코스 강의

https://devuna.tistory.com/32

https://seing.tistory.com/29