백준 문제풀이
GCD 합 _ 백준 9613
GCD, 즉 최대공약수의 합을 출력하는 문제이다. 해당 문제에서는, 테케의 수, 각 테케에서의 숫자 갯수, 테케 내의 숫자 입력 이렇게 세가지로 크게 입력을 나눌 수 있다. 입력을 받은 뒤에는 최대공약수를 다 더하면 되는데, 이는 함수를 통해서 간단히 구현할 수 있다. 최대 공약수 관련 문제는 아래에 정리해놓은게 있으니, 그쪽을 보고 오면 좋을 것 같다. 2020/05/16 - [백준 문제풀이] - 최대공약수/ 최소공배수_ 백준 2609번/1934번 사실 gcd 함수만 알면 그렇게 어려운 문제는 아닌 것 같다. #include #include using namespace std; int nums[100]; int gcd(int a, int b) { if (b == 0) return a; else retu..
팩토리얼 0 의 개수 _ 백준 1676
이번 문제는 팩토리얼과 관련된 문제이다. 팩토리얼은 기본적으로 큰 수이기 때문에, 일일히 확인하는 방식은 옳지 않다. 맨 처음으로 생각한건 10으로 나눴을때 나머지가 0인걸 생각했는데, 10은 2와 5의 곱셈으로 이루어지고, 2의 배수보다는 5의 배수가 더 적으니 5의 배수인 것의 수를 세서 0의 개수를 확인할 수 있을 것 같다고 생각했다. 그래서 5의 배수 , 25의 배수, 125의 배수일때 수를 세는 것으로 알고리즘을 짰다. (125까지인 이유는 입력이 500 이하의 값이기 때문에!) #include #include using namespace std; int main(void) { int a; int result = 0; scanf("%d", &a); for (int i = 2; i
골드바흐의 추측 _ 백준 6588
이번에는 소수와 관련되어서, 조금 더 심화된 내용인 골드바흐의 추측과 관련된 문제입니다. 골드바흐의 추측은 문제에 나온대로, "4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다." 를 중심으로 이루어지는데요, 앞서서 풀었던 문제인 소수 찾기, 구하기의 알고리즘이 다시 활용됩니다. - 해당 코드는 아래 링크에. 2020/05/16 - [백준 문제풀이] - 소수 찾기 / 소수 구하기 _ 백준 1978,1929 소수 찾기 / 소수 구하기 _ 백준 1978,1929 1978번, 1929번 문제는 소수와 관련된 문제이다. 어떤 수 N이 소수가 아니라면, N = a * b 라고 표현할 수 있는데, 이떄 a와 b의 차이가 가장 적은 경우는 √n 이다. 그러므로, 검사를 n까지만 해서, 소수 runa-na..
소수 찾기 / 소수 구하기 _ 백준 1978,1929
1978번, 1929번 문제는 소수와 관련된 문제이다. 어떤 수 N이 소수가 아니라면, N = a * b 라고 표현할 수 있는데, 이떄 a와 b의 차이가 가장 적은 경우는 √n 이다. 그러므로, 검사를 n까지만 해서, 소수를 찾을 수 있다. 이러한 소수의 특징을 이용하면, 아래와 같은 함수를 만들 수 있다. (true = 소수 false = 소수아님) bool prime(int n) { if (n < 2) return false; for (int i = 2; i * i
최대공약수/ 최소공배수_ 백준 2609번/1934번
지금은 코드플러스에서 기초 알고리즘 강의를 구매해서, 관련 문제를 푸는 중인데 백준 2609번이랑 1934번이 비슷한 문제인거 같아서 한번에 정리해보려고 한다. 먼저, 최대공약수의 경우에는 유클리드 호제법을 이용하는 방법을 사용하는 것이 좋다. 여기서 유클리드 호제법이란, a를 b로 나눈 나머지를 r이라고 했을 때, GCD(a,b) = GCD(b,r)인 것을 활용하여, r의 값이 0이 되면 그때의 b의 값이 최대 공약수라는 것을 활용한다. 최소공배수의 경우에는 위에서 구한 최대공약수를 활용하여 구할 수 있다. 최소공배수는 두수의 공통된 배수 중 가장 작은 정수이기 때문에, 두수 a, b의 최대공약수가 g라고했을 때 최소공배수 = g * (a/g) * (b/g)가 된다. 2609번 #include #inc..