본문 바로가기

algorithm8

[Algorithm] Dijkstra Algorithm (다익스트라 알고리즘) Dijkstra 알고리즘은 단일 시작점에서 모든 정점으로의 거리를 구하는 알고리즘이다. 다음과 같은 그래프가 주어졌다고 하자. 해당 그래프는 인접 행렬(Adjacency Matrix) W로 구현되어 있다. 시작점은 1번이다. 위 그림에서 dist 배열은 시작점에 해당하는 1번 정점으로부터의 거리를 나타낸다. dist[i] : 1번 정점으로부터 i번 정점까지의 거리 dist 배열의 각 원소를 INF로 초기화 한다. 우선, 시작점에서 시작점으로의 거리를 0으로 설정한다. 그리고 시작점에 인접한 정점들의 거리를 갱신한다. 위 사진의 경우 1번 정점은 2번 정점과 3번 정점에 인접해있다. 정점까지의 거리는 각각 2와 3이다. Dijkstra 알고리즘의 핵심은 dist[j]를 구할 때, 특정 경유지(예를 들어 i.. 2021. 4. 6.
[BOJ] 백준 1222 - 홍준 프로그래밍 대회 문제 링크 1222번: 홍준 프로그래밍 대회 홍준이는 프로그래밍 대회를 개최했다. 이 대회는 사람들이 팀을 이루어서 참가해야 하며, 팀원의 수는 홍준이가 정해준다. 팀원이 홍준이가 정한 값보다 부족하다면, 그 팀은 대회에 참여할 수 www.acmicpc.net 첫째 줄에 학교의 수 N(2 a; divisorCount(a); } long long maxParticipants = 0; for (long long i = 1; i n; for (int i = 0; i > a; divisor[a]++; } long long maxParticipants = 0; for (long long i = 1; i 2021. 4. 1.