지난 학기들의 기록/알고리즘28 [강의노트] 최소신장트리 - 1 최소신장트리 - 1 가중그래프 간선에 무게를 가지는 그래프. 이미 배운 내용이라 익숙하다. 아래 가중그래프 예시를 보면, 각 지역(정점)을 잇는 간선의 무게는 여행거리(km)를 나타낸다. 신장트리 신장 부그래프를 다시 떠올려보면 , 모든 정점 + 부분간선의 그래프라고 외웠었다. 그 중에서 트리인 그래프를 우리는 신장트리라고 부른다. 다시 말하면, 신장트리(Spanning Tree)는 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 그림은 그래프 G의 노드 A,B,C를 모두 포함하지만 순환이 존재하지않는 그래프 G의 신장트리 3개를 보여주고 있다. 그럼 최소신장트리는 무엇일까? 최소신장트리는 신장트리 중에서 총 간선 무게의 합이 최소인 신장트리를 의미한다. 최소신장.. 2021. 11. 26. [강의노트] 방향그래프 - 2 방향 그래프 - 2 https://man-25-1.tistory.com/187 [강의노트] 방향 그래프 - 1 방향 그래프 - 1 지금까지 무방향 그래프의 구현과 수정, 그리고 순회알고리즘 DFS와 BFS에 대해서 다루어보았다. 이번에 배울 것은 간선에 방향성이 존재하는 방향그래프이다. 방향그래프 방향그 man-25-1.tistory.com 방향 그래프의 여러 개념들에 대해 배워보았고 이제는 구현방법에 대해 알아볼 차례이다. 동적프로그래밍 그전에 지난 포스팅에서 다루었던 동적 프로그래밍의 개념에 대해 한번 짚고 가면 동적프로그래밍은 언뜻 보기에 많은 시간이 소요될 것 같은 문제에 주로 적용된다. 적용 조건은 1. 부문제들이 단순해야한다 - 부문제들이 j, k, l, m 과 같은 몇 개의 변수로 정의 되어.. 2021. 11. 24. [강의노트] 방향그래프 - 1 방향 그래프 - 1 지금까지 무방향 그래프의 구현과 수정, 그리고 순회알고리즘 DFS와 BFS에 대해서 다루어보았다. 이번에 배울 것은 간선에 방향성이 존재하는 방향그래프이다. 방향그래프 방향그래프란 모든 간선이 방향간선인 그래프이다. 무방향 그래프에서 방향성만 추가된것이므로 개념은 어렵지않다.. 방향그래프에서 단순하다는 개념은 간선의 수를 m , 정점의 수를 n이라 할 때 m k -> j 의 경로를 구할 수 있게 되는 것이다. 방금 설명한 알고리즘에 대한 수도코드이다. 왼쪽의 설명을 참조하면 어렵지않게 이해할 수 있다. G_k-1 그래프의 정점 i,k 에 대한 경로와 k,j에 대한 경로를 확인하고, 만약 G_k에 vi,vj 경로가 없으면 삽입한다. 아까 설명한 1부터 k-1 까지 번호 매겨진 정점들만 .. 2021. 11. 17. [강의노트] 그래프 순회 -2 (BFS) 그래푸 순회 - 2(BFS) 지난 포스트에서는 DFS에 다루어보았고, 이번에 배울것은 BFS 너비우선탐색이다. 마찬가지로 그래프 순회 기법이다. BFS - 너비우선탐색 너비우선탐색에서 가장 핵심적인 단어를 꼽자면 level 이라고 생각한다. 이 얘기는 뒤에 몇번 더 언급하겠다. BFS는 트리의 level 별로 순회를 한다. 즉 트리에서 루트노드를 기준으로 자식노드로 계속 내려가는 것을 깊이우선탐색이라고 한다면, 기준노드에서 형제노드를 우선적으로 탐색하는 것이 너비우선탐색이다. DFS와는 탐색의 방향성 측면에서 어떻게 보면 반대의 개념이라고도 생각할 수 있다. BFS를 확장해서 해결 가능한 문제를 살펴보자. 두개의 주어진 정점 사이의 최소 간선을 사용하는 경로를 찾을 수 있다고 한다. 그래프 내 싸이클을 .. 2021. 11. 17. 이전 1 2 3 4 ··· 7 다음
