개발일지

개념 MST란 Minimun Spanning Tree의 약어로 최소 신장트리를 뜻한다. => 신장트리 중에서 가중치의 합이 최소인 신장트리를 구하는 것 => 신장트리 : Cycle이 없는 그래프 Kruskal DisjointSet을 이용하여 MST를 갱신하며 구하는 알고리즘 작동원리 1. 모든 간선을 가중치 기준으로 오름차순으로 정렬한다. 2. 가중치가 작은 간선부터 확인하면서 간선에 속한 정점 v1, v2가 다른 SET이면 UNION하고 WEIGHT만큼 RESULT에 더한다. 시간복잡도 간선을 정렬 할 때 : O(ElogE) DisjointSet 사용할 때 : O(1) O(ElogE) 문제 16398 행성 연결 www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 ..

개념 MST란 Minimun Spanning Tree의 약어로 최소 신장트리를 뜻한다. => 신장트리 중에서 가중치의 합이 최소인 신장트리를 구하는 것 => 신장트리 : Cycle이 없는 그래프 Prim Heap을 이용하여 MST를 갱신하며 구하는 알고리즘 작동원리 1. 시작노드를 우선순위 큐에 PUSH한다. 2. 우선순위 큐에서 노드를 POP한다. 3. 체크되지 않은 노드라면 WEIGHT 값만 큼 RESULT에 더하고 갈 수 있는 노드중 체크되지 않은 노드를 우선순위 큐에 PUSH한다. 4. 2 ~ 3을 우선순위 큐가 EMPTY일 때까지 반복한다. 시간복잡도 O(ElogV) 문제 13418 학교 탐방하기 www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표..

개념 최단거리를 구하는 알고리즘이다. 최단거리 + 최단거리 = 최단거리라는 그리디한 개념으로 최단거리를 찾는다. => 간선의 가중치가 음수인게 존재하면 다익스트라를 사용할 수 없다. (최단거리 + 최단거리 = 최단거리라는 보장이 깨지기 때문에) 작동원리 1. 시작 노드를 우선순위 큐에 넣는다. 2. 우선순위 큐에서 POP을한다. 3. POP한 노드가 최단거리이면 해당 노드에서 갈 수 있는 노드중 거리를 갱신하는 노드를 우선순위 큐에 PUSH한다. 4. 2 ~ 3을 우선순위 큐가 EMPTY가 될 때까지 한복한다. 시간복잡도 O(ElogV) 문제 11779 최소비용 구하기 2 www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)..

개념 최대 공약수를 쉽게 구하는 방법 작동원리 ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 ko.wikipedia.org 시간복잡도 O(1) 문제 www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가..

개념 소수를 판별하는 알고리즘 작동원리 1. 2부터 시작한다. 2. 방문하지 않은 숫자이면 그 숫자의 배수를 전부 체크한다. 3. 체크되지 않은 숫자는 소수이다. 시간복잠도 O(NloglogN) 문제 1978 소수찾기 www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 코드 #include #include using namespace std; constexpr int MAX = 1000; int main() { vector isPrime(MAX, true); isPrime[0] = isPrime[1] = false; for (in..

개념 그래프를 탐색할 때 해당 분기를 먼저 탐색하는 방법 작동원리 1. 갈 수 있는 정점이 있으면 들어간다. 2. 갈 수 있는 정점이 없으면 가장 가까운 분기로 돌아가서 다른 방향으로 들어간다. 시간복잡도 O(V + E) 문제 11724 연결 요소의 개수 www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 코드 #include using namespace std; int n, m; vector gra..

개념 그래프를 탐색할 때 인접한 노드를 우선적으로 탐색한다. 작동원리 1. Queue에 방문할 노드를 PUSH한다. 2. Queue에서 POP하고 인접한 노드를 Queue에 PUSH한다. 3. Queue가 비어있을 때까지 반복한다. 주의할 점 인접한 노드를 방문할 수 있는지 검사해야한다. - 인덱스 - 방문여부 시간복잡도 O(V + E) 문제 7576 토마토 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 코드 #include using na..

개념 이분 그래프가 있을 때 A집합과 B집합을 최대한 매칭하는 경우 Alternating Path(교차 경로) 그래프 위의 경로 중 매칭되지 않은 정점부터 시작하여 매칭을 이어주고 있지 않은 간선과 이어주는 간선이 교차하면서 반복되는 경로 (X - O - X - O - X ....) (X : 연결안된 정점, O : 연결된 정점) Augmentine Path(증가 경로) 양 끝 정점이 매칭되어 있지 않은 교차경로 교차경로 안에서 증가경로를 반전하면 매칭의 크기를 늘릴 수 있다. 작동원리 1. A그룹에서 매칭에 속하지 않은 정점들의 레벨을 구한다. 2. 증가 경로를 체크한다. 3. 더 이상 증가경로를 찾지 못할 때까지 반복한다. 시간복잡도 O(V^(1/2) * E) 문제 9525 룩 배치하기 www.acmi..