목록Algorithm/math (16)
:: ADVANCE ::
BAEKJOON ONLINE JUDGE 1850 최대공약수 https://www.acmicpc.net/problem/1850 이 문제는 약간 함정이다.입력받은 A와 B로 1로만 만들어진 수를 만든 다음 최대공약수를 구하려 했는데 수가 너무 커서 결과를 구할 수 없었다.문제를 풀던 도중 규칙을 찾은 것이결국 1의 개수의 최대공약수가 결과 수의 1의 개수라는 것이었다. 따라서 A와 B의 GCD를 구한 후 이 수만큼의 1을 출력하면 되는 문제 123456789101112131415161718192021#include long long int gcd(long long int n, long long int m){ if (m == 0) return n; return gcd(m, n % m);} int main(){..
[수학][GCD LCM] 최대공약수와 최소공배수 최대공약수 (GCD, Greatest Common Measure) 두 자연수의 경우 약수를 구해보면 공통된 약수를 가지고 있다.이 중 가장 큰 약수를 최대공약수라 한다.최대공약수를 구하는 가장 단순한 방법은 2부터 min(A, B)까지 모든 정수로 나누어 보는 방법이 있다. 123456int g = 1;for(int i = 2; i
[수학][mod] % 나머지 연산자 나머지 연산% 또는 mod(모드) 연산자 라고 한다. 나머지 연산자는 나눗셈 연산 후 나머지를 구하는데 사용한다.나머지 연산의 특성상 결과값은 0 ~ (자신 - 1) 의 값이 나온다. 나머지 연산자의 분배 법칙을 보자.각각 나머지 연산을 취한 후 다시 전체적으로 나머지 연산을 한다. 일단, 나누기의 경우에는 성립하지 않는다. (Modular Inverse를 구해야 한다.) 뺄셈의 경우, 음수가 나올 수 있기 때문에 M을 더해준 후 다시 전체의 나머지 연산을 해주어야 한다. 이는 C 언어의 % 연산자에서 음수 처리는 다음과 같이 정의되어 있기 때문이다. X % Y를 연산할 때 그 연산 결과의 부호는 X의 부호를 따라간다.Y의 부호는 무시되며, 오직 X가 양수이면 결과도 ..
dovelet 3 단계 For 최대공약수, 최소공배수 / gcd_lcm http://59.23.113.171/30stair/gcd_lcm/gcd_lcm.php?pname=gcd_lcm 1234567891011121314151617181920212223242526272829303132333435363738394041#include int gcd(int n, int m){ int temp; while (n != m) { if (n > m) { temp = n; n = m; m = temp; } temp = n; n = m - n; m = temp; } return n;} int lcm(int n, int m){ int i = 1, temp = n; while (temp % m != 0) { temp = n ..
dovelet 29 단계 수학 술 취한 간수 / jailer http://59.23.113.171/30stair/jailer/jailer.php?pname=jailer 12345678910111213141516171819202122232425#include int main(void){ int n, i, j, cnt = 0; int check[110] = { 0, }; scanf("%d", &n); for (i = 1; i
dovelet 29 단계 수학 삼각형 만들기 / triangle1 http://59.23.113.171/30stair/triangle1/triangle1.php?pname=triangle1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include long long check[51000]; int main(void) { int n, cnt = 0; scanf("%d", &n); int a, b, c; for (a = 1; a