최대공약수2

• 백준 알고리즘 2609번: 최대공약수와 최소공배수 문제 정보 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 핵심 유클리드 호제법을 이용한 최대공약수와 최소공배수를 구한다 유클리드 호제법에 대한 간단한 설명은 다음 게시물에서 확인할 수 있다 유클리드 호제법: 두 수의 최대공약수 구하기 유클리드 호제법이란? 두 개의 자연수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 방법 중 하나로, 고대 그리스 수학자인 유클리드가 제안한 알고리즘으로, 매우 간단하면서 효과적인 방법 dduneon.tistory.com 풀이 재귀호출을 사용한 풀이 from sys import stdin N, M = map(int,.. 알고리즘/Python 2023. 6. 19.

• 유클리드 호제법: 두 수의 최대공약수 구하기 유클리드 호제법이란? 두 개의 자연수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 방법 중 하나로, 고대 그리스 수학자인 유클리드가 제안한 알고리즘으로, 매우 간단하면서 효과적인 방법 원리? 자연수 a와 b가 있다고 하면, a를 b로 나눈 나머지를 구한다. 나머지를 r이라고 한다. 나머지 r이 0이라면, b는 a와 b의 최대공약수이다. 따라서 알고리즘을 종료하고 b를 결과로 출력한다. 만약 나머지 r이 0이 아니라면, b를 a로 대체하고, r을 b로 대체한다. 다시 말해서 GCD(a, b) = GCD(b, r) 인 것이다. 식으로 풀면, a = bq + r 일 때 GCD(a, b) = GCD(b, r)이다 예시? 48과 18의 최대공약수(GCD)를 구해보면, 1. 48 % .. 알고리즘/개념 2023. 6. 19.