알고리즘
-
SCC-Kosaraju알고리즘 2020. 9. 3. 17:28
SCC(Strongly Connected Component) - 개념 : 방향그래프의 connected component 내 노드 u에서 v로 향하는 경로, 노드 v에서 u로 향하는 경로가 존재하면 해당 connected component를 SCC라 한다. (Connected component : 그래프는 여러개의 부분 그래프로 구성될 수 있는데 서로 연결되어 있는 여러개의 고립된 부분 그래프 각각을 connected component) - SCC를 찾는 알고리즘 Kosaraju's Algorithm : 2번의 DFS를 통해 SCC를 찾는다. 과정 1. digraph G에서 임의의 정점 i부터 dfs 수행 수행 속에서 먼저 끝나는 즉 다른 곳에 갈 곳이 없는 vertex를 stack에 push 하여 저장..
-
위상정렬알고리즘 2020. 8. 24. 21:15
Topology Sort 위상정렬 - 개념 : 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘. 방향성을 거스르지 않는다. 여러 경로가 존재할 수 있기에, 답은 다양하게 나올 수 있다. - 위상 정렬은 DAG(Directed Acyclic Graph, 사이클이 없는 방향그래프)에서만 사용이 가능하다. - 시간복잡도 : O(V+E), V 정점 개수 E 간선 개수 - 구현방법 1. 스택 (DFS 방법)① 임의의 정점에서 시작한다.② 시작한 정점과 연결된 정점들을 모두 방문한다.③ 방문한 정점에서 더이상 탐색할 정점이 없으면 스택에 push해준다.모든 정점을 방문할 때까지 위의 과정은 반복한다.(만약 더이상 탐색할 정점이 없는데 모든 정점을 방문하지 않았다면 DA..
-
CCW알고리즘 2020. 8. 23. 16:43
CCW(CounterClockWise) Algirothm - 개념: 반시계 방향 알고리즘 평면 위에 놓여진 세 개의 점을 벡터의 외적을 이용해서 방향 관계를 찾는 알고리즘. 자세한 설명) https://degurii.tistory.com/47 - 2차원 평면상에 각각 x, y 좌표를 갖고 있는 세점 (p1, p2, p3)가 존재한다고 했을 때, CCW 공식 s = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y) - (p1.y * p2.x + p2.y * p3.x + p3.y * p1.x) 만일 결과값 s가 0보다 작다면(s 0) p1, p2 벡터를 기준으로..
-
LCA알고리즘 2020. 8. 21. 18:36
LCA(Lowest Common Ancestor) - 개념: 트리에서 두 개의 정점를 선택하였을 때 최소 공통 조상(가장 가까운 공통 조상)을 찾는 알고리즘 - 구현방법 정점의 깊이를 저장하는 배열 depth[i] = i번 정점의 깊이 각 정점의 부모를 저장하는 배열 parent[i] = i번 정점의 부모 있다고 할때 1. 간단한 방법 : ① 두 정점 중 깊이가 더 깊은 정점를 찾아, 깊이가 같아질 때까지 그 정점의 부모로 계속 이동한다. ex) 정점 A, 정점 B if depth[A] > depth[B] // A정점이 깊이가 더 깊음 while(depth[A] != depth[B]) A = parent[A] ② 높이가 같아졌다면, 두 정점이 같아질 때까지 두 정점을 동시에 부모로 이동한다. while(..
-
TSP알고리즘 2020. 8. 14. 17:23
TSP(Travelling Salesman Problem) : 여행하는 외판원 문제 - 개념 : 도시의 개수와 각 도시간 연결되있는 거리들이 주어질 때, 모든 도시를 한 번씩 방문하고 원래 도시로 돌아올 수 있는 최단 거리 경로를 구하는 문제 -풀이 1. 완전탐색 : 각 도시를 잇는 모든 경로를 다 확인해보는 방법. 재귀 혹은 순열을 이용해서 푸는 방법인데 현실적으로 이 방법을 사용하지 않는다. 도시의 수가 N일때 시간복잡도가 O(N!)으로 엄청난 시간을 필요로 하기 때문이다. 2. dp : memoization으로 풀 수 있다. 점화식dp[i][j] = i번째 도시까지 j상태의 도시를 지나쳐 왔을 때의 최소 비용 (j상태는 몇번 몇번 도시를 방문했었는지 즉, 각 도시의 방문 여부 상태) +) dp를 사..
-
피사노 주기알고리즘 2020. 8. 9. 21:47
피보나치- 개념 : F0 = 0 , F1 = 1일때 Fn = Fn-1 + Fn-2- 구현 방법 1. 재귀적 방법 : O(2^n) 2. dp 방법 (= memoization 방법) : O(n) 3. 피사노 주기 피사노 주기(Pisano period) - 개념 : 피보나치 수를 어떤 수 K로 나눌 때, 나머지는 항상 주기를 가지게 되는데 이를 피사노 주기라고 한다. ex) 피보나치 수를 3으로 나누었을때, 주기의 길이는 8 N 0 1 2 3 4 5 6 7 89101112131415 Fn 0 1 1 2 3 5 8 13 21 34 55 89 144 233377 610 PP 0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 - 성질 : 주기의 길이를 P라고 하면 N번째 피보나치 수를 M으로 나눈 나머지는 ..
-
Prefix sum알고리즘 2020. 8. 1. 12:34
Prefix sum (구간합) Algorithm - 구간 합이란? 배열 전체 값 중 L ~ R 번째 원소 구간의 합을 의미 - 구현 방법 : Prefix sum algorithm은 데이터 원소들을 누적해서 합한 값을 이용한다. a1, a2, ..., aN 전체 N개의 숫자들이 있을 때 prefix sum의 i번째 값을 구하면 Pi = a1 + a2 + a3 + ... + ai ex) 숫자 5개가 있다고 하자. {1,2,3,4,5}; 그러면 prefix[6] = {0,1,3,4,10,15}; 만약 1번째부터 3번째까지 합을 구하고 싶다면 : prefix[3] - prefix[1-1] = 4 - 0 = 4 이런식으로 계산. => prefix sum의 차로 구간합을 계산한다. L ~ R까지 합을 구하고 싶으면..
-
에라토스테네스의 체알고리즘 2020. 7. 16. 22:11
에라토스테네스의 체 - 개념 : 소수(prime number)를 판별하는 알고리즘 소수? '양의 약수를 두 개만 가지는 지연수' = '1과 자기자신' - 원리 : 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여 해당하는 값을 넣어주고, 이후에 하나씩 지워가는 방법 1. 배열을 생성하여 초기화한다.2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다. 이미 지워진 수라면 배수를 확인하지 않고 다음 수로 넘어간다. (2를 제외한 모든 2의 배수를 지움 3을 제외한 모든 3의 배수를 지움 4를 제외한 모든 4의 배수를 지움 ... 이런식) 3. 2부터 시작하여 남아있는 수를 모두 출력한다. - 구현 코드 123456789101112131415161718192021222324252627#inclu..