다음은 유클리드 알고리즘(euclidean algorithm)을 사용하… | [7급 국가직 자료구조론] 23년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 23년 1회차
다음은 유클리드 알고리즘(euclidean algorithm)을 사용하여 두 정수의 최대공약수(greatest common divisor)를 구하는 파이썬 프로그램이다. gcd(12, 21)를 실행한 후 count 값과 (가)에 들어갈 내용을 바르게 연결한 것은?def gcd(m, n):count (가)
global count
count = count + 1
if m < n:
temp = m
m = n
n = temp
if m % n == 0:
return n
else:
return gcd( (가) )
count = 0
gcd(12, 21)
1
2 m, m % n
2
2 n, n % m
3
3 m, n % m
4
3 n, m % n
해설
count 값은 3이고, (가)에는 n, m % n이 들어간다.
유클리드 알고리즘은 gcd(m, n) = gcd(n, m mod n)이며 나머지가 0이 되면 n이 최대공약수다. 호출을 추적하면 다음과 같다.
- gcd(12, 21): count=1, m < n이라 교환해 m=21, n=12 → 21 % 12 = 9 → gcd(12, 9)
- gcd(12, 9): count=2 → 12 % 9 = 3 → gcd(9, 3)
- gcd(9, 3): count=3 → 9 % 3 = 0 → 3 반환
- count가 2인 조합: 실제 호출은 세 차례 일어나므로 맞지 않는다.
- m, n % m: 교환 뒤 n < m이므로 n % m = n이 되어 gcd(21, 12)가 끝없이 반복된다.
오류나 개정된 내용이 보이면 알려주세요