-
Sait2000's profile image
Sait2000
July 17, 2022
다익스트라에 제출한 SPFA 저격 데이터
다익스트라 알고리즘은 모든 간선이 음이 아닌 가중치를 가질 때 사용할 수 있는 최단거리 알고리즘으로, 새로 확인할 정점을 고를 때 매번 모든 정점의 알려진 최단거리를 비교하는 방식으로는 $O(V^2)$에, 우선순위 큐를 사용하면 $O(E \log E)$에 구현할 수 있습니다. 한편 벨만-포드 알고리즘의 변형이라고 볼 수 있는 SPFA 알고리즘은 간선의 가중치가 음수인 경우에도 사용할 수 있으며, 최악의 경우의 시간복잡도는 $O(VE)$이지만, $O(E \log E)$ 다익스트라 알고리즘이 정해인 문제에서도 저격 데이터가 없는 경우 통과하는 경우도 있습니다. 이 글에서는 SPFA 알고리즘의 기본적인...
-
Sait2000's profile image
Sait2000
April 14, 2022
Finite Nimber 계산
Aeren 님의 Nimber 포스트에서도 알 수 있듯이 $2^{2^k}$ 미만의 음이 아닌 정수는 nimber 덧셈(xor)과 nimber 곱에 대해서 체를 이룹니다. 이 글에서는 finite nimber에 대해서 nimber 곱, 제곱근, 곱셈 역원 등을 실제로 계산하기 위한 알고리즘을 소개합니다. https://www.ics.uci.edu/~eppstein/numth/를 참고했습니다. 기본 규칙 이 파트에서 소개하는 성질을 포함해서 앞으로 nimber의 몇가지 성질을 증명하지 않고 주어진 것으로 받아들이도록 하겠습니다. Nimber는 체를 이루므로 덧셈, 곱셈에 대해서 교환 법칙, 결합 법칙, 분배 법칙 등이 성립합니다. 따라서 앞으로 표기에서 불필요한 괄호를 생략하고, 곱셈은...