N개의 최소공배수

문제

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수를 만드는 문제입니다.

• 입력: n개의 숫자가 담긴 정수 배열 arr (길이 1 이상 15 이하, 원소는 100 이하의 자연수)
• 출력: 배열에 담긴 모든 수의 최소공배수

링크: https://school.programmers.co.kr/learn/courses/30/lessons/12953

풀이 1: 제한 사항을 활용한 브루트 포스 탐색

가장 직관적인 방법으로, 배열 내의 최댓값부터 시작하여 1씩 증가시키며 배열의 모든 원소로 나누어 떨어지는지 검사합니다.

• 장점: 로직이 매우 직관적이고 단순하여 구현하기 쉽습니다.
• 시간 복잡도 분석: 일반적인 최소공배수 문제라면 1씩 증가시키는 1차원적인 탐색은 시간 초과(Time Out)를 유발하기 쉽습니다. 하지만 이 문제는 배열의 길이가 최대 15, 원소의 최댓값이 100으로 매우 작다는 제약 조건을 가지고 있습니다. 만약 최악의 케이스로 arr = {97, 98, 99, 100}이 주어졌을 때 최소공배수는 약 9,400만 수준이며, 이는 자바 알고리즘 환경에서 1초(약 1억 번 연산) 내에 충분히 통과 가능한 수치입니다.

코드 1

class Solution {
    public int solution(int[] arr) {
        int max = 0;
        for (int n : arr) {
            max = Math.max(max, n);
        }
        
        // 최댓값부터 1씩 증가하며 탐색
        for (int i = max; ; i++) {
            boolean flag = true;
            for (int n : arr) {
                // 하나라도 나누어 떨어지지 않으면 공배수가 아님
                if (i % n != 0) {
                    flag = false;
                    break;
                }
            }
            
            // 모든 수로 나누어 떨어졌다면 최소공배수
            if (flag) {
                return i;
            }
        }
    }
}

풀이 2: 유클리드 호제법을 활용한 O(N log K) 최적화

수학적 속성을 이용하면 1씩 증가시키는 무의미한 탐색을 모두 없앨 수 있습니다. 두 수 a와 b의 최소공배수(LCM)는 두 수의 곱을 최대공약수(GCD)로 나눈 값과 같습니다. 즉, LCM(a, b) = (a * b) / GCD(a, b) 공식이 성립합니다.

N개의 수의 최소공배수는, 앞의 두 수의 최소공배수를 구한 뒤, 그 결과값과 세 번째 수의 최소공배수를 구하고, 다시 그 결과값과 네 번째 수의 최소공배수를 구하는 식으로 끝까지 누적해 나가면 쉽게 구할 수 있습니다.

• 최대공약수(GCD) 연산: 유클리드 호제법(gcd(a, b) = gcd(b, a % b))을 이용하면 아주 빠르게 최대공약수를 찾을 수 있습니다.
• 누적 연산: 배열의 첫 번째 원소를 시작 값으로 잡고, 배열을 순회하며 기존 최소공배수와 다음 원소 간의 새로운 최소공배수를 계속해서 갱신합니다.

코드 2

class Solution {
    public int solution(int[] arr) {
        // 첫 번째 원소를 초기 최소공배수로 설정
        int answer = arr[0];
        
        // 배열을 순회하며 누적 최소공배수를 갱신
        for (int i = 1; i < arr.length; i++) {
            answer = lcm(answer, arr[i]);
        }
        
        return answer;
    }
    
    // 유클리드 호제법을 이용한 최대공약수(GCD) 계산
    private int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    
    // 최소공배수(LCM) = 두 수의 곱 / 최대공약수
    private int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }
}

알고리즘 분류

수학 (Mathematics), 정수론 (Number Theory), 유클리드 호제법 (Euclidean Algorithm), 최대공약수와 최소공배수 (GCD & LCM)