코테 - 최대공약수(GCD) 찾기 5가지 방법

최대공약수(GCD)는 두 숫자의 공통된 약수 중 가장 큰 값입니다. 아래는 C 언어를 사용해 두 숫자의 GCD를 찾는 5가지 방법으로, 코딩 테스트 준비에 유용합니다.

방법 1: 유클리드 알고리즘 (반복)

유클리드 알고리즘을 반복문으로 구현하여 두 숫자를 나눈 나머지를 이용해 GCD를 계산합니다.

#include <stdio.h>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int a = 48, b = 18;
    printf("GCD(%d, %d) = %d\n", a, b, gcd(a, b));
    return 0;
}
        

방법 2: 유클리드 알고리즘 (재귀)

유클리드 알고리즘을 재귀적으로 구현하여 간결하게 GCD를 계산합니다.

#include <stdio.h>

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

int main() {
    int a = 48, b = 18;
    printf("GCD(%d, %d) = %d\n", a, b, gcd(a, b));
    return 0;
}
        

방법 3: 반복문을 통한 약수 나열

두 숫자의 약수를 나열하고 공통 약수 중 가장 큰 값을 찾습니다.

#include <stdio.h>

int gcd(int a, int b) {
    int min = a < b ? a : b;
    int result = 1;
    for (int i = 1; i <= min; i++) {
        if (a % i == 0 && b % i == 0) {
            result = i;
        }
    }
    return result;
}

int main() {
    int a = 48, b = 18;
    printf("GCD(%d, %d) = %d\n", a, b, gcd(a, b));
    return 0;
}
        

방법 4: 소인수분해

두 숫자의 소인수분해를 통해 공통 소인수를 곱하여 GCD를 계산합니다.

#include <stdio.h>

int gcd(int a, int b) {
    int result = 1;
    int min = a < b ? a : b;
    for (int i = 2; i <= min; i++) {
        while (a % i == 0 && b % i == 0) {
            result *= i;
            a /= i;
            b /= i;
        }
    }
    return result;
}

int main() {
    int a = 48, b = 18;
    printf("GCD(%d, %d) = %d\n", a, b, gcd(a, b));
    return 0;
}
        

방법 5: 이진 GCD 알고리즘

이진 GCD 알고리즘(슈타인 알고리즘)을 사용하여 비트 연산과 나눗셈으로 GCD를 계산합니다.

#include <stdio.h>

int gcd(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;
    int shift = 0;
    while (((a | b) & 1) == 0) {
        a >>= 1;
        b >>= 1;
        shift++;
    }
    while ((a & 1) == 0) a >>= 1;
    while (b != 0) {
        while ((b & 1) == 0) b >>= 1;
        if (a > b) {
            int temp = a;
            a = b;
            b = temp;
        }
        b -= a;
    }
    return a << shift;
}

int main() {
    int a = 48, b = 18;
    printf("GCD(%d, %d) = %d\n", a, b, gcd(a, b));
    return 0;
}
        

각 방법은 시간 복잡도와 코드 단순성 측면에서 장단점이 있습니다. 유클리드 알고리즘(방법 1, 2)은 효율적이고 간단하며, 이진 GCD(방법 5)는 비트 연산을 활용해 특정 상황에서 더 빠를 수 있습니다. 코딩 테스트에서는 유클리드 알고리즘이 가장 일반적입니다.

설명

• 방법 1: 유클리드 알고리즘 (반복): 가장 효율적이고 간단한 방법으로, 나눗셈의 나머지를 반복적으로 계산. 시간 복잡도 O(log min(a,b)).
• 방법 2: 유클리드 알고리즘 (재귀): 반복문 대신 재귀 호출로 구현. 코드가 간결하지만 스택 오버플로우 가능성 주의.
• 방법 3: 반복문을 통한 약수 나열: 직관적이지만 비효율적(O(min(a,b))). 소규모 입력에 적합.
• 방법 4: 소인수분해: 공통 소인수를 곱해 GCD를 계산. 구현이 복잡하고 효율이 낮음(O(min(a,b))).
• 방법 5: 이진 GCD 알고리즘: 비트 연산과 뺄셈을 사용해 나눗셈 연산을 줄임. 큰 숫자에서 유리할 수 있음.

각 코드 예시는 a=48, b=18일 때 출력 예시: GCD(48, 18) = 6을 생성합니다. 코딩 테스트에서 요구되는 정확성과 효율성을 고려하여 작성되었습니다.