A collection of 92 articles on programming, technology and life.
Concept 그래프 간선에 유량과 비용이 있을 때 최소 비용으로 최대 유량을 구하는 알고리즘이다. [[Maximum Flow (Edmonds-Karp Argorithm)]]에서 간선의 비용 정보가 추가된 내용이다. SPFA(Shortest Path Faster Algorithm) 알고리즘을 사용한다. SPFA(Shortest Path Faster Algorithm) 원리 Maximum Flow에서 사용하는 Edmonds-Karp Argorithm와 Bellman-Ford Algorithm(like
Concept 방향 그래프($G$)에서의 시작점($source$), 종점($sink)$까지 Edge 용량(capacity)을 고려해 최대 유량을 구하는 문제이다. 이를 구하기 위한 알고리즘을 에드몬드-카프(Edmonds-Karp Argorithm) 알고리즘이라고 한다. 노드 $v,u$에서 '흐를 수 있는 유량'을 capacity라고 하고 $c(v,u)$라고 표현하다. 실제 노드 $v,u$에서 '흐르는 유량'을 flow라고 하고 $f(v,u)$라고 표현한다. Capacity와 Flow를 합쳐서 F/C
Concept 2차원 좌표 평면에 위에 존재하는 여러 점들 중 일부를 이용하여 모든 점을 포함하는 볼록 다각형을 말한다. 볼록 다각형이란, 경계의 두 점을 잇는 어떤 선분도 다각형 외부로 나가지 않는 단순 다각형 이다. Convex Hull을 구하기 위해선 모든 점들을 탐색하여 해당 점이 다격형의 선분으로 포함될지 안될지를 판단해야 한다. Convex Hull의 대표적인 알고리즘은 Graham's Scan이다. Graham's Scan 원리 Graham's Scan의 작동 방
Concept 노드 사이의 최단 경로를 탐색하는 이다. 특정 노드에서 연결되어 있는 모든 정점간의 최단 경로를 구할 수 있다. 모든 정점에서 다른 모든 정점의 최단 거리를 구하는 과 다르게 하나의 정점에서 다른 모든 정점의 최단 거리를 구하는 이다. 음의 간선이 있는 경우에는 을 사용할 수 없다. (이 경우 `벨만-포드(Bellman-Fo
Concept 노드 탐색 방법 중 하나로 임의의 노드에서 다음 Branch로 넘어가기 전에 해당 Branch를 완벽하게 탐색하는 방법을 말한다. 하나의 Branch씩 탐색하기 때문에 보통 재귀를 이용해 구현한다. BFS와 마찬가지로 Visited Array로 중복 탐색을 방지한다. 노드의 개수 $n$, 간선의 개수 $e$이라 할 때 시간 복잡도는 $O(n+e)$ DFS 원리 ![BASE TREE](<https://dqygovtpvlsoxwnnhepz.supabase.co/storage/v1/objec