유클리드 호제법1 유클리드 호제법 백준의 정수론 문제를 살펴보다, 유클리드 호제법에 대해 알게 되었다. 어떤 것인지 간단하게 파악하고, 이를 이용해 문제를 푼 것에 대해 짤막히 기록한다. 유클리드 호제법 자연수 혹은 정수 사이의 최대공약수(Greatest Common Denominator: GCD)를 구하기 위한 알고리즘. a와 b의 최대공약수는, a / b의 나머지 r과 b의 최대공약수와 같다. 이를 실제 함수로 구현하면 재귀 혹은 반복을 통해 구현할 수 있다. 나는 아래와 같은 코드를 작성해 문제풀이에 활용하였다. const getGCD = (a, b) => { if (a === b) return a; if (a === 1 || b === 1) return 1; if (b === 0) return a; return getGCD(b, .. 2023. 10. 29. 이전 1 다음