[백준] 2609번 - 최대공약수와 최소공배수

문제 링크 : https://www.acmicpc.net/problem/2609

 

 

문제 탐색하기

 

1) 문제 분석

• 두 개의 수가 한 줄에 입력
• 최대 공약수와 최소 공배수를 출력

 

 

코드 설계하기

1. 실행 구조

1) 입력값을 읽어서 공백을 기준으로 num1, num2으로 분리 

2) 두 수를 숫자로 변환 

3) 최대공약수, 최소공배수 함수 구현

4) 결과 출력

 

2. 고민이 되었던 부분

 

1) 최대공약수, 최소공배수에 대한 개념을 바로 잡았어야 했다. 

 

최대공약수(GCD)    

• 두 수를 나누어 떨어지게 하는 "가장 큰 수"    
• 예) 12, 18 → 공약수: 1, 2, 3, 6 → 최대공약수 = 6

최소공배수(LCM)    

• 두 수 모두의 배수 중에서 "가장 작은 수"    
• 예) 12, 18 → 공배수: 36, 72, 108 ... → 최소공배수 = 36

2) 기존 코드의 개선

(1) 최대 공약수 함수 : getGCD1

let getGCD1 = (num1, num2) => {
    if (num1 === 0) return num2;
    if (num2 === 0) return num1;

    let gcd = 1; // 공약수를 저장할 변수. 최소 1은 항상 공약수.

    // 두 수 중 작은 수까지만 확인
    for (let i = 2; i <= Math.min(num1, num2); i++) {
        // i가 num1, num2 모두를 나누어 떨어뜨릴 수 있다면
        if (num1 % i === 0 && num2 % i === 0) {
            gcd = i; // 공약수 갱신
        }
    }
    
    return gcd; // 마지막에 갱신된 값이 최대공약수
}

: 처음에 사용했던 방식은 '완전 탐색 방식'이었다. 두 수 중 더 작은 수까지 반복문을 돌면서 동시에 나누어 떨어지는 가장 큰 수를 찾는 방시식으로 구현했다. 이 방식의 구현은 직관적이고 이해하기 쉽지만, 두 수가 클 경우(예: 10^9) 성능이 떨어진다.

• 시간복잡도 : (O(min(n1, n2)))

 

(2) 최소 공배수 함수 : getLCM1

let getLCM1 = (num1, num2) => {
    if (num1 === 0 || num2 === 0) return 0;
    let lcm = 1; // 후보값을 1부터 시작
    
    // 무한 반복 → 조건을 만족하면 break
    while (true) {
        // lcm이 num1, num2 모두로 나누어 떨어질 때 (즉, 공배수일 때)
        if ((lcm % num1 === 0) && (lcm % num2 === 0)) {
            break; // 처음 발견된 순간이 최소공배수
        }
        lcm++; // 아니라면 1씩 증가시키며 탐색
    }
    return lcm;
}

: 최소 공배수 또한, '탐색형' 방식이었다. 이 방식은 단순히 1부터 시작해서 차례대로 값을 올려가며 “두 수로 동시에 나눠지는 수”를 찾는다. 이 방식의 구현은 작은 수일 때는 잘 동작하지만, 큰 수일 경우 너무 오래 걸린다.

• 시간복잡도 : O(num1 * num2)

 

3) 유클리드 호제법

: 유클리드 호제법(Euclidean Algorithm)은 두 수의 최대공약수(GCD)를 빠르게 구하는 방법이다.

 

• 두 수 a, b (a > b)에 대해
  GCD(a, b) = GCD(b, a % b)
• 나머지가 0이 될 때, 그때의 나누는 수가 바로 최대공약수

이 방법의 경우 시간복잡도가 O(log(min(a, b)))로서, 매우 빠르다.

 

또한, 최소 공배수의 경우, 두 수의 곱을 최대공약수로 나눈 값으로 볼 수 있기에, 최대공약수를 구하는 함수를 재사용하면 더욱 시간이 단축될 것이라 생각했다. 여기서 중요했던 점은 num1과 num2를 곱한 뒤에 최대공약수로 나누는 방식이 아닌, (num1 / gcd(num1, num2)) * num2 으로 순서를 바꾸어서, 오버플로우/정밀도 손실 완화하는 부분도 발견했다.

그 결과 시간이 무려 4분의 1로 줄어든 것을 발견할 수 있었다.

 

 

정답 코드

// 최대공약수(GCD) & 최소공배수(LCM) 구하기

// 입력 처리
const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

// 입력한 두 수
const [n1, n2] = input[0].split(" ").map(Number);

/*
    최대공약수(GCD)
    - 두 수를 나누어 떨어지게 하는 "가장 큰 수"
    - 예) 12, 18 → 공약수: 1, 2, 3, 6 → 최대공약수 = 6
*/

// 방법1 : 완전 탐색 방식
// - 두 수 중 더 작은 수까지 반복문을 돌면서 동시에 나누어 떨어지는 가장 큰 수를 찾는다.
// - 구현은 직관적이고 이해하기 쉽지만, 두 수가 클 경우(예: 10^9) 성능이 떨어진다.
// - 시간복잡도 : (O(min(n1, n2)))
let getGCD1 = (num1, num2) => {
    if (num1 === 0) return num2;
    if (num2 === 0) return num1;

    let gcd = 1; // 공약수를 저장할 변수. 최소 1은 항상 공약수.

    // 두 수 중 작은 수까지만 확인
    for (let i = 2; i <= Math.min(num1, num2); i++) {
        // i가 num1, num2 모두를 나누어 떨어뜨릴 수 있다면
        if (num1 % i === 0 && num2 % i === 0) {
            gcd = i; // 공약수 갱신
        }
    }
    
    return gcd; // 마지막에 갱신된 값이 최대공약수
}

// 방법2 : 유클리드 호제법(Euclidean Algorithm)
// - 원리: GCD(a, b) = GCD(b, a % b)
// - 즉, 두 수를 나눴을 때의 '나머지'를 이용해 점점 더 작은 문제로 줄여가다가, 나머지가 0이 되는 순간의 수가 최대공약수.
// - 시간복잡도: O(log(min(n1, n2))) → 매우 효율적.
let getGCD2 = (num1, num2) => {
    if (num1 === 0) return num2;
    if (num2 === 0) return num1;

    while (num2 !== 0) {
        let temp = num1 % num2; // 나머지를 구함
        num1 = num2;            // num2를 새로운 기준으로
        num2 = temp;            // 나머지를 다음 피제수로
    }
    return num1; // 나머지가 0일 때의 num1이 최대공약수
}

/*
    최소공배수(LCM)
    - 두 수 모두의 배수 중에서 "가장 작은 수"
    - 예) 12, 18 → 공배수: 36, 72, 108 ... → 최소공배수 = 36
*/

// 방법1 : 완전 탐색 방식
// - 1부터 시작해서 차례로 증가시키며, 두 수로 동시에 나눠지는 순간 멈춘다.
// - 구현이 직관적이지만, 최악의 경우 num1*num2까지 확인해야 해서 성능이 매우 떨어짐.
// - 시간복잡도 : O(num1 * num2) (비효율적)
let getLCM1 = (num1, num2) => {
    if (num1 === 0 || num2 === 0) return 0; // 0 포함 시 LCM은 0
    let lcm = 1; // 후보값을 1부터 시작
    
    // 무한 반복 → 조건을 만족하면 break
    while (true) {
        // lcm이 num1, num2 모두로 나누어 떨어질 때 (즉, 공배수일 때)
        if ((lcm % num1 === 0) && (lcm % num2 === 0)) {
            break; // 처음 발견된 순간이 최소공배수
        }
        lcm++; // 아니라면 1씩 증가시키며 탐색
    }
    return lcm;
}

// 방법2 : 최대공약수(GCD) 활용 공식
// - 성질: LCM(a,b) * GCD(a,b) = a * b
// - 따라서 LCM(a,b) = (a / GCD(a,b)) * b
// - 유클리드 호제법으로 GCD를 구한 후, 즉시 계산하므로 매우 효율적.
// - 시간복잡도 : O(log(min(n1, n2))) (실전용)
let getLCM2 = (num1, num2) => {
    if (num1 === 0 || num2 === 0) return 0; // 0 포함 시 LCM은 0
    
    const gcd = getGCD2(num1, num2);  // 최대공약수 구하기
    return (num1 / gcd) * num2;       // 곱하기 전에 나누어 overflow 방지
}
    

// 결과 출력
console.log(getGCD2(n1, n2)); // 최대공약수
console.log(getLCM2(n1, n2)); // 최소공배수

 

마무리하며

 

어제에 이어, 오늘도 백준 문제를 풀며 코딩테스트를 준비할 수 있어서 다행이라고 생각했다. 오늘 문제의 경우에는 어제보다 더 쉬운 문제에 속한다고 생각한다. 두 수를 입력 받고, 최대공약수와 최소공배수만 구해서 출력하면 됐기에 말이다. 하지만, 생각보다 쉬운 문제는 아니었다. 그냥 결과를 출력하는 것까지는 쉽겠지만, 이를 최적화하는 과정에 대해서 고민하는 것이 필요했고, 이 부분이 핵심이었다.

 

어제 문제를 풀고 난 뒤에는 AI나 search의 도움을 받지 않고 풀고자 결단했었지만, 오늘은 최대공약수와 최소공배수를 구하는 방법에 대해서 찾아보며 문제를 풀게 되면서 어제 내린 결단을 지키지 못한 순간도 있었다. 그래도 원리를 이해하고, 조금씩 조금씩 내 것으로 만드는 단계라고 생각한다. 꾸준히 풀다보면 점점 스스로의 힘을 키울 수 있지 않을까 싶기도 하다. 암튼 내일도 코테를 풀어보자!