YJ_Scribbles

★ 최단 경로(Shortest Path) 문제 - 주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제 ☆ 최단 경로를 찾는 가장 대표적인 알고리즘 - 다익스트라(Dijkstra) 최단 경로 알고리즘 ☆ 다익스트라 알고리즘 - 주어진 출발점에서 시작 - 출발점으로부터 최단 거리가 확정되니 않는 점들 중에서 출발점으로부터 가장 가까운 점을 추가하고, 그 점의 최단 거리를 확정 ★ Dijkstra(다익스트라) 알고리즘 ShortestPath(G, s) 입력: 가중치 그래프 G=(V,E), |V|=n , |E|=m 출력: 출발점 s로부터 (n-1)개의 점까지 각각 최단 거리를 저장한 배열 D 1. 배열D를 ∞로 초기화시킨다. 단, D[s]=0으로 초기화한다. // 배열 D[..

★ 최근점 점의 쌍 찾기 - 차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제 ☆ 간단한 방법 - 모든 점에 대하여 각각의 두 점 사이의 거리를 계산하여 가장 가까운 점의 쌍을 찾기 - 5개의 점이 아래의 [그림]처럼 주어지면, 1-2, 1-3, 1-4, 1-5, 2-3, 2-4, 2-5, 3-4, 3-5, 4-5 사이의 거리를 각각 계산하여 그 중에 최소 거리를 가진 쌍이 최근접 점의 쌍이 됨. ㅇ 비교해야 할 쌍은 몇 개인가? - nC₂ = n(n-1)/2 - n=5이면, 5(5-1)/2 = 10 - n(n-1)/2 = O(n²) - 한 쌍의 거리 계산 : O(1) - 시간복잡도 : O(n²)xO(1) = O(n²) ☆시간복잡도가 O(n²)보다 효율적인 방법..