Graph5 [MIT 6.006 정리] Lec 18. 그래프 (최단 경로 알고리즘_ 다익스트라 가속화) * 본 포스팅은 기본적으로 edwith 플랫폼을 통해 제공되고 있는 MIT 6.006 Introduction to Algorithms (Fall 2011) 강의 내용을 바탕으로 정리한 것입니당 :D ------- * ------- * ------- * ------- * 단일 시작 단일 도착 다익스트라 이전까지 일반적인 최단 경로 알고리즘 (다익스트라 / 벨만-포드 등) 은 '하나의 시작점과 임의의/모든 도착점에 대해 최단 경로를 구하는 문제 (single-source, any/all destination)' 를 가정했음 하지만 모든 도착점이 아닌 특정한 하나의 도착점에 대해서만 최단 경로를 구하면 되는 문제라면, 몇 가지 최적화를 통해 알고리즘 실행 시간을 줄일 수 있음! 최악 시간 복잡도는 변하지 않으.. 2021. 3. 30. [MIT 6.006 정리] Lec 17. 그래프 (최단 경로 알고리즘_ 벨만-포드 알고리즘) * 본 포스팅은 기본적으로 edwith 플랫폼을 통해 제공되고 있는 MIT 6.006 Introduction to Algorithms (Fall 2011) 강의 내용을 바탕으로 정리한 것입니당 :D ------- * ------- * ------- * ------- * 일반적인(generic) 최단 경로 알고리즘 Recap 알고리즘을 시작할 때, 시작점인 정점 u 로부터 정점 u 까지의 최단 경로의 가중치는 0 으로 두고, 나머지 정점들과의 최단 경로의 가중치는 무한대로 설정함 알고리즘을 진행하면서, 그 중 일부는 무한대의 값을 그대로 유지하고, 다른 일부는 유한한 최단 경로의 가중치 값을 얻게 될 것이며, 음의 순환을 갖고 있는 그래프라면 일부 경로의 가중치는 정의되지 않을 것 일반적인 최단 경로 알고.. 2021. 3. 30. [MIT 6.006 정리] Lec 16. 그래프 (최단 경로 알고리즘_ 다익스트라 알고리즘) * 본 포스팅은 기본적으로 edwith 플랫폼을 통해 제공되고 있는 MIT 6.006 Introduction to Algorithms (Fall 2011) 강의 내용을 바탕으로 정리한 것입니당 :D ------- * ------- * ------- * ------- * 최단 경로 알고리즘의 기본 구조 Recap d[v] : 출발점 s 부터 정점 v 까지의 (현재 시점에서의) 최단 경로의 길이 d[s] = 0, d[v] = inf. (for any v) 로 초기화 후, 완화(relaxation) 과정을 통해 d[v] 값을 줄여 나감 모든 정점 v 에 대해 d[v] = delta[v] (출발점에서 해당 정점까지의 실제 최단 경로(a shortest path) 의 길이) 로 수렴할 때까지 반복 후 알고리즘 종.. 2021. 3. 17. [MIT 6.006 정리] Lec 15. 그래프 (최단 경로 알고리즘_brute-force) * 본 포스팅은 기본적으로 edwith 플랫폼을 통해 제공되고 있는 MIT 6.006 Introduction to Algorithms (Fall 2011) 강의 내용을 바탕으로 정리한 것입니당 :D ------- * ------- * ------- * ------- * 가중 그래프 (Weighted graphs) 간선에 가중치가 부여된 그래프 구조 (모든 간선이 갖는 가중치가 동일하지 않음!) --> 더욱 다양한 종류의 문제에 대해 적용 가능함 G = (V, E, W) W = 각 간선의 가중치를 나타내는 가중치 함수. W: E(간선 집합) → R(실수 집합) 다익스트라 알고리즘; 음수가 아닌 (non-negative) 가중치를 가정. O(V log V + E) 의 복잡도. 벨만-포드 알고리즘; 음수인 가.. 2021. 3. 16. [MIT 6.006 정리] Lec 13. 그래프 (그래프 탐색, 너비 우선 탐색 (BFS)) * 본 포스팅은 기본적으로 edwith 플랫폼을 통해 제공되고 있는 MIT 6.006 Introduction to Algorithms (Fall 2011) 강의 내용을 바탕으로 정리한 것입니당 :D ------- * ------- * ------- * ------- * 그래프 탐색 (Graph search) 그래프 G = (V, E) V = 정점(vertices, == 노드 nodes) 의 집합, E = 간선(edges) 의 집합 e = {v, w} (un-ordered pairs of vetices) 또는 (v, w) (ordered pairs) ∈ E 그래프 탐색 (graph search) 은 이러한 그래프 구조를 탐험(explore) 하는 것! 응용 예시 웹 크롤링 (동적으로 새로운 페이지가 생성되.. 2021. 3. 14. 이전 1 다음