최대 공약수 구하기 (1) 프로그램 예제2 : 최대 공약수 구하기 문제 해결 방법 구상 (아는 지식 정리) GCD1 알고리즘

Presentation on theme: "최대 공약수 구하기 (1) 프로그램 예제2 : 최대 공약수 구하기 문제 해결 방법 구상 (아는 지식 정리) GCD1 알고리즘"— Presentation transcript:

1 최대 공약수 구하기 (1) 프로그램 예제2 : 최대 공약수 구하기 문제 해결 방법 구상 (아는 지식 정리) GCD1 알고리즘
두 자연수 a, b (a >= b)의 최대 공약수를 구하라. 문제 해결 방법 구상 (아는 지식 정리) 최대 공약수는 두 수 a, b의 약수 중에서 제일 큰 수 (GCD1) 어떤 수 n의 약수는 그 수를 1부터 n까지로 나누었을 때, 나머지가 없는 수이다. 최대 공약수는 두 수를 소인수 분해하여 찾을 수 있다. 두 수가 공통적으로 나누어지는 소인수들을 전부 곱하면 최대 공약수이다. GCD1 알고리즘 a의 약수를 구한다. b의 약수를 구한다. a, b의 약수에 공통으로 들어있는 가장 큰 수를 구한다. 기초컴퓨터프로그래밍

2 최대 공약수 구하기 (2) a, b의 약수를 구하여 배열 ad[], bd[]에 저장하는 알고리즘
idx1 := 1; idx2 := 1; for i := 1 to a do for i := 1 to b do if (a mod i = 0) then if (b mod i = 0) then ad[idx1] := i; bd[idx2] := i; idx1 := idx1 + 1; idx2 := idx2 + 1; endif endif endfor endfor 두 약수 배열에 공통으로 들어 있는 가장 큰 수를 찾는 방법 큰 수부터 비교 (예: 36과 16의 최대 공약수) 1 2 3 4 6 9 12 18 36 // 36의 약수 // 16의 약수 1 2 4 8 16 기초컴퓨터프로그래밍

3 최대 공약수 구하기 (3) 약수 배열에서 공통의 가장 큰 수를 찾는 알고리즘
i := idx1 – // i를 ad 배열의 최대 첨자 값으로 초기화 j := idx2 – // j를 bd 배열의 최대 첨자 값으로 초기화 flag := false // flag는 수를 찾았을 때 true 값을 가지는 변수 while ((flag = flase) and (i >= 1) and (j >= 1)) do if (ad[i] > bd[j]) then i := i – 1 else if (ad[i] < bd[j]) then j := j – 1 else flag = true endwhile return (ad[i]) 기초컴퓨터프로그래밍

4 최대 공약수 구하기 (4) GCD1의 효율 개선 방법 소인수 분해를 이용하는 알고리즘 (GCD2)
두 수중 작은 수보다 큰 약수는 구할 필요 없음 약수를 구하기 위해 제곱근까지의 수로만 나누고, 나누어지는 수의 몫과 제수를 약수로 취함 기타 소수(prime number)를 구할 때 적용한 방법 등 이용 소인수 분해를 이용하는 알고리즘 (GCD2) 두 수중 작은 수의 약수를 구하고 그중 소수를 배열에 저장 : pn[] gcd := 1 for i := 1 to maximum_index_of_pn while ((a mod pn[i]) = 0) and (b mod pn[i] = 0) do gcd = gcd*pn[i]; a = a/pn[i]; b = b/pn[i]; endwhile endfor 기초컴퓨터프로그래밍

5 최대 공약수 구하기 (5) Euclid Algorithm : GCD3 Euclid Algorithm 적용 예
최대공약수를 구하는 효율적인 방법 a if b = 0 GCD(a, b) = GCD(b, a mod b) otherwise function GCD3(a, b) if (b = 0) then a else GCD3(b, a mod b) end Euclid Algorithm 적용 예 72와 20의 최대공약수 GCD3(72, 20) = GCD3(20, 12) = GCD3(12, 8) = GCD3(8, 4) = GCD3(4, 0) = 4 int gcd3(int a, int b) { if (b==0) return(a); else return(gcd3(b, a%b)); } 기초컴퓨터프로그래밍

6 최대 공약수 구하기 (6) 알고리즘 비교 72와 20을 입력으로 했을 경우의 mod 연산 및 기타 연산 알고리즘 GCD1
(약수 구하여 비교) GCD2 (소인수 분해 이용) GCD3 (Euclid Algorithm) mod 연산 회수 기타 연산 92 12 (비교 연산) 22 없음 4 기초컴퓨터프로그래밍