프로그래머스: 최대공약수와 최소공배수

문제 설명

• 두 수 n과m의 최대공약수, 최소공배수를 구하는 문제입니다.

접근법

• 최대공약수를 구하는 방법은 유클리드 호제법또는 1부터 Max(n,m)까지 값을 꺼내 n과m이 나눠떨어지는지 확인하는 방법이 있습니다.

• 최소공배수 = 숫자n x 숫자m / (n과m의 최대공약수)입니다.

정답

파이썬

def solution(n, m):
    min_ = 1
    for i in range(1,min(n,m)+1):
        if n%i == 0 and m%i == 0:
            min_ = i
    
        
    answer = [min_,n*m/min_]
    return answer

자바

class Solution {
    public int GCD(int n, int m){ #GCD메서드를 유클리드 호제법으로 구현합니다
        int tmp;        
        while (m != 0){ // 파이썬은 while y가 되지만 java는 안됩니다
            // 파이썬은 n,m = m,n%m이 되지만 자바는 안됩니다.
            tmp = n;
            n = m;
            m = tmp%m;
        }
        return n;
    }
    
    public int[] solution(int n, int m) {
        int[] answer = {0,0};
        answer[0] = GCD(n,m);
        answer[1] = n*m/GCD(n,m);
        return answer;
    }
}

기타

• 개인적으로 유클리드 호제법은 설명을 봐도 이해가 잘 되지 않았습니다. 그래서 이론적으로 완벽히 이해하려고 하기 보다는 대략적인 코드를 외운 뒤 직접 활용하고 문제를 풀면서 대략적인 메커니즘을 이해했습니다. 저는 DFS,BFS,백테스트 등의 내용도 이러한 방식으로 공부하는 게 더 효율적이였습니다.