CCW(Counter Clock-Wise)
CCW 알고리즘은 한 선과 한 점의 위치 관계를 구할 때 사용하는 알고리즘입니다. 한 선분 AB와 점 C가 일직선 상에 있는지, 반시계 방향에 있는지, 시계방향에 있는지를 알려줍니다. 이 알고리즘은 기하 문제를 푸는데 사용이 되며…
2024-06-042분
최근 글
이분 매칭 (Bipartite Matching)
두 그룹으로 구분된 정점과, 서로 다른 그룹의 정점을 연결하는 간선들로 이루어진 그래프를 이분 그래프(Bipartite Graph)라고 합니다. 그룹 A에 속하는 정점 Ai와 그룹 B에 속하는 정점 Bj를 연결하는 간선 (Ai,…
2024-06-033분
KMP (Knuth–Morris–Pratt)
KMP 알고리즘은 문자열 탐색 알고리즘입니다. KMP는 Knuth–Morris–Pratt의 줄임말로 KMP 알고리즘을 제안한 Donald Knuth, Vaughan Pratt 그리고 James H. Morris의 이름을 따서 이름…
2024-05-314분
Floyd-Warshall (플로이드-워샬 알고리즘)
플로이드-워샬 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 정점 사이의 최단 거리를 구하는 알고리즘으로 O(V^3)의 시간 복잡도를 가집니다. 하나의 정점으로부터 다른 모든 정점사이의 최단 거리를 구하는…
2024-05-302분
벨만-포드 알고리즘
벨만 포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 어느 한 정점에서 나머지 정점까지 거리를 구하는 알고리즘입니다. 하지만 다익스트라와는 다르게 음수 가중치를 갖는 그래프에서도 동작을 하며, 음수 사이클을 찾아내는 기능도 가지고…
2024-05-293분
다익스트라(Dijkstra) 알고리즘
다익스트라 알고리즘은 그래프의 한 노드에서 연결된 다른 노드들로 가는 최단 거리를 구하는 알고리즘입니다. 만약 모든 노드 쌍간의 최단 거리를 구하고 싶다면 N개의 각 정점에 대해 해당 정점을 출발점으로 하는 다익스트라 알고리즘을…
2024-05-284분
서로소 집합(Disjoint-Set)
서로소 집합(Disjoint-Set)은 집합, 혹은 그룹을 관리하는 효율적인 알고리즘입니다. 각각의 그룹을 트리 구조로 관리하는 이 알고리즘은 크게 두 가지의 연산을 가집니다. find(x): x번 노드의 최고 조상(루트)을 찾는…
2024-05-254분
Binary Indexed Tree
Binary Indexed Tree(또는 fenwick tree, 이하 BIT)는 Segment Tree와 비슷하게 구간에 대한 정보를 저장할 수 있는 자료구조입니다. 기본적으로 아래의 그림과 같은 1-based 구조를 가지며,…
2024-05-242분
세그먼트 트리(Segment Tree)
세그먼트 트리(Segment Tree)는 구간에 대한 정보를 빠르게 구해낼 수 있으며 완전 이진트리 형식의 구조를 가지는 자료구조입니다. 구간 최소값을 구하는 세그먼트 트리 예시 구간의 최솟값을 구하는 세그먼트 트리는 먼저 구하고자…
2024-05-234분
최소 신장 트리(Minimum Spanning Tree)
최소 신장트리란 최소 신장 트리(Minimum Spanning Tree)는 가중치가 있는 무방향 그래프의 모든 노드를 포함하면서 사이클이 없고 가중치의 합이 최소가 되는 트리입니다. 연결그래프가 주어질 때, MST를 구하는…
2024-05-214분