(S2W2) TIL 26일차 220307 (기초 자료구조)

오늘의 학습목표

• 트리 및 그래프의 탐색 기법에 대해 이해할 수 있다.
  • 트리 순회(Tree Traversal)를 이해할 수 있다.
    • 전위 순회 (preorder traverse)
    • 중위 순회 (inorder traverse)
    • 후위 순회 (postorder traverse)
  • BFS와 DFS의 개념을 이해하고 알고리즘 문제에서 사용할 수 있다.
• 자료구조를 활용하여 알고리즘 문제에 접근할 수 있다.

학습내용

BFS (Breadth-First Search)

너비 우선 탐색이라고하고, 주로 두 정점 사이의 최단 경로를 찾을 때 사용합니다.

만약 경로를 하나씩 전부 방문한다면, 최악의 경우 모든 경로를 다 살펴봐야 합니다.

 

DFS (Depth-First Search)

깊이 우선 탐색이라고 하고, 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용합니다. BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있습니다.

 

DFS와 BFS는 모든 정점을 한번만 방문한다는 공통점을 지니고 있지만, 사용할 때의 장단점은 분명하기에 상황에 맞는 탐색 기법을 사용해야합니다.

 

오늘의 회고

오늘 코플릿도 지난주 코플릿과 마찬가지로 어려웠고, 이번 주말이용해서 더 공부해야겠다고 생각했습니다.

알고리즘이 저에겐 좀 많이 어려워서 섹션2가 끝날때 까지 계속 주말 시간이용해서 봐야겠습니다.