12. ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜ (Greatest Common Divisor, GCD) Codility Lesson ํ•œ๊ตญ์–ด ์ •๋ฆฌ๋ณธ (JavaScript ver.)

์ตœ๋Œ€๊ณต์•ฝ์ˆ˜(GCD)๋ž€?

๋‘ ๊ฐœ์˜ ์ •์ˆ˜ a, b์˜ ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜(GCD)๋Š” ๋‘ ์ˆ˜๋ฅผ ๋™์‹œ์— ๋‚˜๋ˆŒ ์ˆ˜ ์žˆ๋Š” ๊ฐ€์žฅ ํฐ ์ •์ˆ˜ ๋ฅผ ์˜๋ฏธํ•œ๋‹ค.


1. O(n) ์‹œ๊ฐ„ ๋ณต์žก๋„์˜ ์œ ํด๋ฆฌ๋“œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (๋บ„์…ˆ ๋ฐฉ์‹)

JavaScript ์ฝ”๋“œ:

function gcdSubtraction(a, b) {
    if (a === b) return a;
    return a > b ? gcdSubtraction(a - b, b) : gcdSubtraction(a, b - a);
}

2. O(log n) ์‹œ๊ฐ„ ๋ณต์žก๋„์˜ ์œ ํด๋ฆฌ๋“œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (๋‚˜๋จธ์ง€ ๋ฐฉ์‹)

JavaScript ์ฝ”๋“œ:

function gcd(a, b) {
    return a % b === 0 ? b : gcd(b, a % b);
}

์ด ๋ฐฉ๋ฒ•์€ ๋น ๋ฅด๊ณ , ๋Œ€๋ถ€๋ถ„์˜ ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด์—์„œ ๊ธฐ๋ณธ์ ์œผ๋กœ ์ œ๊ณต๋œ๋‹ค.


3. ์ตœ์†Œ๊ณต๋ฐฐ์ˆ˜(LCM) ๊ณ„์‚ฐ

์ตœ์†Œ๊ณต๋ฐฐ์ˆ˜(LCM)๋Š” ๋‘ ์ˆ˜ a, b์˜ ์ตœ์†Œ๊ณต๋ฐฐ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค.

function lcm(a, b) {
    return (a * b) / gcd(a, b);
}

์ด ํ•จ์ˆ˜๋Š” O(log n) ์‹œ๊ฐ„ ๋ณต์žก๋„๋กœ ์ตœ์†Œ๊ณต๋ฐฐ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ๋‹ค.


๋ฐ˜์‘ํ˜•

๋Œ“๊ธ€