부트캠프 62일차 (자료구조-Tree, Graph)

오늘의 생각

 

만신창이가 되어버린 나

트리와 그래프에 대해 배웠다. 하루만에 배우기에는 너무 벅찬 양이었던 것 같다.

 

여기에 더해 BFS, DFS까지 배워야되서 우려한대로 연습 문제를 풀려니 눈 앞이 캄캄했다.

 

특히 그래프 관련된 문제는 시각화가 힘들어서 전체적인 구도를 잡고 논리 구조를 구성해 나가는 것이 매우 어려웠다. (왜 배열에서 1이 간선이란 말인가...)

 

요즘 알고리즘 공부를 시작하면서 쉬운 단계의 알고리즘을 풀다보니 나도 모르게 자만하고 있었던 것 같다..

 

알고리즘 풀 때 작은 다짐
1. 문제가 요구하는 바를 "완전히" 이해했는지 확인하기
2. 의사 코드를 꼭 적어서 논리 구조 정리하기
3. 작성 중에도 왜 해당 로직이 필요하고 어떤 결과값이 나오는지 생각하기
4. 어렵다고 레퍼런스 찾아보지 말고, 현재 겪은 문제를 작은 단위로 나눠보기
5. 나눈 단위의 문제부터 천천히 해결 방법을 찾아보고 이해하기

 

---

오늘의 키워드

Tree, 선형 구조, 비선형 구조, 사이클Cycle, 루트Root, 간선Edge, 노드Node, 리프 노드Leaf Node, 깊이, 레벨, 높이, 서브 트리Sub Tree, 정 이진 트리Full binary tree, 포화 이진 트리Perfect binary tree, 완전 이진 트리Complete binary tree, 이진 탐색 트리Binary Search Tree, 트리 순회Tree Traversal, 전위 순회preorder traverse, 중위 순회inorder traverse, 후위 순회postorder traverse, 그래프, 정점Vertex, 인접 행렬, 인접 리스트, BFS(Breadth-First Search), DFS(Depth-First Search)

 

---

오늘의 학습내용

• 트리의 정의, 구조 및 특징
• 트리 구조의 레벨과 서브 트리
• 이진 트리의 정의 및 종류
• 이진 탐색 트리의 정의 및 특징, 탐색 과정
• 트리 순회 사용법 및 종류
• 그래프의 정의, 구조 및 표현 방식 (인접 행렬, 인접 리스트)
• BFS와 DFS의 차이

 

---

어려웠던 keyword / 활용한 질문

 

Q. 이진 탐색 트리의 문제점이 있다면, 무엇인가요?

 

A. 이진 탐색 트리는 트리 안에 찾고자 하는 값이 없더라도 연산 및 탐색을 계속해서 진행해야 합니다. 

 

Q. 그래프의 규모가 작고 depth가 얕다면 어떤 탐색 기법을 고려하는 것이 좋을까요?

 

A. 너비 우선 탐색(BFS)을 고려하는 것이 좋습니다. 깊이가 얕기 때문에 가까운 정점부터 탐색하는 것이 효율적이기 때문입니다. 반대로 만약 깊이가 깊다면 깊이 우선 탐색(DFS)를 고려하는 것이 좋습니다.