25Days) 자료구조/알고리즘(5) - Search Algorithm (Tree traversal, BFS/DFS)

◉ 학습목표

1. 트리 순회 방식인 전위 순회, 중위 순회, 후위 순회를 이해할 수 있다.
2. 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)을 이해하고 장단점을 고려해 알맞는 자료구조를 활용할 수 있다.

1. Tree traversal (트리 순회)

⦿ 학습내용

☞ 트리 순회 (Tree traversal)

✔︎ 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것
✔︎ 트리 구조에서 노드를 순차적으로 순회할 때의 순서는 항상 왼쪽 → 오른쪽
✔︎ 종류로는 전위 순회, 중위 순회, 후위 순회방식이 있음

☞ 전위 순회 (preorder traverse)

✔︎ root → left → right 순으로 순회

☞ 중위 순회 (inorder traverse)

✔︎ left → root → right 순으로 순회

☞ 후위 순회 (postorder traverse)

✔︎ left → right → root 순으로 순회

2. BFS (Breadth-First-Search) / DFS (Depth-First-Search)

⦿ 학습내용

☞ 너비 우선 탐색 (BFS, Breadth-First-Search)

✔︎ 너비를 우선적으로 탐색하는 방법
✔︎ 루트(root)로부터 가까운 정점부터 탐색

☞ 깊이 우선 탐색 (DFS, Depth-First-Search)

✔︎ 깊이를 우선적으로 탐색하는 방법
✔︎ 하나의 경로를 끝까지 탐색한 후 다음 경로로 넘어감

◉ 느낀 점

☞ 이론적으로는 정말 다 이해가 된다. 그렇지만 항상 코플릿에 알고리즘 문제풀이를 할 때, 분명 Tree구조인지, Graph구조인지, 어떤 자료구조를 사용해야하는 지 문제에 명시가 되있음에도 항상 어려움을 겪고 있다.. 경험 부족이겠지 🥲 알고리즘 문제풀이가 절실하다.. 머리가 나쁘면 몸을 고생시켜야 한다!! 많은 문제를 풀어보자❗️

◉ 내일의 키워드

・ Time Complexity (시간복잡도)
・ Greedy Algorithm (탐욕 알고리즘)
・ Implementation (구현)