15강 최대공약수(Python Algorithm 15 GCD)

15강 최대공약수(Python Algorithm 15 GCD)

 

부제 : 알고리즘을 배우면서 파이썬 기초부터 RPG까지 정복

내용 : 초중고 또는 코딩 기초 입문자를 위한 누구나 따라 배울 수 있는 Python Algorithm 프로그램 기초 강의

 

1. 파이썬 기초 입문자

2. 알고리즘 기초에서 수학 기초

3. 기초 코딩

4. Text RPG Project

 

[동영상강의]

https://youtu.be/gJQwu4Gx8ks

Python-Algorithm-15-최대공약수.pdf

0.10MB

오랫만에 파이썬을 공부해 보는군요.

감각을 잃어버릴까봐 매주에 한 개씩이라도 공부를 해야 할 것 같습니다.

훗날 자라미를 교육하기 위해서라도 RPG까지 기초 이론을 끝내야 할 것 같습니다.

알고리즘이라는 제목으로 강의를 하지만 실제로는 파이썬 기초 문법부터

다 가르치고 있으므로 처음 부터 따라해보세요.

 

중간 중간에 나오는 기초 문법에 해당하는 사항은 그 문법을 설명하고 지나갑니다.

 

 

최대공약수(Greatest Common Division:GCD)

 

 

4의 약수는 1, 2, 4 이고

 

12의 약수는 1, 2, 3, 4, 6, 12 입니다.

4 와 12의 공통된 약수는 1, 2, 4 가 되는데 이것들을 공약수라고 부르고

이 공약수 중 가장 큰 값을 최대공약수라고 하며 여기서는 4가 됩니다.

최대공약수 구하기

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

     4와 12 에서 4를 i 에 저장합니다.

    4와 12 중에서 작은 값을 최대공약수라고 생각하고 i 에 저장하는 것입니다.

• i 가 두 수의 공통된 약수인지 확인합니다.
• 4와 12는 둘다 i 로 나누어 떨어집니다.
• 공통된 약수이면 이 값을 결괏값으로 돌려주고 종료합니다.
• 4 가 최대공약수가 됩니다.

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

    4와 6 에서 4를 i 에 저장합니다.

    4와 6 중에서 작은 값을 최대공약수라고 생각하고 i 에 저장하는 것입니다.

• i 가 두 수의 공통된 약수인지 확인합니다.
• 4 는 i로 나누어 떨어지지만 6은 i 로 나누어 떨어지지 않습니다.
• 공통된 약수가 아니면 i를 1 만큼 감소시킵니다.
• i를 1만큼 감소시켜 i는 3이 됩니다.
• i 가 두 수의 공통된 약수인지 확인합니다.

     4 는 i로 나누어 떨어지지않고 6은 i 로 나누어 떨어집니다.

• 공통된 약수가 아니면 i를 1 만큼 감소시킵니다.

    i를 1만큼 감소시켜 i는 2가 됩니다.

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

      4 는 i로 나누어 떨어지고 6도 i 로 나누어 떨어집니다.

• 공통된 약수이면 이 값을 결괏값으로 돌려주고 종료합니다.
• 2 가 최대공약수가 됩니다.

만약 i 가 1이되면 1은 모든 두 수의 공통된 약수가 되므로 1 을 최대공약수로 해서

결괏값으로 돌려주면 됩니다.

3과 5의 공통된 약수는 1 뿐이므로 이 경우 i=1 이 되겠죠.

먼저 코딩을 해 봅시다.

그리고 결과를 보고 난 다음

while 문을 다음 강의에 진행하겠습니다.

 

그리고 최대공약수 구하는 다른 방법을 알아보도록 합시다.

 

gcd.py

 

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

def gcd(a, b): # 두 수 a, b를 받음

  i = min(a, b) # 두 수 중에서 최솟값 구함
  while True :  # while문은 조건문이 참인 동안에 
                # while문 아래에 속하는 문장들이 
                # 반복해서 수행됨
                # True 이므로 무한 반복
    if a % i == 0 and b % i == 0: # % 나머지구함
      return i  # i 값을 돌려 준 후 함수를 즉시 종료
    i -= 1 # i를 1만큼 감소

print(gcd(4, 12)) # 4
print(gcd(4, 6))  # 2
print(gcd(3, 5))  # 1
  

4
2
1