Programming/Algorithm (17) 썸네일형 리스트형 네트워크 유량(Network Flow) 1. 개념 그래프의 간선에 거리, 시간이나 가중치, 즉 cost 대신에 용량(capacity)이라는 개념이 추가된다. 이제 두 정점 u, v를 잇는 간선 (u, v)가 있을 때, 정점 u에서 v 방향으로 간선의 용량 이하만큼의 유량(flow)을 흘려보낼 수 있다. 또한, 그래프에 서로 다른 두 정점인 소스(source), 싱크(sink) 정점이 정해지고 소스 정점에서 유량을 발생시켜서 간선들을 통해 싱크 정점에 도달시키는 것이 목표이다. 유량을 발생시킬 수 있는 것은 소스 정점 뿐이고, 그 외의 정점들은 자신이 받은 유량만큼만 다시 흘려보낼 수가 있다. 2. 특징 - 각 간선에 흐르는 유량은 그 간선의 용량을 넘어서는 안 된다. - 소스와 싱크를 제외한 정점에서는 들어오는 유량 총합과 나가는 유량 총합이.. CCW(CounterClockWise) 알고리즘 1. 개념 CCW는 외적을 이용해서 점 3개의 방향성을 나타내는 알고리즘이다. 즉, 세 점으로 이루어진 삼각형의 면적을 구하는 방법을 이용해서 방향성을 구한다. 우선 점 3개로 나타날 수 있는 경우는 총 3가지이다. 시계 방향, 일직선 방향, 반시계 방향 총 3가지이다. 2. 구현 어떠한 경우인지 알기 위해서 다음과 같은 식을 세운다. 여기서 S의 부호에 따라 경우를 3가지로 파악한다. 1) S > 0 : 반시계 방향 2) S = 0 : 일직선 3) S < 0 : 시계 방향 1234567891011int ccw(int x1, int y1, int x2, int y2, int x3, int y3) { int temp = x1*y2+x2*y3+x3*y1; temp = temp - y1*x2-y2*x3-y3*.. 배낭 알고리즘(Knapsack Algorithm) 1. 개념 무게 W를 감당할 수 있는 배낭이 있을 때 n개 종류의 다른 가치를 가진 물건을 선택해서 넣어 최대의 가치를 구하는 알고리즘이다. Knapsack 문제는 0-1 Knapsack과 Fraction Knapsack이 있다. 0-1 Knapsack은 물건을 자를 수 없고, Fraction Knapsack은 자를 수 있다. 2. 구현 물건을 하나씩 담아보면서 용량을 초과하면 담지 않고, 용량을 초과하지 않는다면 담아보고 가치가 더 크면 그 용량의 가치를 바꿔준다. 점화식은 다음과 같다. D[i][j] = max(D[i-1][j-weight[i]]+price[i], D[i-1][j]);여기서 D[i][j] 는 D[capacity][n], capacity = 배낭의 용량, n = 물건의 개수로 선언한다... 최소 공통 조상(Lowest Common Ancestor / LCA) 1. 개념 트리 그래프 G에서 임의의 정점 A와 B의 최소 공통 조상은 A와 B가 각각 자신을 포함하여 조상을 따라 거슬러 올라갈 때 처음 공통으로 만나게 되는 정점이다. 트리 그래프 G에서 임의의 정점 A와 B의 최소 공통 조상은 A 혹은 A의 조상이면서 B 혹은 B의 조상인 정점들 중 가장 깊은 정점이다. 2. 구현 보통 parent[i] 처럼 일차원 배열로 표현하던 부모 배열을 parent[u][k] 2차원 배열로 만든다. 이것이 뜻하는 바는 정점 u의 2^k 번째 부모라는 뜻이다. 이것을 풀어쓰면 2^(k+1) = 2^k + 2^k 이므로 , parent[u][k+1] = parent[parent[u][k]][k] 의 점화식을 구할 수 있다. 이 점화식에서 수 있듯이 k=i 일 때의 정보로 k=i.. 에라토스테네스의 체(get Prime Number) 소수를 구할때 최대로 효율적인 알고리즘을 만드는데 도움이 되는 것인데, 따로 개념을 설명하지는 않겠다. 내가 보기 위한 메모용 글이다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include#include#include using namespace std; #define MAX 50001 int num[MAX]; void func(int n){ int sqt = sqrt(n); for(int i=2; i n; for(int i=2;i 벨만 포드 알고리즘 (Bellman-Ford-Moore Algorithm) 1. 개념 V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 특정 출발 정점(S)에서 부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘. 다익스트라 알고리즘과는 다르게 음의 가중치를 가지는 간선이 있어도 가능하다. 또한, 그래프에 음의 가중치를 가진 사이클의 존재 여부를 확인할 수 있다. 2. 구현 V개의 정점과 E개의 간선을 가진 가중 그래프에서 어떤 정점 A에서 B까지의 최단거리는 최대 V-1개의 간선을 사용한다는 아이디어로 시작한다. 1) Distance[i] : 출발점(S)에서부터 i 정점까지의 최단거리를 저장하는 배열. Distance[S] = 0 으로 초기화하고, 나머지는 모두 무한대로 초기화 2) V-1 번 모든 간선을 확인해 아래의 조건을 만족할 때마다 최단거리배열을 갱신한다. - .. 유클리드 호제법(Euclidean algorithm) 1. 개념 유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘이다. 호제법이란 두 수가 서로의 수를 나누어 원하는 수를 얻는 알고리즘이다. 2개의 자연수 A B (A>B)에 대해 A를 B로 나눈 나머지를 r이라고 했을 때 A와 B의 최대공약수는 B와 r의 최대공약수와 같다는 성질을 이용한다. 2. 구현 1) 재귀호출 1234int gcd(int a, int b){ return b ? gcd(b, a%b) : a;}cs 2) 반복문 12345678910int gcd(int a, int b){ while (b > 0) { int q = a; a = b; b = q % b; } return a;}cs * 응용 유클리드 호제법을 응용하면 최소공배수 또한 구할 수 있다. 간단하게 곱하고 나누.. 크루스칼 알고리즘(Kruskal's Algorithm) - 최소 신장 트리(Minimum Spanning Tree) 1. 개념 크루스칼 알고리즘은 최소 신장 트리를 찾는 알고리즘이다. 최소 신장 트리는 무향 연결 G에서 간선의 가중치의 합이 최소인 신장 트리이다. 간선의 개수 E, 정점의 개수 V 일때 O(ElogV)의 시간복잡도를 가지는 알고리즘이다. 2. 구현 1) V개의 정점, E개의 간선을 가진 가중 그래프 G에서 모든 간선을 오름차순으로 정렬한다. 2) 정렬된 간선 목록에서 처음부터 마지막까지 아래의 과정을 반복한다. - 간선 목록에서 하나를 꺼내 해당 간선의 두 정점이 연결되어 있는지 확인한다. - 연결되어있지 않다면 두 정점을 연결한다. 구현할 때 팁은 오름차순 정리는 '우선순위 큐'를 사용하고, 두 정점의 연결 확인은 'Union-find'를 사용하는 것이다. 또한, cnt 변수를 따로 주어서 정점이 하.. 이전 1 2 3 다음
