방금 프로그래머스에서 풀어본 방식인 크루스칼 알고리즘으로 풀어보았다. 여기서 좀 헷갈렸고, 놓쳤던 부분은 parent를 설정할 때 정점이 1부터 시작한다는 것으로 생각해야하고, 그래서 V + 1 사이즈로 초기화해야한다. // MST(Minimum Spanning Tree) // 최소 신장 트리는 두 종류 알고리즘으로 풀 수 있다. // 크루스칼 알고리즘 VS 프림 알고리즘 // 크루스칼 알고리즘은 간선을 선택하며 찾는 알고리즘 // 프림 알고리즘은 정점을 선택하며 찾는 알고리즘이다. #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; long long V, E; long long getRoot(vector& par..
알고리즘
최소 신장 트리, C++ 최소 신장 트리, MST(Minimum Spanning Tree) 알고리즘은 두 가지 방식으로 풀 수 있다. 크루스칼 알고리즘과 프림 알고리즘이다. 크루스칼 알고리즘은 간선을 가중치가 작은 순서대로 오름차순으로 정렬을하고, 사이클을 형성하지 않는 방향으로 간선을 선택하며 트리를 구성한다. 정점이 많을 때 효과적인 알고리즘이다. 프림 알고리즘은 아무 정점을 시작 정점으로 설정한 뒤, 시작 정점의 인접 정점들 중에 가장 가중치가 작은 간선을 선택하며 정점을 잇는다. 하나의 정점을 잇게 되면, 현재까지 방문한 정점들의 인접 정점중에서 방문하지 않으면서 가장 작은 가중치를 가진 간선을 선택하는 알고리즘이다. 이렇게 되면 문제는 정점이 많아지게 된다면, 이전 방문했던 모든 정점들의 인접 ..
www.acmicpc.net/problem/1708 볼록 껍질 문제는 Convex Hull 문제라고 보면 된다. Convex Hull 문제를 푸는 방식은 두 가지가 있다고 한다. 하나는 Graham Scan 방식과 Jarvis March 방식이다. Jarvis March 방식은 나도 아직 잘 모르겠고, Graham Scan 방식으로 문제를 풀었다. 알고리즘 설명은 이렇다. 1. 좌표값들이 주어진다. 2. 모든 좌표 중에서 극좌표를 결정한다. 3. 극좌표 결정은 y 좌표값이 가장 작고, 만약 y값이 같다면 x값이 작은 좌표를 찾아 극좌표로 결정하면 된다. 4. 극좌표를 기준으로 모든 좌표들을 반시계방향으로 좌표를 정렬한다. 5. 이 때, 정렬하는 방식은 ccw 방식을 사용하면 된다. 6. ccw > 0 이..
점 P1, P2, P3가 주어질 때, 점 P1을 기준으로 세 점이 반시계 방향인지, 직선인지, 시계 방향인지 방향성을 판단하는 문제이다. #define _CRT_SECURE_NO_WARNINGS #include int ccw(int x1, int y1, int x2, int y2, int x3, int y3) { int res; res = 1 * (x1 * y2 - y1 * x2) + 1 * (x2 * y3 - y2 * x3) + 1 * (x3 * y1 - x1 * y3); if (res > 0) return 1; else if (res == 0) return 0; else return -1; } int main() { int x1, y1, x2, y2, x3, y3; scanf("%d %d %d %d ..
