Greatest Common Divisor

Q: 유클리드 알고리즘의 시간 복잡도는 얼마인가요?

이 알고리즘은 O(log(min(a, b))) 단계로 실행됩니다. 두 단계마다 적어도 큰 수가 절반으로 줄어들기 때문입니다. 최악의 경우는 연속된 피보나치 수의 쌍입니다. 10^9 이하의 수에서는 최대 43단계이며, 알고리즘은 추가 공간을 O(1) 만큼 사용합니다.

Q: gcd(a, b)는 왜 gcd(b, a % b)와 같을까요?

a = q × b + r 이고 r = a % b 라고 쓰세요. a 와 b 를 나누는 수는 a - q × b 도 나누며, 이는 r 입니다. b 와 r 을 나누는 수는 q × b + r 도 나누며, 이는 a 입니다. 두 쌍은 공약수가 같으므로 최대공약수도 같습니다.

입문수학과 시뮬레이션

+10

양의 정수 a와 b가 주어집니다. 두 수를 모두 나머지 없이 나누는 가장 큰 정수인 최대공약수를 반환하세요.

예를 들어, 8과 12를 모두 나누는 수는 1, 2, 4이므로 답은 4입니다.

함수

gcd(a: integer, b: integer) → integer

ainteger: 첫 번째 양의 정수
binteger: 두 번째 양의 정수
반환값integer: a와 b를 모두 나누는 가장 큰 정수

제약 조건

1 ≤ a ≤ 10⁹
1 ≤ b ≤ 10⁹

예제

입력: a = 12b = 18
출력: 6
설명: 12의 약수는 1, 2, 3, 4, 6, 12이고, 18의 약수는 1, 2, 3, 6, 9, 18입니다. 두 목록에서 가장 큰 수는 6입니다.

입력: a = 17b = 5
출력: 1
설명: 17과 5는 모두 소수이고 서로 다르므로, 두 수가 공통으로 가지는 유일한 약수는 1입니다.

입력: a = 42b = 42
출력: 42
설명: 어떤 수는 자기 자신을 나누며, 42보다 큰 수는 42를 나눌 수 없으므로 42와 42의 최대공약수는 42입니다.

후속 질문

유클리드 알고리즘을 확장하여 a × x + b × y = gcd(a, b)를 만족하는 정수 x와 y도 반환할 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

정의에 따르면 후보를 하나씩 시도해 볼 수 있으며, 작은 수에서는 이 방법이 효과적입니다. 하지만 a와 b가 최대 10^9라면, 공통 인수가 없는 두 큰 수는 10억 번의 시도를 하게 만듭니다. gcd(a, b)가 gcd(b, a % b)와 같다는 유클리드의 관찰은 수를 매우 빠르게 줄여 주므로, 10^9 이하의 어떤 두 수 쌍도 43단계를 넘길 필요가 없습니다.

더 작은 숫자부터 거꾸로 세기

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

어떤 공약수도 두 수 중 더 작은 수보다 클 수 없습니다. b의 약수는 최대 b이기 때문입니다. 따라서 후보 d를 min(a, b)로 시작하고 두 수 모두를 나눌 때까지 1씩 줄여 나갑니다. 후보를 큰 값부터 확인하므로, 조건을 만족하는 첫 번째 수가 최대 공약수입니다.

12와 18의 경우 12(18을 나누지 못함)를 시도한 다음, 실패하는 11, 10, 9, 8, 7을 차례로 시도하고 6에서 멈춥니다. 1은 모든 수를 나누므로 반복문은 항상 끝납니다.

비용은 후보의 개수입니다. 두 소수인 999999937과 999999929의 답은 1이며, 반복문은 거의 10^9번 실행됩니다. 이는 가장 큰 테스트에는 너무 느립니다.

알고리즘

a와 b 중 더 작은 값으로 d를 설정합니다.
a % d 또는 b % d가 0이 아닐 동안 d에서 1을 뺍니다.
d를 반환합니다.

def gcd(a, b):
    d = min(a, b)
    while a % d != 0 or b % d != 0:
        d -= 1
    return d

유클리드 알고리즘

핵심 아이디어

r = a % b일 때 a = q × b + r라고 씁니다. a와 b를 모두 나누는 수는 r = a - q × b도 나눕니다. b와 r을 모두 나누는 수는 a = q × b + r도 나눕니다. 따라서 (a, b)와 (b, r) 쌍은 정확히 같은 공약수와 같은 최대공약수를 가집니다.

(a, b)를 (b, a % b)로 바꾸고 b가 0이 될 때까지 반복합니다. 모든 수는 0을 나누므로 gcd(a, 0) = a이며, a가 답입니다. 12와 18의 경우 (12, 18)은 (18, 12)가 되고, 이어서 (12, 6), 그다음 (6, 0)이 되며, 답은 6입니다. a가 더 작으면 첫 단계에서 자동으로 두 수가 바뀌므로, 정렬할 필요가 없습니다.

두 단계마다 큰 수는 적어도 절반으로 줄어드므로, 반복문은 O(log(min(a, b)))번 실행됩니다. 가장 느린 입력은 701408733과 433494437 같은 연속된 피보나치 수이며, 이 경우에도 42단계만 걸립니다.

알고리즘

b가 0이 아닌 동안 r = a % b를 계산합니다.
a = b와 b = r로 설정합니다.
b가 0이 되면 a를 반환합니다.

def gcd(a, b):
    # gcd(a, b) == gcd(b, a % b), and gcd(a, 0) == a.
    while b != 0:
        a, b = b, a % b
    return a

함정과 경계 사례

알고리즘은 짧으므로 버그는 업데이트 순서와 종료 조건에서 발생합니다.

잘못된 순서로 업데이트하기. a = b 다음에 b = a % b를 실행하면 b % b를 계산하게 됩니다. 이는 항상 0이므로 b를 반환합니다. 나머지를 먼저 임시 변수에 저장하거나 두 값을 한꺼번에 할당하세요.
루프가 끝날 때 a 대신 b를 반환하기. 이 시점에서 b는 0입니다.
카운트다운을 2에서 멈추거나 max(a, b)에서 시작하기. 전자는 17과 5처럼 서로소인 수의 쌍을 놓치고, 후자는 더 작은 수를 나눌 수 없는 후보를 검사하느라 시간을 낭비합니다.
나머지 연산 대신 반복해서 빼기를 사용하기. 그러면 gcd(10^9, 1)을 계산하는 데 10억 번 빼야 하지만, %는 이를 한 번에 처리합니다.

자주 묻는 질문3

유클리드 알고리즘의 시간 복잡도는 얼마인가요?

이 알고리즘은 O(log(min(a, b))) 단계로 실행됩니다. 두 단계마다 적어도 큰 수가 절반으로 줄어들기 때문입니다. 최악의 경우는 연속된 피보나치 수의 쌍입니다. 10^9 이하의 수에서는 최대 43단계이며, 알고리즘은 추가 공간을 O(1)만큼 사용합니다.

gcd(a, b)는 왜 gcd(b, a % b)와 같을까요?

a = q × b + r이고 r = a % b라고 쓰세요. a와 b를 나누는 수는 a - q × b도 나누며, 이는 r입니다. b와 r을 나누는 수는 q × b + r도 나누며, 이는 a입니다. 두 쌍은 공약수가 같으므로 최대공약수도 같습니다.

GCD와 LCM의 차이는 무엇인가요?

최대공약수는 두 입력값을 모두 나누는 가장 큰 수이고, 최소공배수는 두 입력값으로 모두 나누어떨어지는 가장 작은 수입니다. 두 값은 gcd(a, b) × lcm(a, b) = a × b라는 관계가 있으므로, 최대공약수를 구하면 최소공배수는 a / gcd(a, b) × b입니다.

def gcd(a, b):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

a = 12
b = 18

예상 출력