다익스트라2

• 

  [백준] 14938 서강그라운드 14938번: 서강그라운드 (acmicpc.net) 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 문제 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 .. TIL/SW&백준 문제 리뷰 2021. 8. 23.

• 

  210709 벨만-포드(Bellman-Ford), 다익스트라(Dijkstra) 최단 경로(Shortest Path)를 찾는 대표적인 알고리즘들 중 일부 벨만-포드(Bellman-Ford) 벨만포드는 가중치가 음수일 경우에도 사용가능 ( 다익스트라와의 차이점 ) 초기화 : 간선 검사 순서 임의로 정하는 등등 앞서 정한 순서대로 모든 간선 확인하며 Relax ( 정점에 기존 보다 더 낮은 가중치로 도달할 수 있으면 값 갱신 == 최단거리 값 갱신) 해줌 정점의 개수 - 1 번 만큼 반복 시간복잡도 : ( 간선의 개수 ) * ( 정점의 개수 -1 ) => O ( 간선의 개수 * 정점의 개수 ) 다익스트라(Dijkstra) Greedy 알고리즘이라고 할 수 있음 그래프 내의 특정 정점에서 갈 수 있는 모든 정점들까지의 최단경로를 구하는 알고리즘 효율적, 실생활에서 많이 사용됨 ex) gp.. 미가공 필기(알고리즘) 2021. 7. 13.