Python 유클리드 호제법 & 피보나치 수열 코드 분석

분석 대상 코드

def make_numbers(n, g): # 피보나치 생성 → 단계 n 보장 a, b = 1, 1 for _ in range(n): a, b = b, a + b # gcd 맞추기 위해 g 곱하기 return g * b, g * a def euclid_process(a, b): step = 0 print(f"\n[유클리드 호제법 과정 시작]") while b != 0: q = a // b r = a % b step += 1 print(f"{step}단계: {a} ÷ {b} = {q} … {r}") a, b = b, r print(f"\n최대공약수(GCD) = {a}") print(f"총 단계 수 = {step}") return a, step # ===== 실행 ===== n = int(input("단계 수 n 입력: ")) g = int(input("최대공약수 g 입력: ")) x, y = make_numbers(n, g) print(f"\n생성된 두 수: ({x}, {y})") gcd, steps = euclid_process(x, y) # 검증 print("\n[검증]") print("단계 수 일치:", steps == n) print("GCD 일치:", gcd == g)

코드의 목적: 원하는 유클리드 호제법의 '단계 수(n)'와 '최대공약수(g)'를 입력하면, 그 조건에 정확히 맞는 두 숫자(x, y)를 생성하고, 실제로 유클리드 호제법을 실행하여 결과가 일치하는지 검증하는 프로그램입니다.

[1] 상세 개념 5가지

1. 유클리드 호제법과 피보나치 수열의 관계 (라메의 정리)

이 코드의 가장 핵심적인 원리입니다. 유클리드 호제법을 사용할 때, 주어진 숫자 크기에 비해 가장 많은 계산 단계를 거치는 최악의 입력값은 바로 연속된 두 피보나치 수입니다. 예를 들어, `gcd(8, 5)`는 `gcd(5, 3)`, `gcd(3, 2)`, `gcd(2, 1)` 등 여러 단계를 거칩니다. 이 코드는 이 원리를 역으로 이용합니다. "n 단계가 걸리는 두 수를 만들고 싶으면, n+2번째와 n+1번째 피보나치 수를 사용하면 된다"는 아이디어에 기반합니다. `make_numbers` 함수가 바로 이 역할을 수행합니다.

2. 피보나치 수열 생성기

make_numbers 함수 내부의 `for` 루프는 피보나치 수열을 생성합니다. a, b = 1, 1로 시작하여 a, b = b, a + b를 반복합니다. 피보나치 수열을 F(1)=1, F(2)=1, F(3)=2, ... 라고 할 때,

따라서 이 루프는 정확히 n단계의 유클리드 호제법을 유발하는 두 기초 숫자 `F(n+2)`와 `F(n+1)`을 찾아냅니다.

3. 최대공약수(GCD)의 분배법칙 성질

최대공약수에는 gcd(g * a, g * b) = g * gcd(a, b) 라는 중요한 성질이 있습니다. 즉, 두 수에 같은 수를 곱하면, 그들의 최대공약수에도 똑같이 해당 수가 곱해집니다. 연속된 두 피보나치 수의 최대공약수는 항상 1입니다(gcd(F(n+2), F(n+1)) = 1). 여기에 위 성질을 적용하여, `make_numbers` 함수는 피보나치 수로 찾은 두 수에 우리가 원하는 최대공약수 `g`를 곱해줍니다. 그러면 `gcd(g*F(n+2), g*F(n+1))`은 `g * gcd(F(n+2), F(n+1)) = g * 1 = g`가 되어, 우리가 원하는 최대공약수 `g`를 갖는 두 수를 만들 수 있습니다.

4. 유클리드 호제법의 단계(Step) 계산

euclid_process 함수는 단순한 최대공약수 계산을 넘어, 나눗셈이 한 번 일어날 때마다 `step` 변수를 1씩 증가시킵니다. 이를 통해 '두 수를 나누고 나머지를 구하는' 핵심 과정이 총 몇 번 반복되었는지를 측정합니다. 이 `step` 값이 바로 우리가 처음에 입력했던 `n`과 일치하는지를 검증하는 데 사용됩니다.

5. 코드의 전체적인 설계 (생성자 → 실행자 → 검증자)

이 코드는 세 부분으로 명확히 나뉩니다.

  1. 생성자 (make_numbers): 주어진 조건(n, g)에 맞는 문제를 만들어냅니다.
  2. 실행자 (euclid_process): 만들어진 문제를 풉니다.
  3. 검증자 (main 블록): 문제의 조건과 풀이의 결과가 일치하는지 확인합니다.
이러한 구조는 특정 알고리즘의 성질을 테스트하거나, 알고리즘 교육용 예제를 만들 때 매우 효과적인 프로그래밍 패턴입니다.

[2] OX 퀴즈 5개

문제 1

make_numbers(0, 7)을 호출하면, 함수는 `(7, 7)`을 반환한다.

정답: O
상세 풀이: `n=0`이므로 `for` 루프는 한 번도 실행되지 않습니다. 초기값 `a=1, b=1`이 그대로 유지됩니다. 따라서 함수는 `g*b`, `g*a` 즉, `7*1`, `7*1`인 `(7, 7)`을 반환합니다.

문제 2

연속된 두 피보나치 수의 최대공약수는 항상 1이므로, 이들을 '서로소' 관계라고 한다.

정답: O
상세 풀이: 최대공약수가 1인 두 정수의 관계를 '서로소(coprime 또는 relatively prime)'라고 합니다. 연속된 두 피보나치 수는 항상 서로소 관계입니다.

문제 3

make_numbers(n, g)가 반환하는 두 수의 순서를 바꾸어 euclid_process에 넣어도 단계 수와 최대공약수는 동일하게 나온다.

정답: X
상세 풀이: 최대공약수(GCD)는 동일하게 나오지만, 단계 수는 달라질 수 있습니다. `euclid_process(a,b)`에서 `a < b`인 경우, 첫 단계에서 `a, b = b, a % b`가 실행되면서 두 수의 순서가 바뀌게 됩니다. 이 과정이 추가적인 단계로 계산될 수 있으므로, 보장된 단계 수 `n`이 나오지 않을 수 있습니다. `make_numbers`는 큰 수를 첫 번째로 반환하여 이 문제를 방지합니다.

문제 4

이 코드는 입력한 `n`과 `g` 값에 상관없이 항상 "단계 수 일치: True", "GCD 일치: True"를 출력한다.

정답: O
상세 풀이: 이 코드의 설계 자체가 라메의 정리와 GCD의 성질을 이용하여 `n` 단계와 GCD `g`를 만족하는 수를 '만들어'내고, 그것을 다시 '푸는' 방식이기 때문입니다. 수학적 원리가 정확하므로, 컴퓨터의 연산 오류가 없는 한 결과는 항상 일치하게 되어 있습니다.

문제 5

만약 make_numbers 함수에서 `return b*g, a*g` 대신 `return b, a`로 바꾸면, 최종적으로 검증되는 최대공약수는 항상 `g`가 된다.

정답: X
상세 풀이: `return b, a`로 바꾸면 `g`를 곱하는 과정이 생략됩니다. 생성되는 두 수는 연속된 피보나치 수이므로, 그들의 최대공약수는 항상 1이 됩니다. 따라서 검증 결과는 "GCD 일치: False"가 될 것입니다 (단, `g=1`을 입력한 경우는 제외).

[3] 5지선다형 문제 5개

문제 1. n=3, g=10을 입력했을 때, make_numbers 함수가 생성하는 두 수 (x, y)는 무엇인가?

정답: 2번
상세 풀이: `n=3`이므로 `for` 루프는 3번 실행됩니다. 루프 종료 후 `a=3, b=5`가 됩니다. 함수는 `g*b, g*a`를 반환하므로 `10*5, 10*3` 즉, `(50, 30)`을 반환합니다.

문제 2. 이 코드가 유클리드 호제법의 단계 수를 보장하기 위해 사용하는 핵심적인 수학적 대상은 무엇인가?

정답: 3번
상세 풀이: 유클리드 호제법의 최악의 경우(가장 많은 단계)가 연속된 두 피보나치 수를 입력했을 때 발생한다는 '라메의 정리'를 역으로 이용하여, 원하는 단계 수 `n`에 해당하는 피보나치 수를 생성하여 사용합니다.

문제 3. euclid_process(89, 55)를 실행했을 때, 반환되는 단계 수(step)는 얼마인가? (89와 55는 각각 11번째, 10번째 피보나치 수이다)

정답: 2번
상세 풀이: 코드는 `n` 단계에 대해 `F(n+2)`와 `F(n+1)`을 사용합니다. 문제에서 주어진 수는 `F(11)`과 `F(10)`입니다. 따라서 `n+2 = 11` 이라는 관계가 성립하므로, `n = 9`가 됩니다. 즉, 9단계가 소요됩니다.

문제 4. make_numbers 함수에서 g를 곱해주는 궁극적인 이유는 무엇인가?

정답: 3번
상세 풀이: `make_numbers`에서 `g`를 곱하지 않으면 생성되는 두 수는 연속된 피보나치 수이므로 최대공약수는 항상 1이 됩니다. 여기에 `g`를 곱함으로써 `gcd(g*a, g*b) = g * gcd(a,b) = g * 1 = g`라는 성질을 이용하여 최종 최대공약수가 입력받은 `g`와 일치하도록 만드는 것입니다.

문제 5. 만약 사용자가 `n=-1`을 입력하면 어떤 일이 발생하는가?

정답: 3번
상세 풀이: Python에서 `range()` 함수에 음수를 넣으면 (예: `range(-1)`), 아무런 숫자를 생성하지 않는 빈 시퀀스가 됩니다. 따라서 `for _ in range(-1)`은 `for _ in range(0)`과 동일하게 루프를 한 번도 실행하지 않습니다. 결과적으로 `a=1, b=1`이 되어 `(g, g)`가 생성되고, `euclid_process(g, g)`는 1단계만에 끝나므로, 최종 검증에서는 "단계 수 일치: False"가 출력될 것입니다.