알고리즘/Algorithm Theory
-
체비쇼프 거리알고리즘/Algorithm Theory 2024. 3. 24. 19:44
체비쇼프 거리 Chebyshev Distance 유클리드 거리와, 맨허튼 거리 외에도 체비쇼프 거리라는 것이 있다. 솔직히 특별한 거리는 아니고, 맨허튼 거리가 8 방향에 대해 적용되는 것이라고 보면된다. 노랑색 칸 부터 다른 칸들에 대해 체비쇼프 거리를 나타내면 다음과 같다. Flood Fill(BFS) 를 8 방향으로 돌려 얻거나, 격자의 좌표의 차이의 최대 값이 거리가 된다. strcut yx{ int y, x }; yx a, b; int distance = max(abs(a.x - b.x), abs(a.y - b.y)); https://www.acmicpc.net/problem/28452(체비쇼프 거리를 활용한 시뮬레이션 문제) 28452번: 탄막 게임 두 점 $A(x_1, y_1)$과 $B(x_..
-
라빈-카프, 접미사 배열, lcp 배열알고리즘/Algorithm Theory 2024. 3. 24. 04:40
- Hash(string to int) https://blog.joonas.io/143 문자열을 정수로 해싱하기 + 사전순 비교까지 (String to unique integer hashing) 문자열을 정수로?이 글에서 다루는 내용은, 문자열의 형태로 적혀있는 "112223"과 같은 문자열을 말하는 것이 아닙니다. 영어 소문자로만 이루어진 "aaabbb" 또는 대문자로만 이루어진 "ABCCDD" 같은 blog.joonas.io - RabinKarp https://junstar92.tistory.com/125 Rabin-karp(라빈 카프) 알고리즘 두번째로 살펴볼 문자열 탐색 알고리즘은 Rabin-Karp 입니다. 라빈카프 알고리즘은 해싱(Hashing)을 사용해서 문자열에서 특정 패턴과 일치하는지 찾..
-
세그먼트 트리 (Segment Tree)알고리즘/Algorithm Theory 2024. 3. 12. 13:48
- 일반적인 구간 합 계산 int arr[5] = {3, 2, 1, 5, 4}; arr에서의 2번째에서 4번째까지의 합 : 2 + 1 + 5 = 8 배열의 길이가 N 일 때, 일반적인 구간 합 계산으로는 O(N)의 시간 복잡도를 가진다. 만약 N의 길이가 조금만 커져도 해당 연산을 반복하게 되면, 매우 오랜 시간을 필요로 하게 된다.. 해당 경우, 세그먼트 트리를 사용하여, O(logN)의 시간 복잡도로 구간 합을 구할 수 있다. - 세그먼트 트리 해당 배열을 세그먼트 트리로 나타내면 아래와 같다. 트리는 노드는 9 개, 높이는 3인 이진트리 형태를 가진다. 루트 노드 : 총 합(전체 배열의 합) 리프 노드 : 배열의 각 원소 값 트리의 높이 : math.ceil(log2(N)) //ceil은 올림 함수..
-
[Algorithm] MST, Minimun Spanning Tree알고리즘/Algorithm Theory 2024. 2. 21. 10:38
- MST : 그래프의 모든 정점을 연결하는 최소 비용 트리 1) Kruskal 크루스칼 - 간선들을 가중치를 기준으로 오름차순 정렬 - 사이클이 생기지 않는 간선을 (정점의 개수 - 1) 개 만큼 뽑아냄 2) Prim 프림 - 최소 힙을 사용하여, 각 정점으로 부터 최소 간선을 선택해나감 - 크루스칼 알고리즘 - 크루스칼 구현 #include #include #include using namespace std; int N = 5; struct Node { int a, b; int price; }; vector line; int arr[10]; bool compare(Node t, Node v) { return t.price < v.price; } void Init() { for (int i = 0; i..
-
[Algorithm] Union-Find알고리즘/Algorithm Theory 2024. 2. 20. 11:34
- Disjoint-Sets (서로소 집합들) 교집합이 존재하지 않는 집합 - UnionFind 로 해결 가능한 문제 - 특정 집합에 몇 개의 원소가 속해있는지 - 특정 원소가 같은 집합에 속해있는지 https://www.acmicpc.net/problem/10775 https://www.acmicpc.net/problem/1717 - Union 연산과 Find 연산 1. union(A, B) : B가 A의 밑으로 들어감, A와 B가 같은 조직이됨. find(B) : B의 최상위 부모를 찾음 = A 2. union(C, D) : D가 C의 밑으로 들어감, C와 D가 같은 조직이됨. 3. union(D, B) : B가 D의 밑으로 들어감, - UnionFind의 저장 각 - 코드 구현 #include us..
-
[Backtracking] Subset Sum알고리즘/Algorithm Theory 2022. 6. 25. 19:41
Subset Sum(부분 합 문제) : 양의 정수들의 배열이 들어 올때, 배열의 부분합으로 일정 수를 만들 수 있으면 TRUE를, 만들 수 없으면 FALSE를 돌려준다. Ex) X = {8, 6, 7, 5, 3, 10, 9} T = 15이면, {8,7}, {5,10}, {6,9}, {7,5,3} > TRUE - Base Cases T = 0 이면, 선택하지않으면 항상 TRUE 이다. T < 0 이면, 항상 FALSE이다. - General Case(점화식) 총합이 T인 부분집합에 대해, 해당 부분집합은 X의 원소 x에 대해 x를 포함하거나, 포함하지않거나의 두가지로 나뉜다. 1. x를 포함할 경우, T-x 인 X-{x}의 부분집합이 존재한다. 2. x를 포함하지 않을 경우, T 인 X-{x}의 부분집합이..
-
[D&C] Binary Search알고리즘/Algorithm Theory 2022. 6. 25. 18:41
이진 탐색 정렬된 A[0...n-1]의 배열에 대해 k값을 찾을 때, a의 중간값(median)을 k 와 비교하여 같으면 종료. 이진탐색은 실은 분할정복기법이다. 중간값을 k와 비교한 뒤에 배열의 절반에 대해서만 탐색을 계속한다. 즉 문제의 크기가 n/2인 동일한 작은 문제를 해결하다보면, 문제를 해결 할 수 있다. 이진탐색 # A가 정렬된 배열일때 A[a...b]에서 k값을 탐색 int binary_search(A[a...b], k, a, b): if a>b: return -1 mid = (a+b)/2 if A[mid] > k: return binary_search(A, k, a, mid-1) elif A[mid] < k: return binary_search(A, k, mid+1, b) else re..