Algorithm. 2주차 스터디 정리

1. 백트래킹

2. 그래프의 기본과 탐색

3. 그래프의 최소 비용 문제

1. 백트래킹

• 해를 찾는 도중 해가 아니면 되돌아가서 다시 해를 찾는다.

2. 그래프의 기본과 탐색

• 객체들 사이의 연결 관계 표현
• 정점(vertex)집합과 정점을 연결하는 간선(edge)집합으로 구성
• 1) 깊이 우선 탐색(DFS)
  • 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
• 2) 너비 우선 탐색(BFS)
  • 시작 정점에서 인접한 정점을 먼저 모두 차례로 방문

3. 그래프의 최소 비용 문제

• 프림 알고리즘
  • 한 정점에 연결된 간선들 중 하나씩 선택하며 최소 신장 트리를 만드는 알고리즘
• 크루스칼 알고리즘
  • 최소 가중치 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘
• 다익스트라 알고리즘
  • 시작 정점에서 거리가 최소인 정점부터 선택해 나가면서 최단 경로를 구하는 알고리즘

4. 활동 사진

5. Github Repository

https://github.com/ohdowon064/AlgorithmStudy

ohdowon064/AlgorithmStudy