[ALGORITHMS]문제 05. 최대 공약수 구하기

문제 05

최대 공약수 구하기

두 자연수 a와 b의 최대공약수를 구하는 알고리즘을 만들어보세요

최대공약수는 두 개 이상의 정수의 공통 약수 중에서 가장 큰 값을 의미합니다.

문제로 주어진 두 자연수의 최대 공약수를 찾으려면 두수의 약수 중에서 공통 된 것을 찾아 그 값중 최댓값인것을 찾아야 합나다

1. 최대 공약수 알고리즘

최대 공약수 성질을 떠올리면서 다음 알고리즘을 생각해 봅시다.

1. 두 수 중 더 작은 값을 i에 저장합니다

2. i가 두 수의 공통 된 약수인지 확인합니다.

3. 공통된 약수이면 이 값을 결괏값으로 돌려주고 종료합니다.

4. 공통된 약수가 아니면 i를 1만큼 감소시키고 2번으로 돌아가 반복합니다

(1은 모든 정수의 약수이므로 i가 1이 되면 1을 결괏값으로 돌려주고 종료합니다.

예를 들어 4와 6의 최대 공약수를 찾으려면 다음과 같은 과정을 거칩니다.

1. i에 4를 저장합니다

2. 4는 i로 나누어 떨어지지만 6은 나누어 떨어지지 않습니다.

3. i를 1만큼 감소시켜 3으로 만듭니다.

4. 4는 i로 나누어떨어지지 않습니다.

5. i를 1만큼 감소시켜 2로 만듭니다

6. 4도 i로 나누어 떨어지고 6도 i로 나누어떨어지므로 i 값 2가 최대 공약수입니다.

* 최대 공약수를 구하는 알고리즘

2. 유클리드 알고리즘

위에 사진으로 첨부한 알고리즘은 최대 공약수의 정의에 충실할 뿐만 아니라 직관적인 최대공약수 알고리즘입니다. 

이번에는 유클리드가 발견한 최대공약수의 성질을 이용하는 다른 알고리즘을 살펴보겠습니다.

유클리드는 최대 공약수에 다음과 같은 성질이 있다는 것을 발견하였습니다

 - a와 b의 최대 공약수는 'b'와 'a를 b로 나눈 나머지'의 최대공약수와 같습니다

 즉 gcd(a,b) = gcd(b, a%b)

 - 어떤 수와 0의 최대 공약수는 자기 자신입니다. 즉 gcd(n,0) = n입니다

ex)

gcd(81,27) = gcd(27,81%27) = gcd(27,0) = 27 

풀이 과정을 유심히 살펴보면 어던 두 수 의 최대공약수를 구하기 위해 

다시 다른 두수의 최대공약수를 구하고 있는 것을 알 수 있습니다.

이것이 바로 재귀호출로 이 문제를 풀 수 있다는 힌트입니다.

* 유클리드 방식을 이용해 최대 공약수를 구하는 알고리즘

* 분석하기

gcd(60,24)

-> gcd(24,12)

-> gcd(12,0)

->12

->12

->12

*연습문제

5-1 0과 1부터 시작해서 바로 앞의 두 수를 더한 값을 다음 값으로 추가하는 방식으로 만든 수열을 피보나치 수열이라고 합니다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...

피보나치 수열이 파이썬의 리스트처럼 0번부터 시작한다고 가정할 떄

n번째 피보나치 수를 구하는 알고리즘을 재귀 호출을 이용해서 구현해 보세요

읽어주셔서 감사합니다.