헷갈리는 부분들 정리.md

• 트리는 그래프의 특별한 종류

  • 트리 : 무방향이면서 사이클이 없는 연결 그래프(Undirected Acyclic Connected Graph)

  • 그래프의 한 종류니깐 그래프의 구현과 똑같이 stl vector로 간선 정보를 저장하면 끝

• 이진탐색트리

  • 내가 그냥 class 만들어서 구현함...
  • 바킹독에서는 left child, right child 만들어서 구현
  • 전위 순회, 중위 순회, 후위 순회

• 최소 비용 신장 트리(MST)

  • MST를 만드는 알고리즘 : 크루스칼 알고리즘, 프림 알고리즘

  • 이전 강의들에서는 간선을 vectoradj[10]에 저장했는데 크루스칼 알고리즘에서는 간선을 크기 순으로 정렬하는 과정이 필요하기 때문에 전부 tuple<int,int,int> edge 배열에 저장해둡니다.

  • 이것도 결국 주어진 그래프에서 Minimum Spanning Tree를 구하는 거니깐!!! 그래프의 구조를 사용하는 듯! 근데 여기서는 가중치의 값까지 필요해서 vector 대신 tuple을 사용!

• 그래프

  • 구현 방법 2가지 : 인접 행렬, 인접 리스트

  • stl vector를 사용해서 구현 (인접 리스트 방법)

  • class 없이 stl vector로 간선만 저장하면 끝!

  • DFS, BFS

바킹독에서 DFS, BFS를 여러곳에서 소개한 이유!

1. 그래프
2. 다차원 배열 - Flood Fill
3. 트리

• BFS, DFS는 그래프 자료구조에서 모든 정점을 순회하기 위한 알고리즘
• 다차원 배열이 그래프 자료구조의 특수한 형태여서 사용 가능
• 기본적으로 트리는 그래프의 특별한 한 종류이기 때문에 이전 장에서 배운 BFS, DFS 알고리즘을 그대로 적용시킬 수 있습니다

알고리즘 ToDo

• 바킹독 - 프림!

• 바킹독 - 트리!

• 바킹독 - 위상 정렬!

• 바킹독 - 0x0D강 - 해쉬, 이진트리, 힙

• DS 책 - 탐색2

• DS 책 - 우선순위 큐 & 힙

• 테이블과 해쉬

• 그래프에서 DFS구현.. 다시 해야될듯... 재귀부분도 안봄!!!

• 계산복잡도 구하는 방법 확실하게!!!