GCD

#1. 문제 #2. 풀이 1. 유클리드 호제법 [BOJ알고리즘, C++]#2609_최대 공약수와 최소 공배수, 유클리드 호제법 [BOJ 알고리즘, C++] #2609_최대 공약수와 최소 공배수, 유클리드 호제법 BOJ 알고리즘 문제 풀이, 2609_최대 공약수와 최소 공배수 유클리드 호제법 알고리즘을 통해 두 자연수의 최대 공약수와 최소 webddevys.tistory.com Details '유클리드 호제법'은 두 수 a와 b의 최대 공약수를 구하는 알고리즘입니다. 이 알고리즘은 두 정수 a와 b의 최대 공약수가 a와 b를 나눈 나머지 값을 이용하여 계속 나누는 과정을 반복하다가, 나머지가 0이 되어 나누어 떨어지는 수가 생기면 그 수가 두 수의 최대 공약수가 되는 점을 활용합니다. 2. 최대 공약수, ..

[BOJ 알고리즘, C++] #2609_최대 공약수와 최소 공배수, 유클리드 호제법 BOJ 알고리즘 문제 풀이, 2609_최대 공약수와 최소 공배수유클리드 호제법 알고리즘을 통해 두 자연수의 최대 공약수와 최소 공배수를 구하는 문제   문제 풀이 1. 유클리드 호제법A = 106, B = 161.C = A % B = 106 % 16 = 10A 유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나입니다.A와 B를 나눈 나머지 값을 R이라고 한다면, A와 B의 최대 공약수는 B와 R의 최대 공약수와 같습니다!이 성질을 이용하여, B(혹은 Determinant)를 이전의 나머지 값으로 나누는 작업을 반복합니다.최종적으로, 나머지 값이 0이 되었을 때, "마지막 B" 값이 A와 B의 최대 공약수..