공부기록/Algorithm

Dijkstra 다익스트라 Floyd-Warshall 플로이드 워셜 어떤 문제에 사용할까? 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 노드/간선 갯수 적을 떄 사용 사용처 가중 그래프(weighted graph)에서 하나의 정점으로부터 시작하여 각각의 노드로 가는 각각의 최단경로를 찾는 데 효율적. 가중 그래프에서 정점간 모든 쌍 사이에서 가장 짧은 경로를 찾는데 적합함. (all-pairs shortest path algorithm) source - usecase a single-source shortest path algorithm a multi-source shortest path algorithm 정점 방문 방..

학습 자료 (레퍼런스) https://www.youtube.com/watch?v=xeSz3pROPS8 https://www.geeksforgeeks.org/topological-sorting/ 위상정렬 그래프 정점의 선형적 정렬(ordering)으로, vertex U에서 V로 가는 방향성이 유지된 채 정렬되는 것. 즉, U가 V를 가리킨다면(향한다면) 위상정렬 시 U는 언제나 V보다 먼저 등장해야 한다. 왜냐하면 U를 거쳐야 V를 갈 수 있기 떄문이다. 방향성이 있고 싸이클이 없는 그래프인 DAG(directed acycled graph) 에서만 가능하다. 선형 시간 복잡도를 보임 (O(V+E)) 결과물은 unique하지 않다. (레벨간의 순서 stable은 보장하지만, 결과물이 언제나 동일하지 않다.)..

DFS vs BFS, 언제 무엇을 써야 할까? 어느 탐색 전략이 좋은지는 그래프의 모양에 따라 효율이 갈리니 모양과 용도를 보고 선택하자! DFS>BFS DFS가 BFS보다 우월한 성능을 낼 때 높은 분기 계수(branching factor)를 가진 두껍게 연결된 그래프에서(thickly connected graphs DFS가 BFS보다 더 좋은 성능을 낸다.[같은 뜻의 비슷한 표현] 그래프의 간선이 많고(=밀도가 높다/dense하다) 평균 인접 노드 수가 노드 수에 비해 높다면 너비 우선 검색은 긴 대기열을 가진다. 그에 비해 DFS는 적은 스택을 가지므로 DFS가 좀 더 성능이 좋을 것이다.) 해답(solution)이 가장 먼 자식 노드에 있을 것 같으면 DFS가 더 좋은 선택이 된다. BFS>DFS..