2019/124 ๋ฐฑ์ค 14500๋ฒ ํ ํธ๋ก๋ฏธ๋ ธ ์์ ํ์(brute-force) ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ :: ์ฝ๋์๋ชฝ [๋ฐฑ์ค] 14500๋ฒ ํ ํธ๋ก๋ฏธ๋ ธ 14500๋ฒ: ํ ํธ๋ก๋ฏธ๋ ธ ํด๋ฆฌ์ค๋ฏธ๋ ธ๋ ํฌ๊ธฐ๊ฐ 1×1์ธ ์ ์ฌ๊ฐํ์ ์ฌ๋ฌ ๊ฐ ์ด์ด์ ๋ถ์ธ ๋ํ์ด๋ฉฐ, ๋ค์๊ณผ ๊ฐ์ ์กฐ๊ฑด์ ๋ง์กฑํด์ผ ํ๋ค. ์ ์ฌ๊ฐํ์ ์๋ก ๊ฒน์น๋ฉด ์ ๋๋ค. ๋ํ์ ๋ชจ๋ ์ฐ๊ฒฐ๋์ด ์์ด์ผ ํ๋ค. ์ ์ฌ๊ฐํ์ ๋ณ๋ผ๋ฆฌ ์ฐ๊ฒฐ๋์ด ์์ด์ผ ํ๋ค. ์ฆ, ๊ผญ์ง์ ๊ณผ ๊ผญ์ง์ ๋ง ๋ง๋ฟ์ ์์ผ๋ฉด ์ ๋๋ค. ์ ์ฌ๊ฐํ 4๊ฐ๋ฅผ ์ด์ด ๋ถ์ธ ํด๋ฆฌ์ค๋ฏธ๋ ธ๋ ํ ํธ๋ก๋ฏธ๋ ธ๋ผ๊ณ ํ๋ฉฐ, ๋ค์๊ณผ ๊ฐ์ 5๊ฐ์ง๊ฐ ์๋ค. ์๋ฆ์ด๋ ํฌ๊ธฐ๊ฐ N×M์ธ ์ข ์ด ์์ ํ ํธ๋ก๋ฏธ๋ ธ ํ๋๋ฅผ ๋์ผ๋ ค๊ณ ํ๋ค. ์ข ์ด๋ 1×1 ํฌ๊ธฐ์ ์นธ์ผ๋ก ๋๋ www.acmicpc.net ํ์ด ์ด๋ฐ ๋ธ๋ก ํํ์ ๋ฌธ์ ๊ฐ ๋์ค๋ฉด ์ค์ ๋ก ๋ํ์ ๊ทธ๋ ค๋ณด๋ฉด์ ๋ฌธ์ ๋ฅผ ํธ๋ ๊ฒ์ด ๊ฐ์ฅ ์ข์ ๋ฐฉ๋ฒ์ธ ๊ฒ ๊ฐ๋ค. ๋จผ์ N*M ํฌ๊ธฐ์ ์ข ์ด ์์ ๋ธ๋ก ํ๋๋ง ๋๋๋ค๊ณ ํ์ผ๋.. 2019. 12. 23. ๋ฐฑ์ค 2309๋ฒ ์ผ๊ณฑ ๋์์ด ์์ ํ์(brute-force) ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ :: ์ฝ๋ ์๋ชฝ ์์ ํ์ Brute-Force ์์ ํ์์ ๋ง ๊ทธ๋๋ก ๋ชจ๋ ๊ฒฝ์ฐ์์๋ฅผ ์ผ์ผ์ด ํ์ํ์ฌ ์ ๋ต์ ์ฐพ์๋ด๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ๊ฐ๋ฅํ ๋ฐฉ๋ฒ์ ๋ชจ๋ ํ์ธํ์ฌ ์ ํ๋๊ฐ ๋๊ณ ๊ฐ๋ ฅํ ๋ฐฉ์์ด์ง๋ง, ์๊ฐ์ ๋ค์ ์ค๋ ๊ฑธ๋ฆฌ๋ ๋จ์ ์ด ์์ต๋๋ค. ๊ทธ๋์ ๋ธ๋ฃจํธ ํฌ์ค ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ๊ธฐ ์ ์ ๋ฌธ์ ์ ๊ฐ๋ฅํ ๊ฒฝ์ฐ์ ์๋ฅผ ๋จผ์ ๊ณ์ฐ์ ํด๋ด์ผํ๋ค. ์ปดํจํฐ๊ฐ 1์ด์ ๋๋ต 1์ต ๋ฒ ์ ๋์ ์ผ์ ํ ์ ์๋ค๊ณ ํ๋ค. ํจ์จ์ฑ์ ๊ณ ๋ คํ์ฌ ๋ธ๋ฃจํธ ํฌ์ค ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ๋ฌธ์ ๋ฅผ ์ ๊ทผํ ๊ฒฝ์ฐ ๊ธฐ์ค์ ์ ํด์ฃผ๋ ๊ฒ์ด ์ข๋ค. ์๋ฅผ ๋ค์ด "์ฒ๋ง(10,000,000) ๊ฑด ์ดํ์ ๊ฒฝ์ฐ ์๊ฐ ์กด์ฌํ ๋๋ง ๋ธ๋ฃจํธ ํฌํธ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ๊ฒ ๋ค."๋ผ๋ ๊ธฐ์ค์ ์ ํ๊ณ ๋ฌธ์ ๋ฅผ ์ ๊ทผํ๋ ๊ฒ์ด ์ ๋ฆฌํ๋ค. [๋ฐฑ์ค] 2309๋ฒ ์ผ๊ณฑ ๋์์ด 2309๋ฒ: ์ผ๊ณฑ ๋์์ด ์ํ ๊ฐ์ ์ค์ ๊ฑธ.. 2019. 12. 23. ์์(Prime Number) ๊ตฌํ๊ธฐ ํจ์จ์ ์๊ณ ๋ฆฌ์ฆ :: ์ฝ๋์๋ชฝ ์์(Prime Number) ์์๋ ์์ ๋ณด๋ค ์์ ๋๊ฐ์ ์์ฐ์๋ฅผ ๊ณฑํ์ฌ ๋ง๋ค ์ ์๋ 1๋ณด๋ค ํฐ ์์ฐ์์ด๋ค. ex) 5๋ 5*1 ๋๋ 1*5๋ก ์๋ฅผ ๊ณฑํฉ ๊ฒฐ๊ณผ๋ฅผ ์ ๋ ์ ์ผํ ๋ฐฉ๋ฒ์ด ๊ทธ ์ ์์ ์ ํฌํจํ๊ธฐ ๋๋ฌธ์ 5๋ ์์์ด๋ค. ์์ (์๋ก ) - ์ํค๋ฐฑ๊ณผ, ์ฐ๋ฆฌ ๋ชจ๋์ ๋ฐฑ๊ณผ์ฌ์ ์ํค๋ฐฑ๊ณผ, ์ฐ๋ฆฌ ๋ชจ๋์ ๋ฐฑ๊ณผ์ฌ์ . ์ข์ธก์ ์์, ์ฐ์ธก์ ํฉ์ฑ์. ์์๋ ์์ ๋ณด๋ค ์์ ๋ ์์ฐ์๋ฅผ ๊ณฑํ์ฌ ๋ง๋ค ์ ์๋ 1๋ณด๋ค ํฐ ์์ฐ์์ด๋ค. ์์(็ด ๆธ, ๋ฐ์: [์์ค], ๋ฌธํ์ด: ์จ์, ์์ด: prime number)๋ ์์ ๋ณด๋ค ์์ ๋ ๊ฐ์ ์์ฐ์๋ฅผ ๊ณฑํ์ฌ ๋ง๋ค ์ ์๋ 1๋ณด๋ค ํฐ ์์ฐ์์ด๋ค. ์๋ฅผ ๋ค์ด, 5๋ 1x5 ๋๋ 5x1๋ก ์๋ฅผ ๊ณฑํ ๊ฒฐ๊ณผ๋ฅผ ์ ๋ ์ ์ผํ ๋ฐฉ๋ฒ์ด ๊ทธ ์ ์์ ์ ํฌํจํ๊ธฐ ๋๋ฌธ์ 5๋ ์์์ด๋ค. ๊ทธ๋ฌ๋ .. 2019. 12. 22. ์ต๋๊ณต์ฝ์(GCD), ์ต์๊ณต๋ฐฐ์(LCM) ๊ตฌํ๊ธฐ ์ ํด๋ฆฌ๋ ํธ์ ๋ฒ ์๊ณ ๋ฆฌ์ฆ :: ์ฝ๋์๋ชฝ ์ต๋๊ณต์ฝ์ GCD(Greatest Common Divisor) ์ต๋๊ณต์ฝ์๋ ๋ ์์ฐ์์ ๊ณตํต๋ ์ฝ์ ์ค ๊ฐ์ฅ ํฐ ์๋ฅผ ์๋ฏธํ๋ค. ex) 72 ์ 30์ ์ต๋๊ณต์ฝ์๋ 6์ด๋ค. ์ต์๊ณต๋ฐฐ์ LCM(Least Common Multiple) ์ต์๊ณต๋ฐฐ์๋ ๋ ์์ฐ์์ ๊ณตํต๋ ๋ฐฐ์ ์ค ๊ฐ์ฅ ์์ ์๋ฅผ ์๋ฏธํ๋ค. ์ต์๊ณต๋ฐฐ์ = ๋ ์์ฐ์์ ๊ณฑ / ์ต๋๊ณต์ฝ์ ex) 72 ์ 30์ ์ต์๊ณต๋ฐฐ์๋ 360์ด๋ค. ์ ํด๋ฆฌ๋ ํธ์ ๋ฒ(Euclidean Algorithm) 2๊ฐ์ ์์ฐ์๋ฅผ ๋ฐ์ ์ต๋๊ณต์ฝ์๋ฅผ ๋ฐ๊ธฐ ์ํด 2๋ถํฐ ๋ ์์ฐ์ ์ค ์์ ์์ฐ์๊น์ง ๋ชจ๋ ๋๋์ด๋ณด๋ฉด์ ๊ฐ์ฅ ํฐ ๊ณต์ฝ์๋ฅผ ๊ตฌํ ์ ์๋ค. ์์ ๊ฐ์ ๋ฐฉ๋ฒ์ผ๋ก ๋ฌธ์ ๋ฅผ ํ๋ฉด ์๊ฐ๋ณต์ก๋๋ O(N)์ด ๋๋ค. ๋์ ๋ฐฉ๋ฒ์ ์๋์ง๋ง ํจ์จ์ ๋์ด๊ธฐ ์ํด ์ ํด๋ฆฌ๋ ํธ์ ๋ฒ์ด๋ ์๊ณ ๋ฆฌ์ฆ.. 2019. 12. 22. ์ด์ 1 ๋ค์