🖥 Computer Science/알고리즘

🧐 DAG : Directed Acyclic Graph DAG는 Cycle이 없는 방향 그래프를 의미합니다. 방향 그래프 $G$ 에서 Cycle이 없다는 것은, $G$ 에 대한 DFS Tree가 Back Edge를 가지고 있지 않다는 말과 동일합니다. 👉 증명 더보기 🧐 위상 정렬(Topological Sort) 위상 정렬은 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘입니다. 위상 정렬은 오직 DAG 에서만 수행될 수 있습니다. 위상 정렬에서의 정렬 기준은 다음과 같습니다. 간선 $($ $u$, $v$ $)$ 가 존재할 경우(즉 $u$ 에서 $v$ 로의 edge가 존재할 경우), 정점 $u$ 는, 정점 $v$ 보다 순서가 앞입니다. 예를 들어 위 그래프에서..

🧐 방향성이 있는 그래프에서의 DFS 방향성이 있는 그래프(Directed Graph) 에서도 Undirected Graph와 똑같은 방법으로 DFS가 가능합니다. 그러나 Directed Graph에서는 간선에 방향성이 있으므로, undirected graph와 달리 DFS Tree에서 Tree Edge가 아닌 부분들을 더 세분화 할 수 있습니다. Directed Graph에서 DFS Tree에 등장하는 Edge는 다음과 같습니다. Tree Edge : Undirected Graph와 동일합니다. DFS Tree 상에 표시되는 간선을 의미합니다. Back Edge $($ $u$, $v$ $)$: $u$ 는 $v$ 의 descendant Forward Edge $($ $u$, $v$ $)$ : $u$ 는 ..

🧐 Biconnected Components 그래프 $G$ 가 biconnected 하다는 것은 다음을 의미합니다. $G$ 는 connected graph 이며, articulation point를 가지고 있지 않다. biconnected를 통한 biconnected component의 정의는 다음과 같습니다. Biconnected component $G’$ of $G$ : $G$ 의 maximal biconnected subgraph 즉 $G$ 의 biconnected component로 $G$ 의 간선들을 partitioning 할 수 있으며, 서로 다른 biconnected component는 최대 한개의 정점(articulation vertex)를 공유합니다. 따라서 위의 그림처럼 Articula..

🧐 Connected Components 그래프 $G$ 의 Connected Component 인 $G'$ 은 다음과 같이 정의됩니다. Connected Component $G'$ of $G$ : Maximal connected subgraph of $G$ ✔️ Maximum과 Maximal의 차이 Maximum : 최대를 의미합니다. Maximal : 더이상 추가할 수 없는 상태를 의미합니다. 즉 Connected Component의 정의는 다음과 같이 해석 가능합니다. $G'$ 에서 추가적으로 $G$ 에 존재하는 아무 정점 하나를 추가하는 순간 disconnected가 되며, $G'$ 은 가능한 모든 간선을 포함하고 있어야 합니다. 즉 induced subgraph를 의미합니다. 이제 Connecte..

🧐 DFS (Depth-First Search) - 깊이우선탐색 이전 글에서 살펴본 explore procedure를 이용하여 그래프 상의 모든 정점을 한번씩 방문하는 방법인 DFS 알고리즘에 대해 알아보도록 하겠습니다. 네 알아봤습니다 :) 코드로 구현 더보기 다음 그래프에 대한 dfs를 코드로 구현해 보도록 하겠습니다. /** * Created by ShinD on 2022/09/22. */ fun main() { val graph = GraphMaker().make() GraphExplorer().dfs(graph) GraphMaker.vertexSet().forEach { println("END [${it.value}], [ ${it.preOrder}, ${it.postOrder} ]") } } ..

🧐 그래프 (Graph) 그래프는 정점(vertex)들과 간선(edge)들로 이루어진 구조로써, 기호로는 다음과 같이 표현합니다. $$G = (V(G), E(G))$$ $V$ 는 정점을, $E$ 는 간선을 의미합니다. 🧐 Simple Graph Self loop 또는 Multiple Edge를 가지지 않는 그래프를 Simple Graph라고 합니다. 그림으로는 아래와 같습니다. 앞으로 등장하는 모든 그래프는, 특별한 설명이 없는 이상 Simple Graph라고 가정하겠습니다. 🧐 Directed Graph와 Undirected Graph 그래프에 속한 $E$ (간선)의 각 원소들이 ordered pair 즉 방향성이 있는 경우, 해당 그래프를 방향 그래프(Directed Graph)라고 합니다. 반대로 ..

🧐 Selection 알고리즘 크기가 $n$ 인 배열 $A$ 가 주어졌을 때, $A$ 에서 $k$ 번째로 작은 요소를 찾는 알고리즘에 대해 알아보도록 하겠습니다. 가장 간단한 방법으로는 $A$ 를 정렬하여 $k$ 번째 수를 가지고 오는 방법이 있습니다. 배열을 정렬하는 알고리즘들 중에서 worst-case가 $O(n \; logn)$ 인 알고리즘(merge sort, heap sort, 등등)을 사용한다면, 이후 $k$ 번째 요소에 접근하는 것은 $O(1)$ 의 시간이 소요되므로 총 시간 복잡도는 $O(n \; log n)$ 입니다. 두번째 방법은 Devide and Conquer 알고리즘 중 하나인 Quick Select 알고리즘을 사용하는 것입니다. 🧐 Quick Select Quick Select는..

🧐 분할 정복이 뭐예요? 일반적으로 어떠한 문제를 더 작은 문제로 분할하고, 분할한 문제들을 해결한 후 조합하여 큰 문제를 해결하는 알고리즘을 의미합니다. 과정을 나열하자면 다음과 같습니다. 1. 주어진 문제를 더 작은 문제(Subproblem)으로 나눕니다. 이때 작아진 문제는 본질적으로 큰 문제와 동일하나 단지 입력(input)의 크기만 작아진 문제를 의미합니다. 2. 1번 과정에서 나눈 Subproblem 들을 재귀적으로(더 작은 문제로 나누며) 해결합니다. 3. 2번에서 해결한 Subproblem들의 답을 적절하게 조합하여, 기존 큰 문제의 답을 도출합니다. 1번의 과정은 Divide 2, 3번의 과정은 Conquer 과정에 해당합니다. 🧐 분할 정복의 일반적인 패턴 분할 정복은 일반적으로 다음과..