경일 메타버스 20220628 13주차 2일 수업내용. 자료구조와 알고리즘-그래프, 최단 경로, 오답노트

자료

https://docs.google.com/document/d/1wUms27Vj8si-jEjfRQJwSvsQ2CJNCv4IU6GOtesY4TE/edit

백준 풀이

2022. 06. 27 이진 검색 예제 : 백준 2110번 공유기 설치 풀이

2022. 06. 27 그래프 예제 : 백준 1260 DFS&BFS 옳은 풀이

• DFS는 위 함수처럼 재귀적으로 구현하는 것이 일반적.

오답노트 : 백준 2110

• 백준 2110 공유기 설치
  접근법이 잘못 되었다. 다시 풀어볼 것.
  범위는 일단 최대로 잡는다.
  -> 조건에 안 맞으면 제외되도록 하면 된다.

  2022. 06. 27 이진 검색 예제 : 백준 2110번 공유기 설치 풀이

매개 변수 탐색 (Parametric Search)

• 이진 검색을 이용하여 조건을 만족하는 최댓값을 구하는 방법.

자료구조 교안 해답

최선문 교수 GitHub

최단 경로(Shortest Path)

• 가중치 그래프에서 두 정점을 연결하는 경로 중 가중치의 합이 최소인 경로.

• 최단 경로를 구하기 위해 간선이 없다면 무한대 값으로 저장.
  ⇒ 막힌 길

• 가중치가 음수여선 안된다.

• 최단 경로를 구하는 알고리즘에서는
  다익스트라 알고리즘과 플로이드 알고리즘이 있다.

다익스트라 알고리즘(dijkstra algorithm)

• 하나의 시작 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다.

• 무방향 그래프, 방향 그래프 모두 적용 가능하다.

• 기본 원리는 시작 정점에서 가장 가까운 정점을 선택하여 추가하면서 추가된 모든 정점에 대한 최단 경로를 구해가는 과정이다.

A* 알고리즘

• 다익스트라 알고리즘을 확장한 최단 경로 알고리즘이다.

• 가중치를 계산할 때, 허용적 휴리스틱(admissible heuristic)을 사용한다.

• 휴리스틱이 0이라면 다익스트라 알고리즘과 정확히 일치한다.

• 휴리스틱으로는 맨하탄 거리, 유클리드 거리, 코사인 유사도 등이 쓰인다.

플로이드(floyd) 알고리즘

• 모든 정점 사이의 최단 경로를 구하는 알고리즘이다.