백준147 백준 1967 c++ -[PlusUltraCode] [필자 사고] 트리의 지름문제이다. 처음보면 당황할 수 있지만 한번만 이해하면 쉽게 풀 수 있는 문제이다. 트리의 지름이란 임의의 두점을 선택했을때 가장 거리가 긴 노드간의 길이를 말한다. 지름을 구하기 위해서는 다음과 같다. 1. 임의의 노드 하나를 선택하여 가장 거리가 먼 노드를 구한다. 2. 가장 거리가 먼 노드에서 다시 시작하여 가장 거리가 먼 노드를 또 구한다. 3. 2번째로 구한 가장 거리가 먼 노드의 길이가 지름의 길이이다. 문제를 해결하는 알고리즘은 dfs 다익스트라 등등 많이 있고 필자는 다익스트라를 이용하여 해결했다. [소스 코드] #include #include #include #include using namespace std; typedef pair Node; vector Arr;.. 2024. 2. 20. 백준 1167 c++ - [PlusUltraCode] [필자 사고] 트리의 지름을 구하라는 문제이다. 먼저 트리의 지름이란 임의이 두 점을 골랐을 때 가장 거리가 긴 길이가 트리의 지름이다. 먼저 임의이 아무 지점에서 각 지점에서의 최단 거리를 구한다. 최단거리중 거리가 가장 긴 IDX를 골라 시작점으로 다시 최단 거리를 구하게 되면 가장 거리가 긴 지점이 나오게 된다. #include #include #include using namespace std; typedef pair Node; const int MAX_NUM = 10000000; vector Arr; vector visited; vector pathLoad; int N; priority_queue pq; void Input() { cin >> N; Arr.resize(N + 1); pathLoa.. 2024. 2. 20. 백준 2166 c++ -[PlusUltraCode] [필자사고] 고등학교 때 배운 신발끈 공식을 적용하면 쉽게 풀 수 있는 문제이다 x1 x2 x3 x1 y1 y2 y3 y1 (x1*y2+x2*y3+x3*y1)-(x2*y1+x3*y2+x1*y3)= ccw 문제에서 다각형의 넓이를 구해야 되므로 x3,y3을 원점이라 하고 각 선분마다 ccw값을 구하고 결과값에 더해준다. 마지막으로 절대값을 취해주고 2로 나눠주면 답이 나온다. #include #include #include #include using namespace std; int N; long x[10001]; long y[10001]; //x1 x2 0 x1 //y1 y2 0 y1 //x1*y2 -x2*y1; void Input() { cin >> N; for (int i = 0; i < N; i++.. 2024. 2. 19. 백준 2162 c++ - [PlusUltraCode] [필자 사고] 백준 17387번으로 선분의 교차여부를 코드로 작성하였다. 이 문제는 그에 더해서 Union 알고리즘을 사용하여 문제를 해결할 수 있는지 묻는 문제였다. 먼저 선분의 교차여부 알고리즘을 만들고 Union 알고리즘을 아용하여 그룹의 최대 갯수를 구했다. #include #include #include #include using namespace std; typedef struct Point { long x1, y1, x2, y2; }Point; vector parent; vector visited; vector groupCount; int find(int a) { if (a == parent[a])return a; else return parent[a] = find(parent[a]); } .. 2024. 2. 19. 이전 1 ··· 32 33 34 35 36 37 다음