아이효 9. 알고리즘 수업

그래프란?

• G = (V(vertex), E(edge))

• 자료구조가 해야하는 것은 연산.
• 연산을 위해서는 입력, 삭제, 검색이 있어야 함.
• 그래프에서 원하는 것을 찾을 때, 모든 곳을 다 체크하는 것을 "순회(traversal)"라고 함.
• 그 방법으로 BFS, DFS가 있음.

BFS

• 한숨에 갈 수 있는 거리를 우선으로 순회하는 것.
• 시작점부터 근접한 것 순서대로 한 층위씩 가는 것.

DFS

• 깊이 가는 것을 우선해서 순회하는 것.
• 갈 수 있는 곳까지 끝까지 가서 원점으로 돌아오는 것.

최단 거리 알고리즘

• 문제를 다음과 같이 정의함.
• def. I "G"는 간선의 가중치가 주어짐. --> 거리 개념, 크기 개념을 준다.
• 그래서 보통 2개의 지점(출발지(source), 목적지(destination))가 주어짐.
• 최단 거리에도 종류가 있음. 출발지나 도착지의 쌍이 여러개일 수 있음.

  하나의 출발지, 하나의 도착지
  여러 개의 출발지, 하나의 도착지
  하나의 출발지, 여러 개의 도착지
  여러 개의 출발지, 여러 개의 도착지

• 환원 개념: 출발지, 도착지가 여러 개일 때 가중치가 0인 거리를 가진 하나의 점으로 모아서 그 집합과 구해야 하는 것의 거리를 구하는 방법.

3가지 알고리즘
1. 다익스트아: single sourse - multiple destination

• 아이디어는 그리디 방법.

2. 벨만코드: single sourse - multiple destination
3. 플로이드워셜: multiple sourse - multiple destination

오늘이 알고리즘 수업의 마지막이었습니다.
피곤해서 조는 바람에 많이 못들었는데, 갑자기 마지막 강의라고 하셔서 잠이 달아나버렸어요.
지효님 고생하셨습니다. 그리고 감사합니다.
덕분에 많은 것을 처음 알 수 있었고 앞으로 잘 나아갈 수 있었어요.
이 시대의 참 선생님이십니다!

사랑해요 지효님!