[Lv.2] N개의 최소공배수 [프로그래머스_코딩테스트] [수학, 유클리드 호제법] [30분]

🔍 문제 요약

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

프로그래머스

1~100의 자연수의 배열 arr이 주어지고 해당 숫자들의 최소공배수를 구하는 문제.

🧠 나의 접근 방식과 시행착오

30분 정도 걸렸다. 사실 유클리드 호제법과 같은 공식적인 부분에 익숙하지 않았어서 논리적으로 생각을 해서 각 숫자들을 소인수 분해를 한 것들을 중복 체크를 해서 나온 값들을 곱하는 형태로 풀었다. 사실 이렇게 풀었어도 풀이가 길어지다 보니 확실하게 정답이 맞을지는 몰랐지만 테스트 케이스는 다 통과하긴 했던 문제.

using System;
using System.Collections.Generic;

public class Solution
{
    /// <summary>
    /// N개의 최소공배수
    /// https://school.programmers.co.kr/learn/courses/30/lessons/12953
    /// </summary>
    public int solution(int[] arr)
    {
        // 아이템이 한개면 최소공배수는 자기 자신
        if (arr.Length == 1) return arr[0];
        
        Dictionary<int,int> yackDict = new Dictionary<int,int>();

        for (int i = 0; i < arr.Length; i++)
        {
            int n = arr[i];
            Dictionary<int,int> tempDict = new Dictionary<int,int>();
            
            for (int j = 2; j <= n; j++)
            {
                if (n % j == 0)
                {
                    if (!tempDict.ContainsKey(j))
                    {
                        tempDict.Add(j, 1);
                    }
                    else
                    {
                        tempDict[j] += 1;
                    }

                    n /= j;
                    j = 1;
                }
            }

            foreach (var pair in tempDict)
            {
                int key = pair.Key;
                int count = pair.Value;

                if (!yackDict.ContainsKey(key))
                {
                    yackDict.Add(key, count);
                }
                else if (yackDict[key] < count)
                {
                    yackDict[key] = count;
                }
            }
        }

        int res = 1;

        foreach (var pair in yackDict)
        {
            int key = pair.Key;
            for (int i = 0; i < pair.Value; i++)
            {
                res *= key;
            }
        }
        
        return res;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        var arr = new int[] { 2, 6, 8, 14 };
        Console.Write(sl.solution(arr));
    }
}

✅ 풀이 코드

피드백은 유클리드 호제법을 써서 GCD -> LCM을 해서 풀라고 한다. 코드가 확실히 간결하게 되는 장점이 있어 보이고 자주 쓰일 수 있기에 꼭 기억해두면 좋지 않을까 싶음. 

public class Solution
{
    public int solution(int[] arr)
    {
        int lcm = arr[0]; // 초기값은 첫 번째 수

        for (int i = 1; i < arr.Length; i++)
        {
            lcm = LCM(lcm, arr[i]); // 누적해서 최소공배수 계산
        }

        return lcm;
    }

    // 최소공배수 구하는 공식: A * B / 최대공약수(GCD)
    private int LCM(int a, int b)
    {
        return a * b / GCD(a, b);
    }

    // 유클리드 호제법을 이용한 최대공약수 구하기
    private int GCD(int a, int b)
    {
        while (b != 0)
        {
            int temp = b;
            b = a % b;
            a = temp;
        }

        return a;
    }
}

✅ 유클리드 호제법이란?

두 수 a와 b의 최대공약수는 b와 a % b의 최대공약수와 같다.
즉, GCD(a, b) = GCD(b, a % b)
이 과정을 나머지가 0이 될 때까지 반복하면 마지막 남은 값이 최대공약수다.

---

🧠 왜 맞는 걸까? (직관적 이해)

• a와 b가 어떤 수 d로 나눠진다면, a % b도 d로 나눠질 수밖에 없어요.
• a = b * q + r 형태로 나누었을 때, GCD(a, b)는 GCD(b, r)와 같아요.
• 이렇게 계속 나머지를 줄여가다 보면 결국 0이 되고, 가장 마지막 나눈 수가 두 수의 공통된 가장 큰 약수, 즉 최대공약수입니다.

🔄 정리

유클리드 호제법이라는게 한 번에 와닿는 느낌은 아니지만 잘 기억해두면 이곳저곳에서 쓸 수 있는 공식이긴 하다.