본문 바로가기

Algorithm/Math

 (11)
[C++] 백준 1373번 : 2진수 8진수 (B2) #문제 www.acmicpc.net/problem/1373 1373번: 2진수 8진수 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. www.acmicpc.net #풀이 & 학습한 내용 먼저 2진수인 수의 총 길이가 3의배수가 되지 않을때, 총 길이가 3의 배수가 되도록 앞에 0을 추가해준다. 그리고 3개씩 잘라서 2진수의 값을 10진수로 변환하여 순서대로 출력하면, 8진수로 변환된 결과가 나온다. 이때, char로 표현된 0~9를 int로 다루고 싶으면 '0'을 빼주면 된다는 점을 기억하자. #소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include #include #include using namespace std; in..
[C++] 백준 17087번 : 숨바꼭질 6 (S1) #문제 www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net #풀이 & 학습한 내용 동생들의 각각의 위치에서 수빈이의 위치를 뺀 값들의 최대공약수(GCD)를 구하는 문제이다. 유클리드 호제법을 이용해 GCD를 구하고, GCD(a,b,c)=GCD(GCD(a,b),c)임을 통해 순차적으로 계산한다. #소스코드 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 26 27..
[C++] 백준 9613번 : GCD 합 (S3) #문제 www.acmicpc.net/problem/9613 9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 b인 경우로 인자를 전달해줘야 한다고 생각했는데 상관없었다. 만약 a> T; while (T--) { ans = 0; cin >> N; for (int i = 1; i > arr[i]; } for (int i = 1; i
[C++] 백준 2004번 : 조합 0의 개수 (S2) #문제 www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 n, m (0 ≤ m ≤ n ≤ 2,000,000,000, n ≠ 0)이 들어온다. www.acmicpc.net #풀이 & 학습한 내용 supremo7.tistory.com/119에서는 2의 개수보다 5의 개수가 항상 적어서 5의 개수만 세어줬지만, 조합의 경우에는 2의 개수가 5의 개수보다 많을 수 있으므로 모두 세어주고 둘 중 최솟값을 답으로 출력해야 한다. #소스코드 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 26 27 28 29 30 31 32 33 34 35 36 37 #include #include using name..
[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 = ..

티스토리툴바