이번학기부터 학교에서 알고리즘 수업을 들으면서, 배운 알고리즘에 대해 공부해볼려고 한다!
(절대 영어 수업이라 못알아들어서 다시 정리하는게.. 아니다...)

최대공약수

최대공약수란?

최대공약수 (Greatest Common Divisor, GCD)는 두 개 이상의 정수의 공통 약수중에서 가장 큰 값을 의미한다.
문제에 주어진 두 자연수의 최대공약수를 찾으려면 아래 단계를 거쳐야 한다고 한다.

1. 두수의 약수 중에서
2. 공통된 것을 찾아
3. 그 값 중 최댓값인 것을 찾아야 한다.

위 내용 중 '약수', '공', '최대'라는 단어를 역순으로 읽으면 '최대공약수'라는 단어가 만들어진다.

1. 최대공약수 알고리즘

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

1. 두 수 중 더 작은 값을 i에 저장한다.
2. i가 두 수의 공통된 약수인지 확인한다.
3. 공통된 약수이면 이 값을 결괏값으로 돌려주고 종료한다.
4. 공통된 약수가 아니면 i를 1만큼 감소시키고 2번으로 돌아가 반복한다.
   (1은 모든 정수의 약수이므로 i가 1이 되면 1을 결괏값으로 돌려주고 종료한다.)

# 최대 공약수 구하기
# 입력: a, b
# 출력: a와 b의 최대공약수

def gcd(a, b):
	i = min(a, b) # min: 두 수 중에서 최솟값을 구하는 파이썬 함수
    while True:
    	if a % i == 0 and b % i == 0:
        	return i
           i = i - 1 # i를 1만큼 감소시킨다.

print(gcd(1,5)) #1
print(gcd(4, 28)) # 4 

2. 유클리드 알고리즘

유클리드 아저씨가 발견한 최대공약수의 성질을 이용하는 또 다른 알고리즘에 대해 알아보자!
유클리드는 다음과 같은 성질이 있다는 것을 발견했다.

• a와 b의 최대공약수는 'b'와 'a를 b로 나눈 나머지'의 최대공약수와 같다. 즉, gcd(a, b) = gcd(b, a % b)이다.
• 어떤 수와 0의 최대공약수는 자기 자신이다. 즉, gcd(n, 0) = n 이다.

두 가지 예시를 통해 알아보자!
gcd(60, 24) = gcd(24, 60 % 24) = gcd(24, 12) = gcd(12, 24 % 12) = gcd(12, 0) = 12
gcd(81, 27) = gcd(27, 81 % 27) = gcd(27, 0) = 27

위 예시를 살펴보면 어떤 두 수의 최대공약수를 구하기 위해 다시 다른 두 수의 최대공약수를 구하고 있는 것을 알 수 있다.
이것이 바로 '재귀 호출'로 이 문제를 풀 수 있다는 힌트다!!

이 문제는 a와 b의 최대공약수를 구하기 위해 (a, b)보다 좀 더 작은 숫자인 (b, a % b) 의 최대 공약수를 구하는 과정을 이용하는 전형적인 재귀 호출 문제이다. (좀 더 작은 값으로 자기 자신을 호출한다.)

그렇다면 재귀 호출이 무한히 반복되지 않도록 하는 데 필요한 조건은 무엇일까?
바로 '어떤 수와 0의 최대공약수는 자기 자신' 이라는 성질이다!
이 성질로 인해 종료조건이 만들어지며, b가 0이면 재귀 호출을 멈추고 결과를 반환하게 된다.

# 최대공약수 구하기
# 입력: a, b
# 출력: a와 b의 최대공약수

def gcd(a, b):
	if b == 0: # 종료 조건
    	return a
    return gcd(b, a % b) # 좀 더 작은 값으로 자기 자신을 호출

print(gcd(1, 5)) # 1
print(gcd(4, 28)) # 4

오늘은 최대공약수와 관련된 문제를 조금 더 풀어봐야겠다!