본문 바로가기
반응형

수학42

BOJ 2609 : 최대공약수와 최소공배수 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2609 두 수 A, B의 최대공약수가 G라면 A = a * G, B = b * G로 정의할 수 있다. 그러면 최소공배수는 a * b * G = A * B / G 가 된다. 최대공약수는 유클리드 호제법으로 구할 수 있다. A % B = R이라고 하면, A와 B의 최대공약수는 B와 R의 최대공약수와 같다. (A ≥ B) 즉, B가 0이 아닌 경우 gcd(B, A % B)를 구한다. 이 과정을 B가 0이 되는 경우에 A를 return하면 된다. 최소공배수의 경우 A * B / G의 경우 A * B 연산에 의해 overflow가 발생할 수 있다. 따라서 나누기를 먼저해서 (A / G * B) overflow를 방지한다. #include int.. 2021. 5. 5.
제곱근 Square root : 바빌로니아 법 (The Babylonian Method) C, C++ 전체 링크 바빌로니아 법은 임의의 수의 제곱근에 빠르게 수렴하는 수열을 만들어 근삿값을 구하는 방법이다. 이 수열을 계속해서 반복하면 x가 √a가 된다. 먼저 PRECISION_COUNT를 5로 정의하고, 바빌로니아 법을 5번 반복해보자. printf에 .[Number]f로 옵션을 주면 Number의 자릿수만큼 소수점을 출력할 수 있다. #include #define PRECISION_COUNT (5) double sqrt(int num) { double x = num / 2.0; for (int i = 0; i < PRECISION_COUNT; i++) { x = (x + (num / x)) / 2; /* xn+1 = (xn + (num / xn)) / 2 */ } return x; } i.. 2021. 4. 9.
BOJ 10830 : 행렬 제곱 알고리즘 문제 전체 링크 www.acmicpc.net/problem/10830 곱셈 문제처럼 이진수의 원리를 그대로 적용하여 해결하였다. 행렬의 곱은 A = B * C 일 때, A[r][c] = ∑B[r][k] * B[k][c]를 이용한다. #include typedef unsigned long long int ull; int N; ull B; int matrix[7][7]; int ans[7][7]; void multiply(int matrixA[][7], int matrixB[][7]) { int temp[7][7] = { 0 }; for (int r = 1; r 2021. 3. 25.
BOJ 1629 : 곱셈 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1629 A를 B번 곱할 때, B가 최대 2,147,483,647이므로, 2,147,483,647번 곱하면 연산 비용이 너무 많이 든다. 즉, O(B)의 비용이 든다. 하지만 분할 정복을 이용하면, O(logB)로 해결 가능하다. 만약 A를 100번 곱해야 한다고 생각해보자. A100 = A50 * A50 A50 = A25 * A25 A25 = A12 * A13 A12 = A6 * A6 A13 = A6 * A7 A6 = A3 * A3 A7 = A3 * A4 A3 = A * A2 A4 = A2 * A2 A2 = A * A 따라서, 재귀 함수를 이용해 답을 (log100)번만에 찾을 수 있다. typedef unsigned long long.. 2021. 3. 24.
BOJ 4913 : 페르마의 크리스마스 정리 알고리즘 문제 전체 링크 www.acmicpc.net/problem/4913 1,000,000의 크기의 수를 매번 소수 판단할 수 없으므로 에라토스테네스의 체를 이용하여 메모해둔다. 그리고 매번 L과 U에 포함된 소수의 개수와 소수 중 제곱수의 수를 셀 수 없으므로 아래와 같이 메모한다. #define MAX (1000000) int L, U; int prime[MAX + 100]; int primeSum[MAX + 100]; int squreSum[MAX + 100]; int main() { makePrime(); /* 에라토스테네스의 체 */ squreSum[2] = primeSum[2] = 1; for (int i = 3; i = 1 : L이 자연수인 경우 (U는 항상 L보다 크다) 2) L이 음수.. 2021. 3. 19.
BOJ 6588 : 골드바흐의 추측 알고리즘 문제 전체 링크 www.acmicpc.net/problem/6588 어떤 숫자가 소수의 합으로 이루어져 있는지 판단해야 한다. 매번 소수 판단 함수를 사용하면, 비용이 많이 들어 time out이 나기 때문에, 주어진 n = 1000000이하의 수에 대해 모두 소수인지 미리 구해둔다. 즉, 에라토스테네스의 체를 이용하여 소수를 먼저 만든다. 그리고 primeNumber에는 prime을 check하여 실제 소수 값을 순서대로 적어둔다. 주어진 요구사항은, n을 만들 수 있는 방법 중 b - a가 가장 큰 값을 출력해야 하므로, 가장 작은 소수 2, 즉 primeNumber[st = 0]부터 시작하면서 n - primeNumber[st]가 소수인지 판단한다. primeNumber[st]가 소수이고 .. 2021. 3. 16.
반응형

티스토리툴바