목록최대공약수 (1)

개발자가 되고 싶은 개발자

[Algorithm] Euclidean Algorithm

유클리드 알고리즘에 대해 알아보고, 관련 문제를 해당 알고리즘으로 풀어보도록 하겠습니다. 유클리드 알고리즘, 유클리드 호제법(互除法)이란? 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다. 호제법에 대한 설명은 다음과 같습니다. 두 수가 서로 상대방을 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 호제법이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 이 뜻의 '호제' 라는 단어가 따로 있지는 않다. 다시, 유클리드 호제법 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질..
Dev/Algorithm 2021. 11. 7. 18:27
이전 Prev 1 Next 다음