[Algoritm] ํ๋ ฌ ํ์ (Python ๊ตฌํ)
ํ๋ก๊ทธ๋๋จธ์ค์์ ์ ๊ณตํ๋ ์นด์นด์ค 2020๋
์ ์
๊ฐ๋ฐ์ ๋ธ๋ผ์ธ๋ ์ฝ๋ฉ ํ
์คํธ 1์ฐจ ๋ฌธ์ 3๋ฒ์ ํ์ด ๋ณด์๋ค. https://programmers.co.kr/learn/courses/30/lessons/60059 ์ฝ๋ฉํ
์คํธ ์ฐ์ต - ์๋ฌผ์ ์ ์ด์ [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr ํด๋น ๋ฌธ์ ๋ ์ด๋ค ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ ๊ฒ์ธ๊ฐ๋ฅผ ์์๋ด๋ ๊ฒ๋ณด๋ค ๊ตฌํ๋ ฅ์ด ํ์ํ ๋ฌธ์ ์๋ค๊ณ ์๊ฐํ๋ค. ํด๋น ๋ฌธ์ ์ ๊ฒฝ์ฐ ์ ํ ์ฌํญ์ ํฌ๊ธฐ๊ฐ ์๊ธฐ ๋๋ฌธ์ ๋ชจ๋ ๊ฒฝ์ฐ๋ฅผ ํ์ธํ๋ ์์ ํ์์ผ๋ก ํ์ด๊ฐ ๊ฐ๋ฅํ๋ฐ, ํ๋ ฌ์ ํ์ ๊ณผ ๋ฒ์๋ฅผ ์ค์ ํ๋ ๊ฒ์ด ์ค์ํ๋ค. ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด์๋ 2์ฐจ์ ํ๋ ฌ์ ํ์ ์ ๊ตฌํํด์ผ ..
[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..