프로그래밍 공부

일반적으로 정수 a, b의 최대공약수를 구한다고 하면 이런 방식으로 구할 수가 있다. // 일반 반복문으로 구현 int gcd(int x, int y){ int Max_Common = 0; for(int i = 1; i y ? y : x); i++){ // 최대공약수이니 작은 값까지만 조사 if(x % i == 0 && y % i == 0){ // 두 수를 i로 나눴을때 둘다 나머지가 0이면 공약수임 Max_Common = i; // 끝까지 반복하면서 최대공약수를 갱신 } } return Max_Common; } 하지만 이런 방식을 사용하면 시간 복잡도는 O(n)이며 보통 알고리즘 문제를 풀 때 시간초과 당하기 좋다. 하지만 유클리드 호제법을 사용해서 O(log n)만에 최대공약수, 최소 공배수를 구할 ..