TIL(26) 21-10-22 : 탐색(힙, 그래프, DFS, BFS)

Facts

✅ 힙 2문제

✅ DFS/BFS 3문제

 

Findings

BST의 평균의 시간이 걸리는 케이스와 최악의 시간이 걸리는 케이스

✔️  Binary Search Tree

아래의 조건들을 다 만족하는 트리를 말한다.

• 이진각 노드가 2개 이하의 자식 노드를 갖는 트리
• 노드가 왼쪽 자식 노드를 가진다면 그 노드가 가지는 값은 그 부모 노드가 가지는 값보다 작다.
• 노드의 오른쪽 자식 노드를 가진다면 그 노드가 가지는 값은 그 부모 노드가 가지는 값보다 크다.

평균의 시간 복잡도는 O(logN)

최악의 시간 복잡도는 O(N)이다.

그 이유는 Binary Search Tree의 시간복잡도는 O(height)이기 때문이다.

 

평균의 시간 복잡도는 O(logN)이지만, 이는 트리가 균형잡혀있을 때의 평균 시간복잡이다.

트리가 아래의 사진과 같이 구성이 되어있을 경우, 최악의 경우 링크드 리스트와 동일한 성능을 보여준다.

출처 : https://www.gatevidyalay.com/time-complexity-of-bst-binary-search-tree/

 

DFS / BFS

그래프를 탐색하는 방법은 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)가 있다.

✔️  DFS (Depth-First Search)

: 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

출처 : https://developer-mac.tistory.com/64

 

현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색

스택 또는 재귀함수로 구현

 

✔️  BFS (Breadth-First Search)

: 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

 

출처 : https://developer-mac.tistory.com/64

현재 정점에 연결된 가까운 점들부터 탐색 

큐를 이용해서 구현

✔️  DFS와 BFS의 시간복잡도

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하다.

DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 된다.

 

N은 노드, E는 간선일 때

인접 리스트 : O(N+E)
인접 행렬 : O(N²)