이번 포스팅에서는 Cut Vertex란 무엇인지 그에 대한 정의와, 판별하는 방법에 대해 알아보겠습니다. 그에 더불어 dfs graph, back edge 에 대한 개념도 살펴봅시다. Definition of Cut Vertex If node s is Cut Vertex, Removing a node s makes Graph G Disconnected. Exists x and y s.t., all paths from x to y goes through s. Cut vertex 정의 1. 연결 그래프 G에서 노드 S를 없앴더니 비연결 그래프가 되었을때, S를 Cut vertex(단절점)라 부른다. 없앴을 때 Disconnected Graph 를 만드는 S를 Cut Vertex 라고 부른다. 2. 노드 X에..

이번 포스팅에서는 Graph traversal(그래프 순회)와, Connected Component 대해 알아보자. Graph Traversal 그래프 순회 정의 모든 Node, Edge를 한번씩 지정된 순서로 방문하는 것이다. 순회를 거친 후에, 그래프에서 뽑아낸 자료구조가 만들어진다. (ex. 트리구조) 트리에서 문제를 푸는 것이 그래프에서 푸는 것보다 쉽다. 그래프 순회의 종류 - Depth First Search (깊이 우선 탐색) - Breadth First Search (너비 우선 탐색) Any-order Traversal Start at a Node S (put S into BOX) While BOX is not Empty Take one Node from BOX If Node not Mar..

우선 approxmiate median 에 대해 알아보기 전에, Quick Sort에 대해 간단히 짚어보자. Quick Sort 저번 포스팅에서 Quick Sort의 평균 시간복잡도가 왜 O(nlogn) 인지 증명해보았다. 시간복잡도 Average : O(nlogn) Worst : O(n^2) 피벗이 중간에 위치해 있다 -> Best Case 피벗이 한쪽 방향으로 계속 쏠려있다. -> Worst Case 정말 운이 안 좋게도 재귀적으로 따라 들어갈 때마다 pivot 이 한쪽 끝이라면 시간복잡도가 O(n^2) 이다. Quick Sort를 쓰는 의미가 없음. 시간복잡도 (최악의 경우) T(n) = n + T(n-1) T(n) = O(n^2) 이렇게 pivot의 위치에 따라 성능에 크나큰 차이가 발생한다. 따..

MergeSort 알고리즘의 시간 복잡도는 O(NlogN) 이다. MergeSort는 매우 준수한 정렬 알고리즘이지만 추가적인 배열 하나가 더 필요하기 때문에 memory allocation이 일어난다. 그리고 새로운 메모리를 할당하는 과정은 꽤 비싸다. 이번 포스팅에서는 퀵정렬에 대해 알아보고, 시간복잡도에 대한 증명도 하고자 한다. Quick Sort 대표적인 divide & conquer 알고리즘. 평균 시간복잡도: O(NlogN) 인 아주 훌륭한 알고리즘이다. 퀵 정렬은 조금 특이한 특징을 가지고 있는데, 바로 피벗(Pivot)을 사용한다는 점이다. 대략적인 소스코드는 다음과 같다. int qsort(int a[], int n){ // pivot int p = a[0]; int i = 1; int..

앞서 최단거리 알고리즘으로 Prim, Kruskal 을 다뤄보았다. 이번 포스팅에서 다룰 Shortest Path 알고리즘은 다익스트라(dijkstra)이다. 다익스트라 알고리즘이 왜 정확한지 정확성 증명을 해보고, 코드로 구현을 해보겠다. Dijkstra Algorithm 정확성 증명 Source 노드에서 시작 각 노드에 적힌 숫자는 source 노드와의 최단거리를 나타낸다. 정답을 찾아가면서 이 노드들의 숫자를 update 하면 된다. 다익스트라의 특징 모든 노드에서 시작점까지의 최단 거리를 구할 수 있다. 단순히 거리만 구하는 것이 아니라, 지나온 경로도 알 수 있다. (백 트래킹) 진행 방법 위처럼 노드들이 있고, 노드마다 적힌 숫자는 시작 노드와의 최단거리를 나타낸다. 빨간 영역은 알고리즘에 의..

Shortest Path 를 찾는 알고리즘으로 Prim 알고리즘을 살펴보았다. prim 은 그리디 알고리즘으로, MST(최소 신장 트리)를 만들기 위해 힙, 즉 우선순위큐를 사용했다. 두 정점 사이의 edge 거리가 작은 것 우선순위가 높도록 정했다. 이번 포스팅에서 다룰 Kruskal 알고리즘도 Shortest path를 찾는 문제다. 연결 그래프가 주어지고 MST를 구하면 되는 문제이다. Prim 알고리즘과 목적이 같지만, 구현 방법에 약간의 차이가 있다. Prim 알고리즘 포스팅: https://matt1235.tistory.com/51 문제) 다음과 같은 연결그래프가 있다. 모든 정점을 연결하는 Minimum Spanning Tree를 구하라. Prim 알고리즘은 T라는 해집합을 점차 늘려나가는 ..