본문 바로가기

algorithm

(2)

[Algorithm] 최대 공약수, 최소 공배수 구하기 GCD(Greatest Common Divisor) 최대 공약수 구하기 유클리드 호제법 사용 def gcd(a, b): while b: a, b = b, a % b return a a = b x q + r 이라고 했을 때, GCD(a, b) = GCD(b, r)를 만족한다. 간단 증명: 수학적으로 증명하는 방법이 있지만 이해를 위해서 간단히 설명하자면 아래와 같이 표현할 수 있다. b = r x m + n으로 표현할 때, n이 0이라면 b = rm으로 표현된다. 즉, b와 r의 최대 공약수 GCD(b, r) = m이 된다. a = bq + r = rmq + r = r(mq + 1) 이므로 GCD(a, b) = r 이다. => GCD(a, b) = GCD(b, r) = GCD(r, 0) = r LCM(Lo..

[Java] Kruskal's Algorithm 크루스칼 알고리즘 - 최소 신장 트리(MST) 최소 신장 트리 MST(Minimun Spanning Tree) - 크루스칼 알고리즘 자바 구현 🧐 최소 신장 트리 MST(Minimun Spanning Tree)란? 최소한의 가중치를 사용하여 모든 정점이 연결되어 있을 수 있게하는 기법이다. 예시) 도시들은 모두 다리로 연결되어있을 때, 모든 도시를 갈 수 있게 다리를 연결하되 최소한의 다리 길이만을 사용하는 방법 (도시가 가로등으로 다리가 전선으로 바뀔수도 있다.) 네비게이션의 최단 경로 모든 정점(node 혹은 vortex)가 연결될 수 있는 경로 중 가장 적은 가중치(여기선 거리)를 사용하는 경로 주의사항 여기서 연결이란 다른 노드를 거쳐서 가는 것을 포함한다. 간선 혹은 브랜치(노드를 이어주는 선, 거리)는 방향성을 갖지 않는다.(연결만 되어있..

이전 1 다음

728x90

티스토리툴바