#070 · 수학쉬움수학 / 유클리드 호제법

두 수의 최대공약수

문제

자연수 두 개 a, b 가 주어집니다. 두 수의 최대공약수(GCD)를 반환하세요.

a=12,  b=18  → 6
a=15,  b=25  → 5
a=7,   b=13  → 1   (서로소)
a=100, b=10  → 10

시간 복잡도 목표: O(log min(a, b))

예시 1: gcd(12,18) = 6

입력: a = 12, b = 18

출력: 6

예시 2: gcd(15,25) = 5

입력: a = 15, b = 25

출력: 5

예시 3: 서로소 → 1

입력: a = 7, b = 13

출력: 1

예시 4: 한쪽이 다른쪽의 배수

입력: a = 100, b = 10

출력: 10

예시 5: 둘 다 1

입력: a = 1, b = 1

출력: 1

예시 6: gcd(24,36) = 12

입력: a = 24, b = 36

출력: 12

예시 7: 큰 입력, 인접 정수 → 1

입력: a = 1000000000, b = 999999999

출력: 1

solution.ts

에디터 로딩 중…

▶ 실행은 기록 없이 채점만, 제출은 결과가 진행률·오답노트에 기록됩니다.