최대공약수
숨바꼭질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..
최대공약수/ 최소공배수_ 백준 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..