알고리즘) 유클리드 호제법

2023. 12. 29. 20:53알고리즘/개인공부

먼 과거, ‘유클리드’ 라는 사람이 적은 책의 내용으로 2개의 자연수 또는 정식의 최대공약수를 구하는 가장 오래된 알고리즘으로도 알려저 있다. 먼저 호제법의 의미는 두 수가 서로 상대방의 수를 나누어서 결국 원하는 수를 얻는 알고리즘 방식을 뜻하며, 이 유클리드 호제법의 개념은 다음과 같다.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라서, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

추가로, 최소공배수를 구하는 방법은 두 수 a, b를 곱한 수에 최대공약수를 나누어 나온 몫이 바로 최소공배수이다.

// 프로그래머스 최대공약수 최소공배수 구하는 문제

using System;

public class Solution {
    public int[] solution(int n, int m) {
        // 유클리드 호제법을 사용해서 최대공약수를 구한 다음
        // 최소 공배수는 구하는 두 수의 곱에서 최대공약수를 나누어서 구한다        
        int[] answer = new int[2];
        int min = 0; // min은 최대공약수
        int max = 0; // max는 최소공배수

        min = gcd(n, m);
        max = (n*m) / min;

        answer[0] = min;
        answer[1] = max;

        return answer;
    }
    public int gcd(int n, int m)
    {
        if(m == 0) return n;
        else return gcd(m, n%m);
    }
}

'알고리즘 > 개인공부' 카테고리의 다른 글

다익스트라 알고리즘(Dijkstra)  (0) 2024.07.15