728x90
반응형
##최대공약수(GCD)
1.구하는 방법
1) 완전탐색
-수 중 제일 작은 수n , 1부터 n까지 나누어 떨어지는 수 구하기
2) 완전탐색 (제곱근 까지)
-수 중 제일 작은 수n , 1부터 sqrt(n)까지 나누어 떨어지는 수 구하기
3) 유클리드 호제법
-두수 중 하나의 수로 다른 수를 계속 나누는 방법
-시간복잡도: 제일 빠른 방법
1
2
3
4
5
6
7
8
|
int gcd (int a, int b) {
while (b !=0) {
int r = a % b;
a = b;
b =r;
}
return a;
}
|
cs |
##최소 공배수(LCM)
1.구하는 방법
: l = (a/gcd)*(b*gcd)*gcd
반응형
'Algorithm_몰랐던 함수 및 개념' 카테고리의 다른 글
[알고리즘] 부르트포스,완전탐색 (0) | 2021.08.01 |
---|---|
[알고리즘] 소수,에라토스테네스의 체 (0) | 2021.07.31 |
[알고리즘] 그래프 02. 그래프 표현 (0) | 2021.07.27 |
[알고리즘] 그래프 01.개념 (0) | 2021.07.27 |
개념 (0) | 2021.05.30 |