๋ชฉ๋ก์ตœ๋Œ€๊ณต์•ฝ์ˆ˜ (1)

๐Ÿ“ ์ ์–ด์„œ ๋จธ๋ฆฟ์†์œผ๋กœ

[Algorithm] ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜, ์ตœ์†Œ ๊ณต๋ฐฐ์ˆ˜ ๊ตฌํ•˜๊ธฐ

GCD(Greatest Common Divisor) ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜ ๊ตฌํ•˜๊ธฐ ์œ ํด๋ฆฌ๋“œ ํ˜ธ์ œ๋ฒ• ์‚ฌ์šฉ def gcd(a, b): while b: a, b = b, a % b return a a = b x q + r ์ด๋ผ๊ณ  ํ–ˆ์„ ๋•Œ, GCD(a, b) = GCD(b, r)๋ฅผ ๋งŒ์กฑํ•œ๋‹ค. ๊ฐ„๋‹จ ์ฆ๋ช…: ์ˆ˜ํ•™์ ์œผ๋กœ ์ฆ๋ช…ํ•˜๋Š” ๋ฐฉ๋ฒ•์ด ์žˆ์ง€๋งŒ ์ดํ•ด๋ฅผ ์œ„ํ•ด์„œ ๊ฐ„๋‹จํžˆ ์„ค๋ช…ํ•˜์ž๋ฉด ์•„๋ž˜์™€ ๊ฐ™์ด ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค. b = r x m + n์œผ๋กœ ํ‘œํ˜„ํ•  ๋•Œ, n์ด 0์ด๋ผ๋ฉด b = rm์œผ๋กœ ํ‘œํ˜„๋œ๋‹ค. ์ฆ‰, b์™€ r์˜ ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜ GCD(b, r) = m์ด ๋œ๋‹ค. a = bq + r = rmq + r = r(mq + 1) ์ด๋ฏ€๋กœ GCD(a, b) = r ์ด๋‹ค. => GCD(a, b) = GCD(b, r) = GCD(r, 0) = r LCM(Lo..
Programming/Algorithm 2022. 4. 6. 11:11
์ด์ „ Prev 1 Next ๋‹ค์Œ