[알고리즘] 백준 2609 최대공약수와 최소공배수 (+ 유클리드 호제법)

문제링크

• https://www.acmicpc.net/problem/2609

문제 설명

• 주어진 숫자의 최대공약수와 최소공백수 출력

주제

• 정수론 및 조합론

난이도

• 하

풀이 전 계획과 생각

• 2부터 9까지 for문을 와장창 돌려 %로 나머지를 구한 후 조건에 맞게 최대공약수와 최대공배수를 구해야징~ (은 실패)

풀이

num_list = list(map(int, input().split()))
# 1. 최대공약수 구하기 (유클리드 호제법 사용)
# 1_1. 큰 순자가 나머지 진행 시 앞에 올 수 있도록 오름차순으로 정렬
num_list.sort()

num1 = num_list[1]
num2 = num_list[0]
remainder = 1

# 1_2. 나머지가 0이 나올 때까지 while 문 진행
while remainder != 0:
    remainder = num1 % num2	
    num1 = num2
    num2 = remainder

# 1_3. num1 : 나머지가 0을 나누어지는 수
divisor = num1

# 2. 최대공배수 구하기
# 2_1. 앞서 구한 최대공약수와 주어진 숫자들을 나눠 곱한여 구한다.
multiple = divisor * (num_list[1]/divisor) * (num_list[0]/divisor)

# 3. 결과 출력 sep='\n'를 사용하여 여러줄로 결과 출력
print(int(divisor), int(multiple), sep='\n')

풀이하면서 고민했던 점

• 기존에 계획한 for문 이용한 나머지 구하기 제대로 동작은 했지만 코드가 너무 난잡하고 뭔가 더 효율적인 방법이 있으거라는 생각이 들었다.
• 그래서 혹시나 하는 마음에 최대공약수 알고리즘을 검색했고 다행히 위키피디아에서 발견할 수 있었다!

• 유클린드 알고리즘이란, 두개의 자연수의 최대 공약수를 구한다.
  1. 자연수 a와 b가 있다고 가정할 때 (단, a가 b보다 커야한다.)
  2. a % b = r 일 때, a % b == b % r 이다.

     a % b = r
     b % r = r1 
     r % r1 = r2
     .
     .
     .

  3. 위 2번을 반복하다 나머지가 0이 되었을 때 나누는 수가 최대공약수가 된다.
     
     출처 : 위키피디아

문제를 풀고 알게된 개념 및 소감

• 이번 문제는 난이도 자체가 높진 않았지만 내가 직접 알고리즘 개념을 파악한 후에 풀어서 그런지 촘..뿌틋하다. 항상 문제만 쫓아다니다가 내가 문제를 컨트롤한 기분? 이거 참 그래봤자 겨우 한 문제인데 으휴..
  다른 문제들도..이런식으로..풀 수 있으면 좋겠다..ㅎㅎ..