본문 바로가기

Algorithm

 (130)
모듈로 연산 정리 덧셈과 곱셈 - (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..
[C++] 백준 17404번 : RGB거리 2 (G4) #문제 www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net #풀이 & 학습한 내용 supremo7.tistory.com/99에서 풀었던 RGB거리 문제의 응용문제이다. 기존문제에서 추가된 점은 첫번째 집과 마지막 집의 색 또한 같아선 안된다는 점이다. 집들이 원으로 둘러져서 있다고 생각하면 편하다. 이때, 첫번째 집의 색을 하나로 결정한 후, 각각에 대해 dynamic programming을 통해 최솟값들을 구하면 된다. 첫번째 집의..

티스토리툴바