알고리즘
-
세그먼트 트리 시리즈알고리즘/백준 2024. 3. 13. 14:22
각 구간에 대해 특정 해를 항상 가지고 있는 트리. 자료구조로 생각하고 풀이하면 편하다. 각 구간 ~ 에 대해 최소값/최대값/합/곱 ... 을 가지는 트리 - 구간 합 (기본) https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net - 최대 최소 값 https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을..
-
세그먼트 트리 (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..
-
[백준] 30826번 그 긴 수알고리즘/백준 2024. 2. 9. 04:42
https://www.acmicpc.net/problem/30826 30826번: 그 긴 수 팰린드롬 수는 앞에서 읽어도, 뒤에서 읽어도 같은 수를 말한다. 예를 들어, $7$, $88$, $14641$은 팰린드롬 수지만 $201$, $329$, $4700$ 등은 팰린드롬 수가 아니다. 상윤이는 팰린드롬 수 중 양의 정수면 www.acmicpc.net Ad Hoc 문제, 저번의 거울 숫자 문제와 비슷한가? 싶어서 건드려 보았는데, 그냥 각 경우를 고려해서 잘 짜주면 된다. - 문제 요약 팰린드롬 수를 순차적으로 계속 붙여나간 수에서 K 번 째 위치한 수를 찾아주면 된다. Ex. 12345678911223344556677 ... - 각 자리 수 마다 팰린드롬 수를 만들 수 있는 경우의 수 한자리 수의 경우..
-
[BFS] Priority Queue 활용 BFS알고리즘/백준 2024. 2. 8. 13:52
일명 물 채우기 BFS 문제 물을 담아두기 위해서, 테두리부터 물을 흘려 보낸다는 아이디어가 필요하다. - 알고리즘 0. 한 번 추가됬던 칸은 check. 1. 테두리를 우선순위 큐에 추가 2. 우선순위 큐에서 하나씩 pop 하면서, 주변 탐색 3. 주변 탐색 시, 더 낮은 높이면 해당 칸으로 나아가 탐색을 진행하고, 아니면 우선순위 큐에 추가 4. 탐색 시에는 처음에 우선순위 큐에서 pop 한 칸의 높이를 기준으로 탐색 - 예시 문제 1. 수영장 사장님 : https://www.acmicpc.net/problem/15730 2. 물 채우기 : https://www.acmicpc.net/problem/2276 - 수영장 사장님 Code #include #include #include #include us..
-
[Algorithm] 다익스트라알고리즘 2024. 2. 2. 11:24
최단 경로 (BFS) - 그래프에 가중치가 서로 같은 경우 최단 거리 (Dijkstra) - 그래프에 가중치 같이 포함, 정점 A 에서 다른 N 개의 정점에 대한 최소 비용을 구함 가중치가 있는 그래프에서 최소 비용 구하기 BFS와 매우 유사하지만, Queue를 사용하는 것이 아닌, PriorityQueue를 통해 인접 정점이 아닌 거리가 제일 짧은 간선을 뽑아낸다. Dijkstra Algorithm - 각 순간 마다 가장 작은 비용을 선택하면서, 정답 배열과 비교 파란색: Priority Queue 주황색: 정답배열 Code #include #include #include #include #include using namespace std; struct Edge { int num; int cost; /..