본문 바로가기

분류 전체보기

 (248)
[C++] 백준 1676번 : 팩토리얼 0의 개수 (S3) #문제 www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net #풀이 & 학습한 내용 뒤에 0이 붙는 건 2와 5의 곱에 의해 나타난다. 그리고 2의 개수보다 5의 개수가 항상 적기 때문에 5의 개수만 세어주면 된다. 이때 처음에 간과한 것이 5로 나누어 떨어질 때 답에 1을 증가시켜준 것이다. 만약 25일 경우에는 5가 2개 들어있으므로 답에 2를 더해줘야 한다. #소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include #include using namespace std; int main(..
모듈로 연산 정리 덧셈과 곱셈 - (A + B) mod M = ( (A mod M) + (B mod M) ) mod M = ( (A mod M) + B ) mod M - (A x B) mod M = ( (A mod M) x (B mod M) ) mod M = ( (A mod M) x B ) mod M 뺄셈의 경우에는 mod연산 결과가 음수가 나올 수 있으므로 다음과 같이 해야한다. - (A - B) mod M = ( (A mod M) - (B mod M) + M ) mod M 나누기의 경우에는 성립하지 않는다.(Modular Inverse를 구해야 함)
[C++] 백준 6588번 : 골드바흐의 추측 (S1) #문제 www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net #풀이 & 학습한 내용 ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); 이 없으면 시간초과가 나는 문제이다. 그리고 문제를 풀 때는 supremo7.tistory.com/116에서 이용한 에라토스테네스의 체를 통해 해결한다. #소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16..
[C++] 백준 1929번 : 소수 구하기 (S2) #문제 www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net #풀이 & 학습한 내용 에라토스테네스의 체를 이용해야 하는 문제이다. supremo7.tistory.com/115에서 푼 것처럼 하나하나의 수가 소수인지 판정(시간복잡도 O(√n))한다면, 총 시간복잡도는 O(n√n)이 되고, 이때 worst case에서 1,000,000*1,000=1,000,000,000으로 1초(1억)인100,000,000을 넘으므로 불가능하다. 이때, 소스코드 10행에서처럼 i*i> b; for (int i = ..
[C++] 백준 1978번 : 소수 찾기 (S4) #문제 www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net #풀이 & 학습한 내용 어떤 수 N이 소수인지 판정하기 위해 2부터 N-1까지의 수에 대해 N이 나누어 떨어지는지 살펴본다. 만약, 하나라도 나누어 떨어지는 수가 있다면 N은 소수가 아니다. 이때, 2부터 루트 N까지의 수에 대해서만 관찰해도 됨을 기억하자. 즉, 아래 소스코드의 15행은 for (int i=2; i*i> N; int sum = 0; int num; while (N--) { cin >> num; bool isit = true; for (int i = 2; i
[C++] 백준 1934번 : 최소공배수 (S5) #문제 www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net #풀이 & 학습한 내용 유클리드 호제법으로 최대공약수(GCD)를 구하고 이를 통해 (a*b)/GCD로 최소공배수를 구해야하는 문제이다. supremo7.tistory.com/113에서 푼 방식으로 최소공배수(LCM)을 구하면 worst case에서 실행횟수가 약 1000*45000*45000로 약 2,000,000,000,000이다. 1억(1초)이 100,000,000이므로 불가능하다..
[C++] 백준 2609번 : 최대공약수와 최소공배수 (S5) #문제 www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net #풀이 & 학습한 내용 최대공약수는 1부터 두 수 중 작은 수(b)까지 for문으로 살피면서 두 수 모두에 나누어 떨어지면 GCD값을 갱신시켜준다. 최소공배수는 두 수 중 작은 수(b)부터 두 수의 곱(b*a)까지 for문으로 살피면서 두 수 모두에 의해 나누어 떨어지면 LCD값을 결정하고 for문을 탈출한다. cf) 최대공약수는 유클리드 호제법을 통해서 구할 수도 있다. GCD(a, b)=GCD(b, a% b)를 이용하고, a% b가 0일 때 그때 b가 최대공약수이다...
[C++] 백준 2133번 : 타일 채우기 (S2) #문제 www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net #풀이 & 학습한 내용 이번문제에서 가로길이가 0일때의 경우의 수를 1로 설정해줘야한다. 그리고 가로길이가 홀수일때는 총 타일수가 홀수 개가 되므로 항상 경우의 수가 0이다. 마지막에 어떤 타일로 끝날 수 있는지 분석해야하는 과정이 쉽지 않다. 점화식을 세우고 base케이스를 채운 뒤 for문을 통해 dp배열을 채워나가 답을 구했다. #소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include #include using namesp..

티스토리툴바