728x90 프로그래밍/이론2 [이론] 플로이드-워셜 알고리즘 i번 정점에서 j번 정점로 가는 최소 거리를 구하는 알고리즘이다. 3중 for문을 이용하기 때문에 정점의 개수가 적을 때 이용이 가능하다. i → j 가중치가 c일 경우에 i → k → j, 즉 i → k의 최소 가중치 + k → j의 최소 가중치 a+b를 비교해서 가중치가 더 작은 경로를 i → j 가중치로 저장해서 i → j의 최소 가중치를 구하는 알고리즘이다. 2023. 2. 14. [이론] 에라토스테네스의 체 채로 걸러내는 것과 같이 어떤 수가 소수로 판정되면 어떤 수에 1을 제외한 나머지 수를 곱한 것은 모두 합성수이기 때문에 이들을 모두 제거하고 남아있는 수 중 다음으로 작은 수에 1을 제외한 나머지 수를 곱한 값들을 제거한다. 이를 계속 반복하면 남아있는 것들은 모두 소수이다. 2023. 2. 13. 이전 1 다음 728x90
