[항해99]99클럽 코테 스터디 4일차 TIL + 깊이/너비 우선 탐색 (DFS/BFS)

 

 

 

오늘도 깊이 우선 탐색과 너비 우선 탐색입니다.

 

1.  오늘의 학습 키워드 : 깊이 우선 탐색(DFS)/너비 우선 탐색(BFS)

어제 DFS/BFS가 뭔지 살펴보았다면 오늘은 특징을 간략하게 공부했습니다.

 

DFS

• 모든 노드를 방문하고자 할때 사용되는 방법
• DFS는 BFS(너비 우선 탐색)에 비해 비교적 간단함 
• 검색 속도는 DFS가 BFS에 비해 느림
• 스택이나 재귀함수를 이용하여 구현

BFS

• 최단 경로를 찾고자 할때 사용 : 위 그림과 같이 BFS는 수평으로 탐색하는 방법이기 때문에 [1-3-7], [1-4-8]과 같은 최단 경로를 중간에 찾을 수 있습니다.
• 예를 들어 A와 B 사이의 관계를 알고 싶을 때 DFS의 경우 모든 경우를 고려해야 될 수도 있지만, BFS는 가까운 관계부터 탐색을 할 수 있습니다. 
• 큐를 이용하여 구현

* 코테 단골 문제인 만큼 기출이 많은 것 같은데 서치하다가 DFS/BFS 문제들을 발견해 첨부합니다.

https://wikidocs.net/206678

DFS/BFS

 

2.  오늘의 문제 :  Find a Corresponding Node of a Binary Tree in a Clone of That Tree

https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/description/

 

3.  풀이 

https://velog.io/@stayplz/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98LeetCode-1379.-Find-a-Corresponding-Node-of-a-Binary-Tree-in-a-Clone-of-That-Tree

[알고리즘]_[LeetCode]- 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

중위순회를 가지고 풀었다고 합니다. 사실 잘 모르겠어서 참고해서 풀었어요.

3.  회고 

첫째날에 비해 제대로 공부를 안하고 있다는 생각이... 우선탐색에 관해 엄청나게 어렵다고 생각해서 진입장벽이 느껴진다. 그래도 코테를 통과하려면 이정돈 해야지 파이팅!!!!!

 

 

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL