목록C++/알고리즘 (16)
나만의 작은 도서관
[알고리즘] 두 포인터(Two-pointer)
두 포인터(Two-pointer)란?두 포인터(Two Pointer)는 두 개의 포인터를 사용하여 문제를 해결하는 알고리즘 기법이다. 두 포인터는 일반적으로 정렬된 배열에서 사용되며, 특정 조건을 만족하는 구간이나 조합을 찾는 문제에서 활용한다. 문제 유형으로는 부분합 찾기나 두 수의 합 등이 있다. 주 목표는 최적화두 포인터는 다른 알고리즘이랑 느낌이 살짝 다르다. 다른 알고리즘들은 특정 문제를 해결하기 위해 사용한다면, 두 포인터는 해결 가능한 문제의 시간복잡도를 줄이기 위해 사용한다. 즉, 최적화를 위한 알고리즘이며 일반적으로 O(N^2) -> O(N)으로 줄이는 것이 목표다. 동작방식두 포인터를 사용하는 상황은 다양하다. 아래 예제는 합이 9가 되는 구간을 찾는 경우이다. 1. 초기화 시작과 끝..
[알고리즘] 위상 정렬(Topological Sorting)
위상 정렬(Topological Sorting)이란? 위상 정렬(Topological Sorting)은 방향 그래프(Directed Graph)의 모든 정점을 간선의 방향을 거스르지 않도록 일렬로 정렬하는 방법이다. 방향성 있는 비순환 그래프(DAG, Directed Acyclic Graph)에서 사용할 수 있으며, 정렬 기준은 선행 정점이 후행 정점보다 먼저 나오는 순서를 따른다. 예를 들어, A 작업을 먼저 끝낸 후에 B 작업을 수행해야 하는 경우, A가 B보다 먼저 나오도록 정렬한다. 위상 정렬은 부분 순서들을 만족하는 전체 순서를 구하는 문제에서 활용되며, 문제 유형은 과목 수강 순서나 프로젝트 작업 순서 등이 있다. 동작방식(아래 동작방식의 예는 BFS를 기반으로 설명한다. DFS로 구현하는 방..
[알고리즘] 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): 현..