[알고리즘] 유클리드 호제법 (Euclidean algorithm), 약수, 배수

유클리드 호제법 (Euclidean algorithm)

• 두 개의 수가 있을 때, 최대공약수를 구하는 알고리즘
• 소인수분해를 하면 효율적이지 않고, 두 수가 크면 시간 복잡도는 계속 증가하므로 유클리드 호제법 알고리즘을 사용하면 문제를 쉽게 해결 가능함

GCD(a, b) = GCD(b, r)

r : a mod b (a에서 b를 나눈 나머지)
조건: 0 ≤ r < b), a ≥ b 

• a, b 를 서로 나눌 때, r=0 이 되면 그 때 b가 최대공약수
• 나머지가 0이 되는 시점까지 계속해서 동일한 연산을 진행해야 하는데 몇번을 통해서 가능한지 알 수 없기 때문에 재귀형태로 구현해야 함

최대공약수 GCD

• Great Common Divisor: 가장 큰 공통된 약수

1. 반복문

int GCD(int a, int b) {
	while(b != 0) {
    	int r = a % b;
        a = b;
        b = r;
    }  
    return a;
}

2. 재귀함수

int GCD(int a, int b) {
	if(a % b == 0) {
    	return b;
    }
    return GCD(b, a % b);
}

• a(큰 숫자)를 b(작은 숫자)로 나눈 값이 0이면 b 리턴, 아니면 재귀 형태로 자신을 호출 (파라미터는 b, 나머지)
• 시간 복잡도 0
• 코드가 간겨랗고 구현이 간단

예를 들어, GCD(48, 18)
48을 18로 나눈 나머지는 12. 따라서 GCD(48, 18)은 GCD(18, 12)로 변경.
18을 12로 나눈 나머지는 6. 따라서 GCD(18, 12)은 GCD(12, 6).
12를 6으로 나눈 나머지는 0. 따라서 GCD(12, 6)은 6이므로, 최종적으로 GCD(48, 18)은 6.

최소공배수 LCM

• Least Common Multiple: 공통된 배수 중 가장 작은 수

int LCM(int a, int b) {
	return a * b / GCD(a, b);
}

• a, b의 최대공약수가 GCD일 때,
  a = A * GCD, b = B * GCD (A, B는 서로소)
  L = A * B * GCD 이므로 a * b = L * GCD

---

문제

분수의 덧셈

• https://school.programmers.co.kr/learn/courses/30/lessons/120808

프로그래머스

최대공약수와 최소공배수

• https://school.programmers.co.kr/learn/courses/30/lessons/12940

프로그래머스

N개의 최소공배수

• https://school.programmers.co.kr/learn/courses/30/lessons/12953

---

약수

약수의 합

public int solution(int n) {
    int answer = 0;
    for(int i = 1; i <= n/2; i++) {
      if(n%i == 0)
        answer+=i;
    }
   return answer + n;
}

• 모든 양의 약수는 해당 숫자(n)의 절반보다 크지 않음
• 더 큰 수에서는 이미 이전에 찾은 약수와 대칭 관계에 있으므로 중복 계산을 피할 수 있음

약수의 개수 - 홀수, 짝수

//제곱수인지 확인
i % Math.sqrt(i) == 0

//제곱수인 경우 약수의 개수가 홀수
//제곱수가 아닌 경우 약수의 개수가 짝수

• 제곱수인지 확인 후, 제곱수인 경우 약수의 개수가 홀수 아니면 짝수

약수의 개수 - 비효율, 효율

private static int findDivisor(int a) {
        int count = 0;
        for(int i = 1; i <= a; i++){
			if(a % i == 0){
               count++;
            }
        }
    return count;
}

• 숫자가 커질수록 효율이 낮음

private static int findDivisor(int a) {
        int count = 0;
        for(int i = 1; i*i <= a; i++){
            if(i * i == a) count++;
            else if(a % i == 0){
               count += 2;
            }
        }
	return count;
}

• 모든 약수는 쌍으로 존재하는데 제곱근인 약수는 자신과 쌍을 이루지 않음 (ex) 36일 경우 6, 6)
• 약수는 제곱근 기준으로 양쪽에 대칭적으로 분포하므로 조건을 i * i <= a로 주어 반만 확인
• 제곱수인 경우 쌍이 아닌 단독 약수이므로 count++
• 제곱수가 아닌 경우 쌍이므로 count += 2