눈송이의 개발생활

유클리드 호제법이 뭘까? 두 수의 최대공약수를 구하는 알고리즘이다. 💡 호제법 : 두 수가 서로 상대 수를 나눠서 원하는 수를 얻는 알고리즘 두 양의 정수 a, b (a>b)에 대해서 r = a % b (r은 a를 b로 나눈 나머지) 이라고 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 반복적으로, rr = b % r 이라고 하면, rr, rrr, ...이 0이 될 때까지 이 과정을 반복한다. rr이 0이면 a, b의 최대 공약수는 r이 된다. 유클리드 호제법을 예시를 통해서 보자! 📌 2058과 1071의 최대공약수 구하기 먼저, 큰 수(2058)를 작은 수(1071)로 나눈다. 2058 % 1071 = 987 나머지(987)가 0이 아니기 때문에, 1071을 987로 나누고 이 과정을 ..

에라토스테네스의 체는 뭘까? 가장 대표적인 소수를 판별하는 알고리즘이다. 소수를 대량으로 빠르고 정확하게 구하는 방법이다. 일반적으로 소수를 구하는 알고리즘의 시간복잡도는 O(N)이다. BUT 에라토스테네스의 체를 사용하게 되면 시간복잡도를 O(N^(1/2))로 줄일 수 있다. 에라토스테네스의 체의 원리? 모든 약수들을 대친 형태를 이룬다는 점에서 가능하다. 예를 들어, 8의 약수인 2와 4를 보면 2\*4 = 4\*2 식에서 대칭인 것을 발견할 수 있다. 따라서 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 된다. 위의 예시로 다시 설명하면, 8의 약수를 구하기 위해서는 1, 2만 보면 된다. (8=2루트2) 🚩 하나의 소수 판별 def is_prime(x): end = int(x ** 0.5) f..