アルゴリズム#アルゴリズム#
450 ワード
1.ユークリッド湖製法
A.定義
O(N)からO(logN)に減少させることができる.ex) 85와 51의 최대 공약수를 유클리드 호제법을 사용하여 구해보자.
X % Y = R이라고 했을 때, X,Y의 최대 공약수는 Y와 R의 최대 공약수와 같다는 특징을 기억하자. 나머지 R이 0이 될 때까지 Y와 R의 나머지 연산을 반복한다.
85 % 51 = 34
51 % 34 = 17
34 % 17 = 0
이때, Y 값의 자리에 있는 17이 최대 공약수가 된다.Reference
この問題について(アルゴリズム#アルゴリズム#), 我々は、より多くの情報をここで見つけました https://velog.io/@du0928/알고리즘テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol