괴물 클럽

철도 2 (Railway 2) 트리 구조에서 모든 노드 쌍 사이의 거리 함수 $f(i,j)$의 총합을 구하는 문제입니다. 이 문제의 핵심은 특정 노드에서 출발할 때 트리의 지름(Diameter) 끝점 중 하나로 향하는 경로가 최적의 해를 포함한다는 점입니다. 트리의 지름을 구한 뒤, 두 끝점을 기준으로 각 노드까지의 거리를 계산하여 정렬합니다. 이를 통해 각 노드별 기여도를 계산하여 ...

문제 도입 그래프 이론 문제를 해결하다 보면, 특정 노드가 구간 내의 모든 노드와 간선을 연결해야 하는 상황이 종종 발생한다. 예를 들어, "노드 u에서 구간 [L, R]에 속하는 모든 노드로 이동 가능"과 같은 제약 조건이 대표적인 경우다. 이러한 경우 단순히 모든 노드를 순회하며 간선을 생성하면 O(n²)의 시간 복잡도가 발생하여 시간 초과가 발생할 수 있다. 이러한 ...

A 문제 문제는 매우 간단합니다. 세 정수 r, g, b와 문자열 c가 주어집니다. c가 "Red"이면 g와 b 중 최솟값을, "Blue"이면 r와 g 중 최솟값을, 그 외의 경우 r와 b 중 최솟값을 출력하면 됩니다. 코드 보기 #include<bits/stdc++.h> using namespace std; int main(){ int red, green, blue; string color; cin >> red > ...

A* 알고리즘 MATLAB 구현 1. MATLAB 코드 구현 % Excel 파일에서 맵 읽기 map = xlsread('your_map_file.xlsx'); % 시작점과 종료점 설정 startPoint = [1, 1]; endPoint = [size(map, 1), size(map, 2)]; % A* 알고리즘 핵심 코드 openSet = [startPoint]; cameFrom = containers.Map(); gScore = containers.Map(); gScore(startPoint) = 0; ...