:: ADVANCE ::

BAEKJOON ONLINE JUDGE 1676 팩토리얼 0의 개수 https://www.acmicpc.net/problem/1676 이 문제는 팩토리얼 계산 결과값에서 0의 개수를 찾는 것이 아니다. 팩토리얼이 결국 곱으로 이루어진 연산이기 때문에 그리고 0은 10을 얼마나 곱하느냐에 따라 결정이 되기 때문에 팩토리얼을 이루는 수의 소인수 중에서 2와 5의 개수에 따라 결정이 된다. 정리를 하면 N! = 1 x 2 x 3 x ... x N ex) 10! = 3628800 10! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 10! = 1 x 2 x 3 x (2 x 2) x 5 x (2 x 3) x 7 x (2 x 2 x 2) x (3 x 3) x (2 x 5) 10! = 2^..

BAEKJOON ONLINE JUDGE 11635 소인수분해 https://www.acmicpc.net/problem/11653 소인수 분해라고 해서 소수 여부를 판단할 필요는 없다.2부터 하여 나누어 떨어지는 가장 작은 값이 n이 가지고 있는 소인수이다.또한, n을 소인수 분해했을 때 나타날 수 있는 인수 중 가장 큰 값은 root(n)이다.따라서, 2부터 root(n)까지 반복문을 돌면서 n을 나눌 수 있으면, 나누고, 나눌 수 없을 때까지 계속한다. 123456789101112131415161718192021222324252627#include void factorize(int n){ int i; if (n

BAEKJOON ONLINE JUDGE 6588 골드바흐의 추측 https://www.acmicpc.net/problem/6588 123456789101112131415161718192021222324252627282930313233#include int prime[1000001]; void checkprime(){ int i, j; for (i = 2; i

BAEKJOON ONLINE JUDGE 9613 GCD 합 https://www.acmicpc.net/problem/9613 각 입력의 조합을 만들어서 gcd를 구하여 합하면 되는 문제 1234567891011121314151617181920212223242526272829303132333435363738#include int gcd(int n, int m){ if (m == 0) return n; return gcd(m, n % m);} int main(){ int t; int n; int i, j; long long int sum; int num[101]; scanf("%d", &t); while (t--) { sum = 0; scanf("%d", &n); for (i = 0; i

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(){..

[Algorithm][math] 소수, 에라토스테네스의 체 소수 (prime)약수가 1과 자기 자신 밖에 없는 수 (1은 소수가 아니다) n이 소수가 되려면, 2보다 크거나 같고, n - 1보다 작거나 같은 자연수로 나누어 떨어지면 안된다. 1234567891011bool isprime(int n){ int i; if(n 소수가 아닌경우 이미 앞에서 배수를 돌면서 i의 배수 또한 0이 되기 때문에 배수를 탐색할 필요가 없다. * i가 배열의 범위나 자료형의 범위를 넘지 않도록 주의한다. 123456789101112131415int prime[1001]; void checkprime(){ int i, j; for (i = 2; i

[수학][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가 양수이면 결과도 ..

[Greedy] Greedy Algorithm (그리디, 탐욕 알고리즘) 정의 : 미리 정한 기준에 따라서 매번 가장 좋은 답, 최선의 답을 선택하는 알고리즘 최적화 문제를 푸는 데 사용한다.단계 단계 별로 가장 최적인 해를 구한다.효율적이긴 하나 반드시 전체의 최적의 해를 구해준다는 보장은 없다. 1. 해 선택 (Selection Procedure) : 지금 가장 최적인 해를 구하여 부분해 집합에 추가한다.2. 적절성 검사 (Feasibility Check) : 새로운 부분해 집합이 적절한지 검사한다.3. 해 검사 (Solution Check) : 새로운 부분해 집합이 문제의 해가 되는지 검사한다. 그렇지 않을 경우 1번부터 반복한다. 탐욕 알고리즘의 대표적인 예로, 최소의 동전 수로 거스름돈 주기 문..

BAEKJOON ONLINE JUDGE 2823번 유턴 싫어 https://www.acmicpc.net/problem/2823 123456789101112131415161718192021222324252627282930313233343536#include int main(){ int i, j; char map[11][11]; int r, c; int cnt; scanf("%d %d\n", &r, &c); for (i = 0; i