문제링크

문제 설명

내 풀이

def solution(n, m):
    answer = [n, m]
    big = max(answer)
    sm = min(answer)
    
    for i in range(big, 0, -1):
        if n%i == 0 and m%i==0:
            answer[0] = i
            break

    answer[1] = sm*(big//answer[0])

            
    return answer

최대공약수, 최소공배수를 구하는 수식이 있는건 알지만, 그 수식이 생각나지 않았다.
최대공약수와 최소공배수 간 관계를 떠올리면서 코드를 간단하게 짜려고 노력했다.

최대공약수가 더 쉬워서 먼저 구하고, 이를 사용해 최대공배수를 구하면 되겠다고 생각했다.

여러가지 예제를 떠올려서, 모든 예제에 적용할 수 있는 최소공배수를 구하는 방법을 떠올렸다.
이런 경우 내가 이 문제를 어떻게 푸는지를 먼저 알아낸 뒤에 코드로 작성하는 것이 편하다.

내가 최소공배수를 구할때 두 수가 큰 경우에는 소인수 분해를 한 뒤에 서로에게 없는 인수를 곱해서 구했다. 이를 코드로 만들자니 복잡하고.... 좀 더 간단하게 하는 방법이 없는지 계산해본 결과, a를 최대공약수로 나눠서 b와 곱하면 되는거였다!!

이번 코드에도 for문을 사용했기 때문에 시간복잡도가 높을 것이라 생각했는데, 시간복잡도는 높지 않았다.
for문을 많이 돌지 않게 하기 위해서 break를 사용하길 잘한것 같다!

다른 사람 풀이

점수를 많이 받은 풀이는 유클리드 호제법을 사용한 풀이었다....
유클리드 호제법을 재귀함수를 사용해 풀은 사람도 있었다.

코딩테스트를 하려면 수학 공부도 다시 해야하나...고민이 된다.