GCD & Extended Euclidean Algorithm
Greatest Common Divisor(GCD) 두 수를 모두 나누는 가장 큰 수 최대공약수가 무엇인지는 모두 알 것이다. PS에서도 생각보다 자주 쓰이는 개념이다. Greatest Common Divsior Euclidean Algorithm Extended Euclidean Algorithm Greatest Common Divsior 먼저, 정의를 조금 다르게 해보자. 둘 다 양수일 때는 원래의 정의와 동일하다. 둘 중 하나가 0이고, 하나가 0이 아닐 때도 잘 생각해보면 원래의 정의에 부합한다는 것을 알 수 있다. 하지만 이라는 것은 원래의 정의에 어긋난다. 0이 0을 나누고, 0보다 큰 수는 0을 나누지 않는다는 말이 되기 때문이다. 하지만 이렇게 정의함으로서 얻는 장점들이 있다. 예를 들어,..
2016. 8. 9. 14:49