[Algorithm] ์ฌ๊ท๋ฅผ ํตํ ์์ด(permutation) ๊ตฌํ(+ python ๋ด์ฅ ํจ์ ์ด์ฉ)
์์ด์ด๋, N๊ฐ์ ์์์์ ์ํ๋ ๊ฐ์๋ฅผ ๋ฝ์ ๋, ์์๊น์ง ๊ณ ๋ คํ๋ ๊ฒ์ ๋งํฉ๋๋ค. ์์) [1, 2, 3] ๋ฐฐ์ด์์ 2๊ฐ์ ์์๋ฅผ ์ ํํ ๊ฒฝ์ฐ => (1, 2), (1, 3), (2, 3), (2, 1), (2, 3), (3, 1), (3, 2) ์์ ๊ฐ์ ๊ฒฐ๊ณผ์ฒ๋ผ (1, 2), (2, 1)์ ๊ฒฝ์ฐ๋ ์๋ก ๋ค๋ฅธ ๊ฒ์ผ๋ก ํ๋จํฉ๋๋ค. ๐ฅธ ์ฌ๊ท๋ฅผ ํตํ ์ฝ๋ ๊ตฌํ test = [1, 2, 3] test_len = len(test) N = 2 # ๋ฝ์ ์์ด์ ๊ฐ์ visit = [0] * test_len # ํด๋น index์ ๊ฐ์ ์ฌ์ฉํ๋์ง ์ฌ๋ถ arr = [0] * N # ํ์ฌ ์์ด์ ๋ด์ ๋ฐฐ์ด arr_list = [] # ๋ชจ๋ ์์ด์ ๋ด์ ๋ฐฐ์ด def permutaion(level): if level >=..
[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..