백준
2xn 타일링 _ 백준 11726, 백준 11727
11726번 문제와 11727문제는 하나의 조건만 달라서 한번에 정리해보려고 한다. 11726 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 2×n 타일의 우측에 칸을 채워넣는 방식으로 생각하면, 방법은 두가지이다. 1×2가 들어가게 되면 한칸이 완전히 차게 되고, 2 X n-1이 남는다. → d[n-1] 2 X 1 이 들어가게 되면 두칸이 차게되고, 2 X n-2가 남는다 → d[n-2] DP문제이니만큼, 점화식을 세워보면, 2 x n 크기의 타일을 채우는 방법의 수를 d[n]이라고 하면 d[n] = d[n-1] + d[n-2]이 되는 것이다. 여기서 조금 헤맨 부분을 이야기하자면, 그냥 이렇게 세워서 문제를 풀다보니 계속 답이 틀렸다고 하는 문제가 ..
골드바흐 파티션_ 백준 17103
골드바흐 파티션은 이전에 풀었던 골드바흐의 추측과 관련된 문제입니다. 2020/05/17 - [백준 문제풀이] - 골드바흐의 추측 _ 백준 6588 골드바흐의 추측은 2보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 라는 추측이다. 이번 문제는 이 골드바흐의 추측을 기반으로 짝수 N을 두 소수의 합으로 나타내는 골드바흐 파티션을 구하는 문제이다. 여기서 두 소수의 순서만 다른 것은, 같은 파티션으로 취급한다. 에라토스테네스의 체를 활용하여 소수를 먼저 확인해놓고, 그 뒤에 결과값을 출력하는 형식으로 알고리즘을 짜면 된다. 골드바흐 파티션을 계산할 때, '두 소수의 순서만 다른 것은, 같은 파티션으로 취급한다.'라는 조건에 따라 해당 값을 반으로 나눈 값까지만 세면 된다. 코드는 다음과 같다..
숨바꼭질6 _ 백준 17087
동생 N명과 숨바꼭질을 하면서, 한번에 X만큼 움직일 수 있다고 할때, 한번에 움직이기 위한 값을 구하는 문제이다. 이번 문제에서 중요한 것은 GCD이다. 즉, 최대공약수를 구해야 한다는 것. 왜 최대공약수가 필요하냐면 한번에 이동할 수 있는 위치값을 찾아서, 동생들의 위치에 모두 도달해야 하기 때문이다. 즉, 수빈이의 위치 - 동생의 위치의 절댓값들의 최대공약수를 찾으면 되는 문제이다. GCD함수를 구현하고, 문제를 해석하면 어렵지 않은 문제이다. 나는 배열을 사용하긴 했는데, 지금 풀고 나니까 굳이 배열이 없이도 풀 수 있는 문제인 것 같다. #include #include using namespace std; int nums[100000]; int GCD(int a, int b) { if (b ==..
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..