김진우 개발일지 블로그

다익스트라(dijkstra) 알고리즘다익스트라 알고리즘은 가중치가 있는 그래프에서 한 노드에서 다른 모든 노드의 최단 거리를 구하는 알고리즘이다. 우선순위 큐를 사용하여 효율적인 동작이 가능하다.동작 원리초기화시작 정점에서 각 정점까지의 거리를 무한(INF)으로 설정합니다.시작 정점의 거리는 0으로 설정합니다.우선순위 큐(priority queue, 최소 힙)를 사용하여 현재 방문할 정점을 관리합니다.가장 가까운 정점 선택우선순위 큐에서 현재까지의 최단 거리가 가장 짧은 정점을 꺼냅니다.인접한 정점 업데이트해당 정점의 인접한 정점들을 확인하며 더 짧은 경로가 있다면 갱신합니다.(현재 정점까지의 최단 거리) + (현재 정점 → 인접 정점 거리)를 계산하여 기존보다 짧으면 갱신 후 큐에 삽입합니다.모든 정점..

#include #include #include #include using namespace std;int main() { int N; cin >> N; vector trees(N); for (int i = 0; i > trees[i]; } vector differences(N - 1); for (int i = 1; i

#include #include using namespace std;bool isSafe(const vector>& board, int row, int col, int num) { for (int i = 0; i >& board) { for (int row = 0; row > board(9, vector(9)); for (int i = 0; i > board[i][j]; } } solveSudoku(board); for (int i = 0; i

#include #include #include using namespace std;bool isGoodSequence(const string& seq) { int len = seq.length(); for (int i = 1; i > N; string seq; findGoodSequence(N, seq); return 0;}

#include #include #include #include #include using namespace std;int getChickenDistance(const vector>& houses, const vector>& selectedChicken) { int totalDistance = 0; for (const auto& house : houses) { int minDistance = INT_MAX; for (const auto& shop : selectedChicken) { minDistance = min(minDistance, abs(house.first - shop.first) + abs(house.second - shop.second)..

#include #include #include #include #include using namespace std;void divideTeams(const vector>& S, int N, vector& team, int idx, int count, int& result) { if (count == N / 2) { vector linkTeam; for (int i = 1; i > N; vector> S(N, vector(N)); for (int i = 0; i > S[i][j]; } } int result = INT_MAX; vector team; divideTeams(S, N, team, 1, 0, result); cout

#include #include #include using namespace std;void sieveOfEratosthenes(int N, vector& isPrime) { isPrime[0] = isPrime[1] = false; for (int i = 2; i > M >> N; vector isPrime(N + 1, true); sieveOfEratosthenes(N, isPrime); for (int i = M; i

#include #include #include using namespace std;bool isPrime(int num) { if (num > N; vector numbers(N); for (int i = 0; i > numbers[i]; } for (int i = 0; i