[Python] 여러 수의 최소공배수와 최대공약수를 구하는 프로그램

 

이게 무슨 제목만 봐도 끔찍한 프로그램이람?

최대공약수랑 최소공배수를 짜는 알고리즘을 구현해보자.

사실 구현해도 숫자가 커질수록, 항의 수가 많아질수록

계산시간이 기하급수적으로 길어질 것이라는 것이 빤히 예상되지만

일단 이론적으로 구멍이 없는 프로그램을 구현해 보도록 하자.

 

우선 첫 번째로 입력값을 받아주자.

숫자를 세 개 이상 입력하고 그 값을 리스트로 처리하면 되겠지?

 

vals = [] 
while True: insert_val = input('GCD, LCM과 공약수를 찾을 수를 세 개 이상 입력하세요') 
      if insert_val == 'start': 
          if len(vals) < 3: 
              print('3개 이상의 값을 넣어주세요.') 
              continue 
          print('입력이 완료되었습니다. {}의 최소공배수, 최대공약수, 공약수를 구합니다.'.format(vals)) 
          break 
      else: 
      	try: 
          vals.append(int(insert_val))
          print('저장되었습니다.') 
        except: 
        print('정수 값을 입력하세요.')

 

이렇게 처리해주면 되겠다.

While loop를 돌며 정수값만 받아서 리스트에 저장하고,

start를 입력하면 while문을 깨고 다음 명령으로 넘어가면 될 것 같다.

이제 알고리즘이 문젠데... 무엇을 가장 먼저 구해야 할까?

 

우선 최대공약수는 공약수 중에서 제일 큰 것만 고르면 될 것 같고

최소공배수는 인수분해를 할 수 있으면 편하겠는데.. 하다가

 

최대공약수 * 모든 항을 최대공약수로 나눈 수의 공약수

라고 놓고 풀어보기로 했다.

 

A = aG B= bG일 때

LCM = abG이고, GCD=G이지만

이는 항이 두 개일때나 이렇게 간단하고, 두 개가 넘어가면 굉장히 복잡해진다.

항이 세 개인 경우만 예로 들어봐도 12,15,18에서

최대공약수는 3, 최소공배수는 180이다. 4*5*6*최대공약수 3 을 해도 값이 다르다.

 

대신 모든 수를 최대공약수로 나누고 그 수들의 공배수를 구해 곱한다면 된다.

 

그래서 항의 개수가 정해져있지 않을 때의 수들은 다 같이 구하던가, 하나 구하고 다음거와 구하고 식으로 넓혀야 되는데

아무리 생각해도 1번과 2번의 것을 먼저 구하고 2번과 3번을 비교하고 하는 방법은

항의 개수가 정해져 있지 않을 때에는 성립시킬 수가 없었다.

혹시 아시는 분 있다면... 댓글좀..

 

해서 나는 공약수를 1부터 가장 큰 수까지 일일히 대입시켜가며

모든 항에 대하여 나눠보고 나머지가 0인 것만 구할 것이다!

최대공약수는 그 중에 제일 큰 것이고, 최소공배수는 아까처럼 수/최대공약수의 최소공배수를 구해 곱하면 된다!

무슨 텅 트위스터도 아니고.. 말장난같네..

 

그럼 공약수-최대공약수-최소공배수 순으로 구하면 될 것 같다.

 

우선 공약수의 범위는 1부터 가장 큰 항까지 하면 된다.

그 수로 다 나눠보고, 리스트에 넣을건데

여기서도 문제가 발생.

처음에 집합을 써서 처리하려 했는데 항의 개수가 정해져 있지 않아서

순서가 꼬이면 공약수가 아닌 것까지 들어가버렸다.

 

예를 들어서 (2,6,10)의 공약수를 구한다고 하면

CD = set([])
val = [2, 6, 10]
for i in range(1,11): 
	for val in vals: 
    	if val%i==0: 
        	CD.add(i) #값이 딱 떨어지면 공약수로 인정 
        else: if i in CD: 
        	CD.remove(i) #하나의 value라도 떨어지지 않으면 공약수에서 삭제 else: pass

 

 

이런 식으로 짰는데 이 알고리즘에 따르면 10도 공약수에 포함된다.

완전히 삽질해버렸구만~

 

그래서 고민에 고민을 거듭해서 상당히 무식하지만

리스트를 두 개 만들어서 하나에 다 때려놓고,

입력한 값과 개수가 같은 수들만 공약수로 인정하는 방법을 썼다.

 

greatest = max(vals)
CD_try = [] 
CD = [] 
print('공약수를 모두 구합니다.') 
for i in range(1,greatest+1): 
	for val in vals: 
		if val%i == 0: 
        	CD_try.append(i) 
        else: 
        	pass 
        
        if CD_try.count(i) == len(vals): CD.append(i)

 

이렇게.

수가 커지면 같이 커질 계산시간이 두려웠지만 묘수가 생각나지 않았다...

그래도 지나치게 크지 않은 수에는 공약수가 금방 잘 나오는 것을 확인할 수 있었다.

 

최대공약수야 GCD = max(CD) 를 해주면 되는거고.

 

최소공배수는

GCD = max(CD) for val in vals: LCM = GCD LCM *= (val/GCD) #수를 최대공약수로 나눈 인수들을 다 곱하기 * 마지막에 최대공약수 곱하기 LCM = factor_LCM * GCD

 

이렇게 구해줬다.

수들을 최대공약수로 나누고, 나머지들끼리 다 곱해주고(인자들 다 곱하기)

마지막에 최대공약수를 곱해준다.

 

아우 헷갈려;

 

최종 코드는

def LCM_GCD_CD() : 
    vals = [] 
    while True: 
        insert_val = input('GCD, LCM과 공약수를 찾을 수를 세 개 이상 입력하세요') 
        if insert_val == 'start': 
            if len(vals) < 3: 
                print('3개 이상의 값을 넣어주세요.')
                continue 
            print('입력이 완료되었습니다. {}의 최소공배수, 최대공약수, 공약수를 구합니다.'.format(vals)) 
            break 
        else: 
            try:
                vals.append(int(insert_val))
                print('저장되었습니다.')
            except:
                print('정수 값을 입력하세요.')
            
    greatest = max(vals)
    CD_try = []
    CD = []
    print('공약수를 모두 구합니다.')
    for i in range(1,greatest+1):
        for val in vals:
            if val%i == 0:
                CD_try.append(i)
            else:
                pass
            if CD_try.count(i) == len(vals): CD.append(i)

    print('최대공약수를 구합니다.') 
    GCD = max(CD) 
    print('최대공약수를 구했습니다.') 
    print('최소공배수를 구합니다.')
    for val in vals: 
        LCM = GCD 
        LCM *= (val/GCD) #수를 최대공약수로 나눈 인수들을 다 곱하기 * 마지막에 최대공약수 곱하기 
    print('최대공약수 : {}'.format(GCD)) 
    print('최소공배수 : {}'.format(LCM)) 
    print('공약수 : {}'.format(CD)) 

LCM_GCD_CD()

 

이런 모양이 된다. 큰 수를 하면 계속 계산을 하긴 하는데, 공약수를 구할 때 1씩 쌓이므로 더럽게 오래 걸린다.

이 메커니즘을 손보고 싶은데...

 

---

그리고 하루가 지난 지금.. 난 답을 알게 되었고.. 이 실패작을 떠난다.. ㅋㅋㅋㅋㅋ

공약수-최대공약수-최소공배수 순서로 구하는 것도 맞았고, 최소공배수를 구하는 접근법까지 맞았지만

자료형의 선택과 우려했던 1씩 더하는 방법에 문제가 있었다.

 

n = list(map(int, input('3개 이상의 수를 입력하세요.').split(","))) 
d = {} 
for num in n: 
	s = set() #전체 약수
    for k in range(1,int(num**(1/2)) + 1):#몫과 나눈 수만 구하면 되므로, 최대인 제곱근까지만 반복하면 됨. 
    	if num % k == 0: 
        	d[k] = d.get(k,0) + 1 
            d[num//k] = d.get(num // k, 0) + 1 
            s.add(k) 
            s.add(num//k) 
        else: 
        	continue 
print(s)
elst = []
for key in list(d.keys()): 
	if d[key] == len(n): 
    	elst.append(key) 

print(elst)
a = max(elst) 
for num in n: 
	a *= int(num/max(elst)) 

print(max(elst)) print(a)

 

우선 코드의 길이가 짧아서 현타왔고, 계산도 압도적으로 빨라서 2차 현타..

지나치게 한 방법(1씩 누적)에 집착했나 싶기도 하고.

핑계라면 핑계지만 딕셔너리 자료형이랑 아직 안 친하다... ㅋㅋㅋㅋ 고하다 추현아

집합 자료형도 쓰려다가 못 썼는데, 아직 많이 미숙한게 느껴진다.

 

복기해보자.

오래 걸렸던 이유는 공약수와 최소공배수를 구할 때 각각의 값을 모두 리스트에 넣고 세는 것과

수를 구할 때 1씩 더했기 때문인데, 이걸 딕셔너리로 만들 생각을 했어야 된다.

 

실제로 리스트에 그 수를 계속 더하는 게 아닌, 딕셔너리로 만들어 키값에 따른 밸류를 더해주면 되는 거였다.

그러면 밸류가 항의 개수랑 같은 키만 고르면 되니까, 공약수를 구하는 과정이 훨씬 빨라지는 것.

 

뭔가 진 기분이다... 더 열심히 공부해봐야지.

(이런 일 있으면 딕셔너리 부수러 가는 편)