개발관련/알고리즘 (1) 썸네일형 리스트형 두 수의 최대 공약수 및 최소 공배수 구하기 (유클리드 호제법) 두 수의 최대 공약수를 구할때 여러 방법이 있다. 나는 두 수의 소인수 분해를 통해서 최대 공약수를 구했다. 최대 공약수 구한 방법 1. 각 수를 소인수 분해한다. 2. 소인수 분해한 것들 중 겹치는 찾는다. 3. 찾은 소인수를 다 곱한다. 그러나 그 과정을 구현하는데 오래걸렸다. 그래서 찾아본 결과 공약수를 구하는 알고리즘인 유클리드 호제법이란 것이 있었다. 유클리드 호제법이란? 두 수 a,b가 있을 때 a를 b로 나눈 나머지를 r이라고 하면 a와 b의 최대 공약수는 b와 r의 최대 공약수가 된다. ( 단 a > b ) 이 과정을 통해 a = bx + r로 만들고 b = rx' + r' / r = r'x'' + r'' 등으로 만든다. 이때 나머지가 0이되면 마지막으로 나눈 수가 a,b의 최대 공약수가 .. 이전 1 다음