목록2024/10 (13)
나만의 작은 도서관
[알고리즘] CCW(Counter ClockWise)와 선분 교차 판정
CCW(Counter ClockWise)란? CCW(Counter ClockWise) 알고리즘은 평면 위에 놓인 세 점의 방향을 계산하여 이 점들이 시계 방향인지, 반시계 방향인지, 혹은 일직선 상에 있는지 확인하는 데 사용한다. 예를 들어 세 점 A, B, C가 주어졌을 때 구하고자 하는 방향이 A -> B -> C라면, 벡터 AB와 벡터 BC을 이용해 방향을 계산하는 방식이다. CCW 알고리즘은 기하학 알고리즘(geometry algorithm)으로 분류되며 볼록 껍질(Convex Hull), 선분 교차 판정과 같은 문제에서 활용할 수 있다. CCW 공식과 방향 판별법세 점 A(x1, y1), B(x2, y2), C(x3, y3)가 주어졌을 때, A -> B -> C의 방향은 다음과 같은 식을 사용하..
[알고리즘] Union-Find 알고리즘
Union-Find 알고리즘란?Union-Find 알고리즘은 서로소 집합(Disjoint Set) 자료구조를 구현하는 알고리즘으로, 서로소 집합들을 효과적으로 관리하기 위해 사용한다. Union-Find 알고리즘은 이름에서도 알 수 있듯 Union과 Find연산을 통해 작동하며, Union은 서로 다른 집합을 하나로 합치는 합연산을, Find는 선택한 원소가 속해있는 집합을 찾는 연산을 한다. 서로소 집합(Disjoint Set)이란?서로소 집합(Disjoint Set, 분리 집합이라고도 부름)이란 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합들을 말한다. 서로소 집합은 특히 동적 연결성을 다루는 문제에 유용하며, 주로 네트워크 연결이나 그래프의 사이클 검출과 같은 문제에 활용할 수 있다. ..
[알고리즘] 프림 알고리즘(Prim Algorithm), 크루스칼 알고리즘(Kruskal Algorithm)
프림 알고리즘(Prim Algorithm)과 크루스칼 알고리즘이란(Kruskal Algorithm)?프림 알고리즘과 크루스칼 알고리즘은 그래프에서 최소신장트리(Minimum Spanning Tree, 줄여서 MST라고 부름)를 찾는 알고리즘이다. 이 두 알고리즘 모두 "부분적으로 최적인 고려사항에 따라 간선을 선택"하기 때문에 그리디 알고리즘(Greedy Algorithm)으로 분류된다. 최소신장트리란?최소신장트리는 그래프의 모든 정점을 포함하는 트리들 중 가중치의 합이 최소인 트리를 말한다. 주로 가장 적은 비용으로 모든 지점을 연결하고 싶을 때 사용한다. 동작방식(프림 알고리즘) 1. 초기화시작점을 선택한다. 시작점은 어떤 정점을 선택해도 상관없지만, 아래 예시에서는 편의상 1번 정점을 선택한다. 2..
[알고리즘] A* 알고리즘(A star algorithm)
A* 알고리즘(A star algorithm)이란?A* 알고리즘은 가중치가 있는 그래프(weighted graph)에서 시작점과 도착점이 주어졌을 때 최단 거리를 구하는 휴리스틱 기반의 알고리즘이다. 다익스트라 알고리즘에서 변형된 알고리즘이며, 동작 방식 또한 유사하지만 특정 지점까지의 추정 거리를 고려한다는 점에서 다르다. A* 알고리즘은 다익스트라 알고리즘보다 빠르게 두 정점 간의 최단 경로를 구해낸다는 점 때문에 게임 내에서 길 찾기 기능으로 사용되며, 대표적으로 스타크래프트가 A* 알고리즘을 사용하였다. (특정 게임에서는 A* 알고리즘마저도 느려 A* 알고리즘보다 빠른 JSP 알고리즘을 사용하기도 한다.) A* 알고리즘의 구성 요소g(n): 시작점에서 현재 정점까지의 실제 경로 비용.h(n): 현..
[알고리즘] 벨만-포드 알고리즘(Bellman-Ford Algorithm)
벨만-포드 알고리즘(Bellman-Ford Algorithm)이란?벨만-포드 알고리즘은 가중치가 있는 그래프(weighted graph)에서 시작점을 기준으로 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘과 동일하게 최단 거리를 찾아주는 알고리즘이지만, 벨만-포드 알고리즘은 다익스트라 알고리즘과는 다르게 음의 가중치가 있는 그래프에서도 사용가능하며, 음수 사이클 또한 찾아낼 수 있다는 점이 다르다. 하지만 모든 간선(E)을 확인하는 작업을 V-1번 반복하기 때문에 시간복잡도가 O(VE)로, O(ElogV)인 다익스트라 알고리즘보다 느리다는 단점이 있다. 알고리즘 분류는 매 순간 모든 간선을 완화하면서 최적해를 점진적으로 찾아가는 방식이기 때문에 다이나믹 프로그래밍(dyn..
[알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm)
다익스트라 알고리즘(Dijkstra Algorithm)이란?다익스트라 알고리즘은 가중치가 있는 그래프(weighted graph)중 음수 가중치가 없는 그래프에서 시작점을 기준으로 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 최단 거리를 구하는 매 단계에서 가장 짧은 경로만 선택하기 때문에 그리디 알고리즘(greedy algorithm)으로 분류된다. 동작방식 1. 초기화 시작점에서 각 정점으로 가는 최단 거리를 저장할 배열을 생성한다. 배열은 시작점과의 거리를 0으로, 다른 정점들과의 거리는 무한대(INF)로 초기화한다. (편의상 시작점은 v1로 설정하였다.)아래 그림에서 Select, Add, Adjacent, Visited는 다음과 같은 의미를 가진다.Selec..