728x90 반응형 최대공약수2 [algorithm] 백준 - 숨바꼭질 6 이 문제는 유클리드 호제법으로 푸는 문제이다. 모든 동생을 찾기 위한 D의 값을 정하기 위해 최대 공약수를 구하는 문제이다. 동생의 위치에서 수빈이의 위치를 빼고 절댓값을 씌운 후 그 값들을 유클리드 함수에 집어 넣어 최대 공약수를 구한다. //숨바꼭질 6 #include #include using namespace std; int uclid(int a, int b){ while(a % b != 0){ int temp = b; b = a % b; a = temp; } return b; } int main(void){ int n, s, num, gcd; vector sisterVector; cin >> n >> s; for(int i = 0; i > num; sisterVect.. 2020. 11. 4. [algorithm] 최대 공배수, 최소 공배수 수학 최대공약수 두 수 이상의 여러 수의 공통인 약수(공약수) 중 가장 큰 수 최소 공배수 두 수 이상의 여러 수의 공통인 배수(공배수) 중 가장 작은 수 최대 공약수 & 최소 공배수 구하는 법 모든 수가 서로수로 나눠질 때까지 나눈다. 나누었던 수를 곱하면 최대 공약수이다. 최소 공배수는 최대 공약수 * 서로수이다. 유클리드 알고리즘 두 자연수 a, b가 주어졌다. 가장 큰 값을 a, 다른 값 b, a와 b를 나눈 나머지를 n이라 했을 때, n이 0일 경우 -> b는 최소 공배수가 된다. 그러지 않을 경우 -> a에 b값을 대입하고, b에 n의 값을 대입한다. n이 0이 될 때까지 위를 반복한다. 만일 자연수가 n개일 때, 첫번째 값과 두번째 값을 대입한 uclid 호출하여 gcd를 구한 후, 이어서 .. 2020. 10. 27. 이전 1 다음 728x90 반응형
