hisLibrary

오늘은 지난번에 공부했던 최단 경로에서 Single vertex가 아닌 All Pairs를 기준으로 공부하려 한다. 또 이를 그리디 알고리즘이라고 한다. 1. All-Pairs Shortest Paths 즉 각노드에 대해서 전부 알고리즘을 수행하는 것이다.따라서 각각 빅오O 에 대하여 V를 곱해주어야 한다. 자 그럼 한번 자세히보자노드의 개수 V는 n개일 때 인접 행렬은 nxn 행렬이 된다. 그리고 각각 노드간 간선은 가중치가 있다.이를 다이나믹 프로그래밍 방법으로 해결하는데 여기서 우리가 전에 증명한 최단 경로의 모든 서브 경로는 최단 경로이다를 이용한다. Let p: a shortest path p from vertex i to j that contains at most m edges 라고 할 때i ..

알고리즘 2018. 11. 18. 15:32

지난번 공부했던 Minimum Spanning Tree는 최소비용에 초점을 맞춰 트리를 구성하는 것이었다.이번에는 최단경로를 구한후 이에 대한 가중치를 구하는 최단경로 알고리즘을 공부해보자 1. Single-Source Shortest Path 가중치가 있는 방향 그래프가 있다. 여기서 시작점 S에서 다른 노드 V 까지의 최소가중치 경로 즉 최단경로를 찾아야 한다. 이후 찾은 최단경로의 가중치는 간선들의 총합이 된다. 여기서 optimal substructure라는 중요 속성을 가지게 되는데 이는 최당경로 안에 있는 서브패스 역시 최단경로가 된다는 것이다. 잠깐 이를 증명해보이고 가겠다 명제 A : 최단경로(P)의 어떤(모든) 서브패스는 최단경로이다 ~A : 최단경로(P)의 몇몇 서브패스는 최단경로가 아..

알고리즘 2018. 11. 18. 12:40

오늘은 Spanning Tree가 무엇인지 알아보고 또 여기에서 파생된 2개의 알고리즘에 대해 공부해보자 1. Minimum Spanning Tree MST는 모든 노드들을 연결(connected)하는데 있어 최소비용(minimum cost)으로 연결하는 트리구조를 말한다. 식으로 표현하면 이렇게 된다. 즉 간선들의 합이 곹 트리의 cost가 되는것이다. 따라서 MST는 몇가지 속성들을 가질 수 있다. 1. V -1 개의 Edge를 가지며2. no cycle3. 고유하지 않을 수있다. ( 최소비용인 다른 경로가 존재할 수 있다는점) 그럼이제 MST가 어떻게 구성되어지는지를 보기전에 사전 지식을 먼저 알고 가자 먼저 S는 V(노드)에 부분집합 A는 E(간선)의 부분 집합이라고 하자여기서 cut( S, V-..

알고리즘 2018. 11. 11. 17:31

지난번에는 너비 우선 탐색에 대해서 공부하였다. 이번에는 이와 비슷하면서도 다른 깊이 우선 탐색 알고리즘에 대해서 알아보자. 1. 깊이 우선 탐색 Search as deep as possible first 가능한한 깊게 찾아라라는 의미로 깊이 우선 탐색의 핵심을 의미한다고 볼 수 있다. 가장 최근에 발견되어진 꼭지점 V에서 시작하는 간선을 찾으며 끝까지 찾았을 때 이후 다시 뒤로 돌아가며 남은 꼭지점이 있는지 찾게 된다. 이후 있다면 다시 그 꼭지점으로부터 시작되는 모든 간선을 찾게 된다. 이와 같은 과정을 모든 꼭지점을 찾을 때 까지 계속 되어진다. 잘 이해가 안되겠지만 의사코를 한번 살펴보면 이해가 될것이다. 사전에 먼저 정의를 하자 자 이와 같다고 할때 1 ~ 4 먼저 각 노드에 대해서 (v개의 노..

알고리즘 2018. 11. 11. 16:54

오늘은 그래프 탐색에 대해 공부해보자 1. Graph-Searching Algorithms 그래프 탐색은 시스템적으로 그래프의 간선들이 꼭지점들을 찾아가는 것이다. 그래프의 구조를 사용하는데 너비 우선 탐색깊이 우선 탐색이 2가지가 있다. 먼저 너비 우선 탐색에 대해 알아보자 2. Breadth-First Search 탐색할 그래프 G는 방향 무방향 둘다 상관 없으며 출발점 꼭지점은 꼭지점 집합에 속한다. d[v]는 s - > v 로 가는 가장 짧은 경로를 의미한다.d[v] = 무한대 는 아직 s가 v로 도달하지 못한 것을 의미한다.ㅠ[v] = u 는 s가 v로 가는 가장 짧은 경로중 마지막 간선을 의미한다. 즉 u는 v의 이전 노드이다. BFS를 그림으로서 한번 보기전에 간단한 색깔에 대해서 정의하고 ..

알고리즘 2018. 11. 4. 18:55

오늘은 그래프에 대해서 한번 알아봅시다. 1. Graph 그래프는 꼭지점들의 집합과 과 간선들의 집합으로 이루어진 집합입니다 그래프의 종류로는 무방향 그래프, 방향 그래프 ,가중치가 있는 그래프, sparse 그래프, dense그래프가 있습니다. 참고로 sparse 그래프는 간선의 개수 보다 노드의 개수가 더 큰 그래프이며 dens.e 그래프는 그것의 반대입니다. 그리고 간선의 개수의 빅오는 V * V 임을 알 수 있습니다. ( 셀프루프 포함 , 배열로 표현시 꽉찬 배열) 인접 관계에서 그래프가 무방향그래프인 경우에는 인접관계가 대칭되지만 방향 그래프인 경우에는 반드시 대칭되지지는 않는다. 또 그래프에서 임의의 두 노드를 골랐을 때 이 두노드가 연결 되어있다면 그래프가 연결되어 있다고 한다. 그리고 방향..

알고리즘 2018. 11. 4. 16:42

이번에는 지난번에 본 이진 트리를 이어서 이진 탐색 트리를 공부해 보겠습니다. 1. 트리와 이진 트리 트리는 사이클이 없는 그래프를 말하며 트리와 이진트리의 속성은 그림과 같습니다. 2. 트리 검색 트리 검색을 공부하는데 있어 공부할 내용과 미리 알아야 할 내용들이 있습니다. 트리에 있어 각 오퍼레이션과 앞서 본 트리들의 빅오 입니다. 그리고 트리의 타입을 보면 트리의 타입별 이러한 속성을 지니고 있다는것을 알수 있습니다 그리고 각각 Degenerate는 빅오 n Balanced 는 빅오 lgnComplete 는 빅오 lgn 인것을 알수 있습니다. 이진 탐색 트리의 속성을 보면 이러한 속성을 가지고 있습니다참고로 X와 Y가 같은 경우는 어느쪽에 오든 프로그램의 특성이므로 상관 없습니다. 3. 노드의 진행..

알고리즘 2018. 10. 28. 10:51

이번글은 요소값을 비교하지 않아도 정렬할 수 있는 알고리즘인 카운팅 정렬 과 레딕스 정렬에 대해 공부해보도록 하겠습니다. 1. Count Sort 카운팅 정렬은 요소간 비교를 하지 않습니다. 하지만 정렬 되어지는 숫자들에 대한 가정에 의존합니다. 그 가정은 천천히 알아봅시다. 각각의 입력 요소 x 에 대해서 x 보다 같거나 작은 요소의 개수를 결정한다는 생각에서 시작 됩니다. 이를 배열 A,B,C로 나타내면 A는 정렬하기 위한 입력값들을 넣게되는 배열B는 정렬되어진 값들을 넣게되는 배열C는 0부터 K까지 중 한 인덱스 i와 동일하거나 작은 값의 개수를 넣게 됩니다. 이를 그림으로 보면 a) A의 각 값의 총 개수에 대응하여 C의 인덱스에 넣어준다. ( 0은 2개 1은 0개 ...)b) C에 모든 요소가 ..

알고리즘 2018. 10. 11. 21:55