다익스트라, 벨만포드, 플로이드 워셜은 모두 최단 거리를 구할 때 사용하는 알고리즘입니다.사실 공부한거 나중에 까먹으면 한눈에 보고 싶을 것 같아서 포스팅으로 정리한 건데잘못된 부분이 있다면 댓글로 따끔하게 일침 부탁드립니다. 감사합니다. ▶ 다익스트라 알고리즘 (백준 1753번 최단경로 문제에서 나온 예제입니다.) 다익스트라 알고리즘은 엣지값이 양수일때만 사용이 가능하고 시작점에서 다른 모든 노드까지의 최단 거리를 구합니다.최단 거리 리스트는 1차원 리스트로 출발 노드는 0, 나머지는 무한대로 초기화해주고,그래프는 인접 리스트 [[] for _ range(n)] 형태로 생겼습니다.visited = [False] * (n+1) # 방문 여부 리스트graph = [[] for _ in range(n+1)..

학교에서 배운 최대공배수 구하는 방법과유클리드 호제법 알고리즘을 사용해서 코드를 구현하는 방법은 다르다. 나처럼 유클리드 호제법이 뭔데? 라고 생각한 분들을 위해5분 안에 쉽게 이해되도록 설명해보겠다. 최소공배수를 구하는 공식에 최대공약수가 들어가므로최대공약수 먼저 알아보겠다.  ※ 유클리드 호제법 - 최대 공약수 유클리드 호제법은 두 자연수의 최대 공약수를 구하는 알고리즘이다.먼저 MOD 연산을 알고 있어야 하는데 MOD는 두 수의 나머지를 구하는 연산이다.예를 들어 파이썬에서 나머지를 구하는 연산은 % 이며, 10 % 6 = 4 가 나온다. 유클리드 호제법으로 108과 138의 최대공약수를 구해보겠다.이해하기 쉽게 그림으로 풀어봤다.  1. 큰 수를 작은 수로 MOD 연산 실행2. 전 단계에서의 작은..