Greatest Common Divisor Explanation

Problem Summary

Write a function that returns the greatest common divisor of two numbers.

Detailed Explanation

이 문제는 **유클리드 호제법(Euclidean Algorithm)**으로 최대공약수를 구하는 방법을 학습합니다. ## 핵심 개념: 최대공약수 (GCD) 최대공약수는 두 수를 모두 나눌 수 있는 가장 큰 수입니다. ### 유클리드 호제법 ```javascript function gcd(a, b) { while (b) { [a, b] = [b, a % b]; } return a; } ``` ### 동작 원리 GCD(a, b) = GCD(b, a % b) - 12와 8의 GCD - GCD(12, 8) → GCD(8, 4) → GCD(4, 0) → 4 ### 재귀 버전 ```javascript const gcd = (a, b) => b ? gcd(b, a % b) : a; ``` ### 왜 작동하는가? - a = b * q + r (a를 b로 나눈 몫 q, 나머지 r) - a와 b의 공약수는 b와 r의 공약수이기도 합니다 - r이 0이 되면 b가 GCD입니다 유클리드 호제법은 약 2300년 전에 고안된 효율적인 알고리즘입니다.

Solution Code

solution.js

function gcd(a, b) {
  while (b) {
    [a, b] = [b, a % b];
  }
  return a;
}

Key Concepts from This Problem

1. 유클리드 호제법

2. 최대공약수

3. 나머지 연산

4. 재귀

Common Mistakes

✗ a와 b의 순서는 알고리즘이 자동으로 처리합니다

✗ while 조건에서 b가 0이면 종료됩니다

✗ 구조 분해 할당으로 값을 동시에 교환합니다

Hints

Hint 1: 유클리드 호제법을 사용하세요.

Complexity Analysis

Time Complexity

O(log(min(a,b)))

Space Complexity

O(1)

Uses almost no additional memory

Related Tags

#알고리즘 #GCD #수학