확장유클리드알고리즘
-
유클리드 알고리즘, 확장 유클리드 알고리즘알고리즘/이론 2021. 4. 20. 20:07
유클리드 알고리즘을 이용한 여러 코드를 짜 봅시다! 유클리드 알고리즘으로 GCD 구하기 GCD 즉, 두 수의 최대 공약수를 구하기 위해서 유클리드 알고리즘을 사용할 수 있습니다 두 수 a, b (a>b) 가 있을 때 a를 b로 나눈 나머지가 0이면 b는 a, b의 GCD이다 라는 알고리즘이 유클리드 알고리즘인데요. 이 때 나머지가 0이 아니면 0이 될 때까지 b와 a%b의 수로 위 과정을 반복해 줍니다. swift 코드로 알아볼게요 func gcd(_ a: Int, _ b: Int) -> Int{ var a = a, b = b if a < b { swap(&a, &b) } if a == b { return a } else if b == 0 { return a } else { return gcd(b, a ..