최대공약수 GCD
두 자연수의 공통된 약수 중 가장 큰 수
ex) 30 과 45 의 최대공약수는 15
최소공배수 LCM
두 자연수의 공통된 배수 중 가장 작은 수
최소공배수 = 두 자연수의 곱 / 최대공약수
ex) 6과 10의 최소공배수는 30
유클리드 호제법
2개의 자연수 a,b에 대해 (a > b) a를 b로 나눈 나머지를 r이라 하면
a와 b의 최대공약수는 b와 r의 최대공약수와 같다
이 성질을 이용해,
b를 r로 나눈 나머지를 r0라 하고, r을 r0으로 나누는 과정을 반복해서 나머지가 0일때
나눈수가 a와 b의 최대공약수가 된다.
func gcd(num1: Int, num2: Int) -> Int {
if num2 == 0 {
return num1
} else {
return gcd(num1: num2, num2: num1 % num2)
}
}
시간복잡도: O(logN)
'코딩테스트 > 알고리즘' 카테고리의 다른 글
투포인터 알고리즘 Swift (0) | 2024.04.14 |
---|---|
순열과 조합 Swift (0) | 2024.04.10 |
깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) Swift (1) | 2024.04.08 |
이분탐색 Swift (1) | 2024.04.06 |
동적계획법 DP(Dynamic Programming) (0) | 2023.04.20 |