STUDY/ALGO | DS
-
[알고리즘] Two Pointers (투 포인터) / Sliding Window (슬라이딩 윈도우)STUDY/ALGO | DS 2021. 9. 26. 22:32
Two Pointers (투 포인터) / Sliding Window (슬라이딩 윈도우) 1. 투 포인터 투 포인터란 1차원 배열에서 배열을 가리키고 있는 2개의 포인터를 조작하여, 원하는 값을 얻는 알고리즘이다. https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 예를 들어, [문제 : 수들의 합2] 에서 우리는 N개의 수열에서 특정 구간의 합이 M이 되는지를 알고싶다. 단순히 모든 경우의 수를 다 구하면 ..
-
[알고리즘] MST (최소 신장 트리, Minimum Spanning Tree)STUDY/ALGO | DS 2021. 8. 14. 21:18
MST (최소 신장 트리, Minimum Spanning Tree) 1. MST 그래프의 모든 정점을 연결할 때, 모든 정점을 간선으로 연결하며 싸이클은 존재하지 않고, 연결된 간선들의 가중치의 합은 최소가 되는 것을 말한다. +) Spanning Tree : 그래프 내 모든 정점을 포함하는 트리 +) 정점 : V , 간선 : E 2. Kruskal's Algorithm | 크루스칼 알고리즘 - 간선 선택 기반 - 시간복잡도 : O(ElogV) ㄴ 간선 정렬 : O(ElogE) ㄴ Unifon Find : O(1) * E = O(E) O(ElogE + E) => O(ElogV^2), (E O(ElogV) 1) 간선 리스트의 가중치들을 오름차순으로 정렬 2) 가중치가 작은 간선 선택 3) union-fin..
-
[알고리즘] Union-Find (유니온 파인드)STUDY/ALGO | DS 2021. 8. 14. 19:43
Union-Find (유니온 파인드) 1. Union-Find - 합집합 찾기 알고리즘 - Disjoint-Set, 서로소 집합 이라고도 한다. - 2개의 서로 다른 노드(x, y)를 선택했을 때, 2개의 노드가 같은 집합(그래프)에 속하는지 확인하는 알고리즘 2. Union - 서로 다른 2개의 노드 x, y가 포함되어 있는 집합을 합치는 연산 1 2 3 4 int find(int x) { if(x == parent[x]) return x; return parent[x] = find(parent[x]); } Colored by Color Scripter cs 3. Find - 노드 x가 어떤 집합에 포함되어 있는지 체크하는 연산. 루트 노드 반환. 1 2 3 4 5 6 7 void union(int x..