알고리즘
[알고리즘] 최소공배수와 최대공약수 C++
0. 목차 최대공약수(Greatest Common Divisior) 의 개념 최대공약수 알고리즘 1 (시간복잡도 O( min(A ,B) ) ) 최대공약수 알고리즘 유클리드 호제법 (시간복잡도 O(logN)) 최소공배수(Lease Common Multiple)의 개념 최소공배수 알고리즘 (시간복잡도 O(logN)) 1. 최대공약수(Greatest Common Divisior)의 개념 최대 공약수의 개념을 설명하기 위해선, 먼저 공약수의 개념을 짚고가자. 공약수란? 2개이상의 N개의 수가 있을때, N개의 숫자에 모두 나누어떨어지는 공통되는 약수를 의미한다. 예를들어 4, 10, 16 세개의 공약수를 살펴보자 4의 약수는 1, 2, 4 10의 약수는 1, 2, 5, 10 16의 약수는 1, 2, 4, 8, 1..
2021. 8. 12.
