GCD (3) 썸네일형 리스트형 BOJ 2981 : 검문 문제 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다. 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오. 풀이 아래 블로그를 참고하였다. https://velog.io/@ledcost/%EB%B0%B1%EC%A4%80-2981-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EA%B2%80%EB%AC%B8-%EA%B3%A8%EB%9.. BOJ 2609 : 최대공약수와 최소공배수 문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 풀이 앞의 약수에서 참고한 알고리즘인 '유클리드 호제법'을 조금만 참고하면 된다. 두 수의 최대 공약수는 두 수의 나머지를 계속 나눔으로써, 언젠가 나누어 떨어지는 수를 의미한다. 그리고 최소 공배수는 두 수의 최대 공약수로 구성된 최소의 수 이므로 x(a를 최대공약수로 나눈 수)*y(b를 최대공약수로 나눈 수)*GCD(a,b)로 귀결된다. 이는 두 수(a = x* GCD(a,b), b = y*GCD(a,b))로 구성 되어 있기 때문에 각각의 최소 공배수는 위와 같이 구성된다. 최대공약수(GCD : Greatest Common Divisor) 최소공배수(LCM : Least Common Multiple) impo.. BOJ 1037 : 약수 문제 양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오. 풀이 진짜 간단한 문제다. 하지만 나는 틀렸다. '유클리드 호제법'은 두 수들의 나누기를 통해서 그 나머지로 기존 수로 나누어서 나머지가 0이 될 때의 나머지 수가 최대 공약수인 방법이다. 여기서 모든 약수들 중에서 최소 약수와 최대 약수의 곱으로 기존 수를 구할 수 있다. https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 유클리드 호제법(-互除法, Euclid.. 이전 1 다음