BOJ 26091

• [Algorithm] 유클리드 호제법을 Java로 구현해보자!! (with BOJ 2609) 안녕하세요 Coding-Knowjam입니다. 오늘은 유클리드 호제법에 대해서 알아보고 코드로 구현해보겠습니다. 그리고 추가적으로 백준 온라인 저지에 있는 BOJ 2609번 최대공약수 문제도 같이 풀어보겠습니다. 1. 유클리드 호제법이란? (Euclidean Algorithm) 1.1 개념 유클리드 호제법은 두 개의 수가 주어졌을 때, 최대공약수를 구하는 알고리즘입니다. 일반적으로 우리가 수학을 배울 때, 두 수 사이의 최대공약수는 소인수분해를 하고 소인수들의 곱으로 구할 수 있었습니다. 소인수분해를 물론 코드로 구현할 수는 있겠지만 효율적이지는 않을 겁니다. 왜냐하면 우선 소인수분해를 위해 소수를 먼저 찾아야 하고, 찾은 소수가 두 개의 수를 공통적으로 나눌 수 있는지를 확인을 해야 하기 때문입니다. 만.. Algorithm & Data Structure/이론 2021. 7. 21.