초보자를 위한 C/C++ 연습

C와 C++로 최대공약수 구하기

이 레슨에서는 유클리드 호제법으로 두 정수의 최대공약수(GCD)를 구합니다.

  • 초급
  • 2분 분량
  • 실행 가능한 예제 2개

소개

어떤 문제를 해결하나요

분수를 약분할 때(48/18을 8/3으로), 같은 크기의 정사각형 타일로 바닥을 빈틈없이 깔 때, 주기적으로 반복되는 일정을 맞출 때는 모두 최대공약수가 필요합니다. 유클리드 호제법을 쓰면 몇 단계 만에 구할 수 있습니다.

일상 속 비유

유클리드 호제법은 직사각형 종이에서 가장 큰 정사각형을 잘라 내는 것과 같습니다. 짧은 변을 한 변으로 하는 정사각형을 잘라 내고, 남은 띠 모양 종이에 같은 일을 반복합니다. 남는 종이가 없어졌을 때 마지막으로 잘라 낸 정사각형의 한 변 길이가 답입니다.

종이 자르기에서 코드로
left = 48, right = 18📄 48 × 18 직사각형
left % right✂️ 정사각형을 잘라 내고 남은 부분
left = right; right = remainder;🔁 남은 띠에 같은 일을 반복
gcd=6⬛ 한 변이 6인 정사각형으로 딱 맞게 채워짐
나머지가 0이 될 때까지 두 수를 (작은 수, 나머지)로 바꿉니다.
한 문장으로

두 수의 최대공약수(GCD)는 두 수를 모두 나누어떨어지게 하는 가장 큰 수입니다. 유클리드 호제법은 두 수를 작은 수와 나머지로 바꾸는 일을 되풀이해서 최대공약수를 구합니다.

핵심 정리

  1. remainder = left % right는 나눗셈을 하고 남은 나머지입니다.
  2. 두 수는 (right, remainder)로 바뀝니다: (48, 18), (18, 12), (12, 6), (6, 0).
  3. right가 0이 되면 반복문이 끝납니다.
  4. 이때 left에 들어 있는 값 6이 최대공약수입니다.

사용하면 좋은 경우

  • 분수를 약분할 때.
  • 최소공배수를 구할 때: a / gcd(a, b) * b.
  • 정수론 연습 문제와 일정 맞추기 문제.

필요 없는 경우

  • C++17 코드: <numeric>의 std::gcd가 이미 이 일을 해 줍니다.
  • 음수 입력을 그대로 넣는 것: 먼저 절댓값으로 바꾸세요.

C와 C++ 코드 예제

C
실행 →
main.c
#include <stdio.h>
int main(void) {
    int left = 48, right = 18;
    // Reduce the pair until no remainder remains.
    while (right) { int remainder = left % right; left = right; right = remainder; }
    printf("gcd=%d\n", left);
}
이 예제의 실행 버튼 만들기 실행 결과
gcd=6
C++
실행 →
main.cpp
#include <iostream>
#include <numeric>
int main() {
    // std::gcd implements Euclid's algorithm.
    std::cout << "gcd=" << std::gcd(48, 18) << '\n';
}
이 예제의 실행 버튼 만들기 실행 결과
gcd=6

C와 C++ 비교

반복할 때마다 프로그램은 remainder = left % right를 계산한 뒤 left = right, right = remainder로 대입합니다. right가 0이 되면 left에 남은 값이 최대공약수입니다. 48과 18이면 결과는 gcd=6입니다.

C

C는 작은 절차형 함수를 쓰고, 데이터가 메모리에 어떻게 표현되는지 그대로 드러냅니다.

C++

C++는 여전히 저수준 작업을 할 수 있으면서, 라이브러리 타입과 더 안전한 추상화를 더합니다.

연습 문제

두 버전을 모두 실행한 다음 코드를 바꿔 보면서 각 언어가 주는 안전성의 차이를 살펴보세요.

  • 잘못된 입력과 경계값으로 테스트해 보세요.
  • -Wall -Wextra -Wpedantic 옵션으로 컴파일해 경고를 더 많이 켜 보세요.
  • 공통 선언은 헤더 파일에, 구현은 별도의 파일에 두어 보세요.

자주 하는 실수

잘못된 순서로 값을 바꿈

right를 따로 저장하기 전에 덮어쓰면 그 값을 잃어버립니다.

문제
right = left % right;
left = right;
수정
int remainder = left % right;
left = right;
right = remainder;

이 레슨을 마쳤나요?

학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.

챌린지로 연습하기

이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.

모든 챌린지