[Python & SQL ] 최대 공약수 구하기

안녕하세요!

 

오늘은 최대공약수를 구하는 알고리즘을 알아보고

파이썬과 SQL을 활용해 구현해 보도록 하겠습니다!

 

 

### 최대 공약수(Gratest Common Divisor) ?

 

최대 공약수는 두 수(a,b) 중에서 공통 약수 중 최대값을 의미합니다.

약수에 대한 개념과 구하는 방법은 아래 링크에서 확인할 수 있습니다!

 

2020/12/28 - [알고리즘] - [Python & SQL] 약수 구하기

[Python & SQL] 약수 구하기

 

### 최대공약수(GCD) 구하는 방법

 

# 두 수가 같은경우

 

두 수가 같으면 당연히 자기 자신이 최대공약수가 됩니다.

 

# 두 수 중 작은 수를 범위로 지정하여 나눗셈 연산 

 

a , b 중 작은 수를 최종 범위로 합니다.

작은 수부터 1씩 감소하며 두 수를 나눗셈

가장 먼저 나눈 나머지가 0이 된 수가 최대공약수 입니다.

 

# 유클리드 호제법

 

2개의 자연수에서 최대공약수를 구하는 알고리즘

호제법 : 서로 상대 수를 나누어 결국 원하는 수를 얻는 알고리즘

 

" 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b),

a와 b의 최대공약수는 b와 r의 최대공약수와 같다 " 

 

위의 성질을 이용합니다.    

간단하게 아래와 같이 순서를 나누어 보았습니다.

 

1. 큰 수를 작은수로 나눈 후 나머지를 확인합니다.

     if 나머지 0 -> 작은수가 최대공약수

     else 나머지 0 x -> 작은수를 나머지로 나눕니다.

 

2. 다시 나머지 확인 

   if 나머지 0? -> 작은수(1번의 나머지)가 최대공약수

   else 나머지 0 x -> 1번 연산 다시 수행

 

---

 

### Python 최대공약수 구하기

 

1. 작은수 범위로 나눗셈 연산

num1=int(input('첫 번째 숫자를 입력하세요 : '))
num2=int(input('두 번째 숫자를 입력하세요 : '))

def get_GCD(num1,num2):
    for i in range(min(num1,num2),0,-1):
        if num1%i==0 and num2%i==0:
            return i
        
if max(num1,num2)%min(num1,num2)==0:
    
    print('최대 공약수는 %d입니다.'%min(num1,num2))
else:
    print('최대 공약수는 %d입니다.'%get_GCD(num1,num2))

유클리드 호제법을 사용하지 않은 코드입니다.

 

2. 유클리드 호제법

num1=int(input('첫 번째 숫자를 입력하세요 : '))
num2=int(input('두 번째 숫자를 입력하세요 : '))

def get_GCD(num1,num2):
    while num1%num2!=0:
        (num1,num2)=(num2,num1%num2)
    return num2
        
if max(num1,num2)%min(num1,num2)==0:
    print('최대 공약수는 %d입니다.'%min(num1,num2))
else:
    print('최대 공약수는 %d입니다.'%get_GCD(max(num1,num2),min(num1,num2)))

while 조건 " num1(큰수) 나누기 num2(작은수)가 0이 아님 "

즉, 해당 조건이 맞는 동안은 계속 연산을 수행

조건에 맞지 않다면(num1%num2==0) while문을 탈출합니다.

 

(num1,num2) = (num2,num1%2num2) 

 

연산 전 : 큰수 num1   작은수 num2

연산 후 : 큰수 num2   작은수 num1%num2

 

위 과정을 while문 안에서 계속 진행하는 것입니다.

 

### SQL 최대공약수 구하기

 

우선 두 수 중에서 작은 수로 나누어 나머지를 확인하는 연산을 진행합니다.

accept num1 prompt '첫번째 수 입력:'
accept num2 prompt '두번째 수 입력:'

select level n, mod(&&num1,level) n1 , mod(&&num2,level) n2
 from dual
 connect by level <=least(&&num1,&&num2)

20과 15를 입력한 결과

least 함수를 사용해 num1, num2 사용합니다.

 

n : 1 ~ 15 

n1 : mod(20, n)

n2 : mod(15, n)

 

즉 각각의 나머지들이 기록됩니다.

 

※ min을 사용하지 않는 이유 ?

 

min : 한 칼럼내에서 가장 작은 데이터를 반환합니다.

num1, num2 는 엄연히 다른 변수(칼럼)으로 생각해야 합니다.

 

따라서 least 함수를 사용해 서로 다른 칼럼을 비교하는 작업을 수행합니다.

gratest를 사용해 더 큰 변수를 찾을 수도 있습니다.

 

accept num1 prompt '첫번째 수 입력:'
accept num2 prompt '두번째 수 입력:'

select '최대공약수는 ' || max(n) || '입니다.' as "최대공약수"
  from(select level n, mod(&&num1,level) n1 , mod(&&num2,level) n2
        from dual
        connect by level <=least(&&num1,&&num2))
  where n1+n2 = 0;

 

위에서 만든 결과를 서브쿼리로 사용합니다.

나머지의 합이 0을 조건으로 사용합니다.

max 함수를 사용해 가장 큰 숫자를 찾아냅니다.

 

 

오늘은 파이썬과 SQL을 사용해서 최대 공약수를 구해 보았습니다.

다음 시간에는 최소 공배수를 구해보도록 하겠습니다!!

 

읽어주셔서 감사합니다.