문제출처] https://www.acmicpc.net/problem/3036 문제요약 톱니바퀴가 맞물려 돌아갈 때 회전 수 구하는 문제 풀이 첫 번째 링과 각 링의 최대 공약수를 구하여 각각 나누어 준 후 첫 번째 링을 최대 공약수로 나눈 몫은 분자로 나머지 링을 최대 공약수를 나눈 몫은 분모로 취하면 된다. 최대 공약수를 구하는 방법은 2609번 최대공약수와 최소공배수 문제의 유클리드 호제법을 이용하면된다. 2609번문제풀이 링크] https://zero-rabbit.tistory.com/53 소스코드는 Python 3으로 작성되었습니다. import sys input = sys.stdin.readline def gcd(a, b): # 무조건 a > b 유지 if a > b: pass else: a, ..

문제출처] https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 문제요약 최소공배수 구하기 풀이 2609번 최대공약수와 최소공배수 문제와 같이 유클리드 호제법을 이용하여 풀면 된다. 2609번문제풀이 링크] https://zero-rabbit.tistory.com/53 소스코드는 Python 3으로 작성되었습니다. import sys input = sys.stdin.readline def gcd(a, b): # 무조건 a > b ..

문제출처] https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제요약 최대공약수와 최소공배수를 구하는 문제 풀이 최대공약수와 최소공배수를 구하는 중학교 때 배운 방법은 소인수 분해를 통한 방법이다. 그러나 소인수 분해를 이용하여 알고리즘을 작성할 경우 성능이 떨어지므로 유클리드 호제법을 이용하였다. 유클리드 호제법은 유키피디어를 참고하였다. https://ko.wikipedia.org/wiki/유클리드_호제법 유클리드 호제법 - 위키백과, 우리 모두의 백과사전 유클리드 호제법(-互除法, Euclidean algo..

문제출처] https://www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 문제요약 1과 N을 제외한 약수가 주어지면 N을 구하기. 풀이 주어진 약수를 정렬하여 가장 작은 약수와 가장 큰 약수를 곱하면 N이 나온다. 소스코드는 Python 3으로 작성되었습니다. import sys input = sys.stdin.readline n = int(input()) numbers = list(map(int, input().split())) numbers.sor..