[GDG - 스터디] 유클리드 호제법 & GCD

유클리드 호제법을 이용하여 GCD를 구하는 방법

• [ ] 유클리드 알고리즘의 원리 ? → 두 수 a와 b가 있을 때, a와 b의 GCD는 b와 a를 b로 나눈 나머지의 GCD와 같다 !

GCD(a, b) = GCD(b, a % b) ex) **GCD(48, 18)**를 구하는 과정

(1)	48 ÷ 18 = 2 (나머지 12) → GCD(48, 18) = GCD(18, 12)
(2)	18 ÷ 12 = 1 (나머지 6) → GCD(18, 12) = GCD(12, 6)
(3)	12 ÷ 6 = 2 (나머지 0) → GCD(12, 6) = GCD(6, 0) = 6

유클리드 알고리즘의 단계

1. 큰 수(a)를 작은 수(b)로 나눈 나머지를 구한다.
2. 작은 수(b)와 나머지(a % b)를 가지고 다시 나눗셈을 반복한다.
3. 나머지가 0이 될 때까지 이 과정을 반복하며, 나머지가 0이 된 순간 a값이 최대공약수이다.

// 최대공약수(GCD)를 구하는 유클리드 알고리즘
public static int gcd(int a, int b) {
    // 나머지가 0일 때, b가 최대공약수
    if (b == 0) {
        return a;
    }
    // 재귀 호출: GCD(a, b) = GCD(b, a % b)
    return gcd(b, a % b);
}

<aside> 💡

참고자료

https://thin-azimuth-2a9.notion.site/N-cf-62e59f1f8755417daad24294dc6fa036?pvs=4

</aside>

문제: 최대공약수 (백준 1850)

문제 링크

 

---

알고리즘 [접근 방법]

• [ ] 유클리드 알고리즘을 이용하여 최대공약수를 구하면 된다.

---

풀이방법

1. 유클리드 알고리즘을 함수로 구현한다.
2. A와 B의 GCD는 GCD('A를 구성하고 있는 1의 개수', 'B를 구성하고 있는 1의 개수')개의 1로 구성된 값과 같다 ! ( ex: GCD(3, 6) = 3 → 3개의 1로 구성된 값 111 → A와 B의 GCD )

---

실패 코드

• [ ] long 타입은 최대 19자리의 숫자까지만 표현 가능하다는 것과 별개로, createNumberWithOnes 메서드에서 너무 긴 문자열을 생성하다보니 메모리가 초과하게 됐다 !

import java.util.*;
import java.io.*;

public class Main {
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long aCount = Long.parseLong(st.nextToken());
        long bCount = Long.parseLong(st.nextToken());
        
        long A = createNumberWithOnes(aCount);
        long B = createNumberWithOnes(bCount);
        
        System.out.print(GCD(A,B));
    }
    
    // 1로 이루어진 자연수를 생성
    public static Long createNumberWithOnes(long count) {
        StringBuilder sb = new StringBuilder();
        for (long i = 0; i < count; i++) {
            sb.append("1");
        }
        return Long.parseLong(sb.toString());
    }
    
    public static long GCD(long n1, long n2) {
        
        if (n2 == 0) return n1;
        return GCD(n2, n1 % n2);
    }   
}

---

해결 코드

import java.util.*;
import java.io.*;

public class Main {
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long aCount = Long.parseLong(st.nextToken());  // A를 구성하고 있는 1의 개수
        long bCount = Long.parseLong(st.nextToken());  // B를 구성하고 있는 1의 개수
        
        // 1의 개수에 대한 GCD 계산
        long gcdCount = GCD(aCount, bCount);
        
        // `gcdCount`개의 1로 이루어진 문자열 생성
        StringBuilder sb = new StringBuilder();
        for (long i = 0; i < gcdCount; i++) {
            sb.append("1");
        }
        System.out.print(sb.toString());
    }
    
    public static long GCD(long n1, long n2) {
        if (n2 == 0) return n1;
        return GCD(n2, n1 % n2);
    }   
}

---

정리

• [ ] 항상 입력값의 크기부터 확인하자 !
• [ ] 사실 이런 수식 관련된 문제가 코테에서 나올지는 모르겠지만, 최대공약수나 최소공배수를 구해야 하는 상황이 온다면 유용하게 쓰일 것 같다.

 

https://thin-azimuth-2a9.notion.site/GDG-GCD-13af4ee21c0080d5a08de6f717d59ed8?pvs=4

GDG 스터디 - 유클리드 호제법 & GCD | Notion