๐๏ธ์ํํธ์จ์ด/๐ปpython
python - ์๋ฃ๊ตฌ์กฐ ๊ธฐ์ด : DFS/BFS 1ํ
ํ์ = Search ๋ง์ ์์ ๋ฐ์ดํฐ ์ค์์ ์ํ๋ ๋ฐ์ดํฐ๋ฅผ ์ฐพ๋ ๊ณผ์ ๊ทธ๋ํ, ํธ๋ฆฌ ๋ฑ์ ์๋ฃ๊ตฌ์กฐ ์์์ ํ์์ ํ๋ ๋ฌธ์ ๋ฅผ ์์ฃผ ๋ค๋ฃธ ๋ํ์ ์ธ ํ์ ์๊ณ ๋ฆฌ์ฆ DFS BFS ๊ธฐ๋ณธ ์ง์ : ์คํ, ํ, ์ฌ๊ท ํจ์ ์๋ฃ ๊ตฌ์กฐ = Data Structure ๋ฐ์ดํฐ๋ฅผ ํํํ๊ณ ๊ด๋ฆฌํ๊ณ ์ฒ๋ฆฌํ๊ธฐ ์ํ ๊ตฌ์กฐ ์คํ๊ณผ ํ๋ ์๋ฃ๊ตฌ์กฐ์ ๊ธฐ์ด ๊ฐ๋ ์ด๋ค ๋ ํจ์๋ก ์ด๋ค์ง๋ค(Push, Pop) Push๋ ์ฝ์ ์ผ๋ก, ๋ฐ์ดํฐ๊ฐ ๋ค์ด๊ฐ Pop์ ์ญ์ ๋ก, ๋ฐ์ดํฐ๊ฐ ์ญ์ ๋จ ์ค์ ๋ก๋ ์คํ, ํ๋ฅผ ์ฌ์ฉ์ ๋ค๋ฅธ ๊ฒฝ์ฐ์ ์๋ก ์ค๋ฒํ๋ก ๋๋ ์ธ๋ํ๋ก๋ฅผ ๊ณ ๋ คํด์ผํจ ์ค๋ฒํ๋กOverflow ๋ ํน์ ํ ์๋ฃ๊ตฌ์กฐ๊ฐ ์์ฉํ ์ ์๋ ๋ฐ์ดํฐ ํฌ๊ธฐ๋ฅผ ์ด๋ฏธ ๊ฐ๋ ์ฐฌ ์ํ์์ ์ฝ์ ๋ ๊ฒฝ์ฐ์ ์ฐ์ฐ์ด ์ํ๋๋ฉด์ ๋ฐ์ํจ ์ฆ, ์ ์ฅ ๊ณต๊ฐ์ ๋ฒ์ด๋ ๋ฐ์ดํฐ๊ฐ ๋์ณํ๋ฅผ..
Python ์๊ณ ๋ฆฌ์ฆ - ๊ตฌํ 4ํ : ์์คํ ๊ฐ๋ฐ
๊ฐ๋จํ ๋ฌธ์ ์ค๋ช ๊ฒ์ ์บ๋ฆญํฐ๊ฐ ๋งต ์์์ ์์ง์ธ๋ค. 1 x 1 ํฌ๊ธฐ์ ์ ์ฌ๊ฐํ๋ค์ด, n x m ํฌ๊ธฐ์ ์ง์ฌ๊ฐํ์ผ๋ก ์ด๋ค์ ธ์๋ค. ๊ฐ๊ฐ์ ์นธ์ ์ก์ง ๋๋ ๋ฐ๋ค์ด๋ค. ์บ๋ฆญํฐ๋ ๋์๋จ๋ถ ์ค ํ ๊ณณ์ ๋ฐ๋ผ๋ณธ๋ค. ๋งต์ ๊ฐ ์นธ์ (A, B) ๋ก ๋ํ๋ธ๋ค. A๋ ๋ถ์ชฝ์ผ๋ก ๋จ์ด์ง ์นธ์ ๊ฐ์์ด๋ค. B๋ ์์ชฝ์ผ๋ก ๋จ์ด์ง ์นธ์ ๊ฐ์์ด๋ค. ์บ๋ฆญํฐ๋ ์ํ์ข์ฐ๋ก ์์ง์ธ๋ค. ๋ฐ๋ค๋ก ๋์ด ์๋ ๊ณต๊ฐ์ ๊ฐ ์ ์๋ค. ์บ๋ฆญํฐ ์์ง์์ ์ค์ ํ๊ธฐ ์ํด ์ ํด ๋์ ๋ฉ๋ด์ผ์ ์ด๋ ๋ค. ํ์์น์์ ํ์ฌ ๋ฐฉํฅ์ ๊ธฐ์ค, ์ผ์ชฝ ๋ฐฉํฅ์ผ๋ก๋ถํฐ ์ฐจ๋ก๋๋ก ๊ฐ ๊ณณ์ ์ ํ๋ค. ( ๋ฐ์๊ณ ๋ฐฉํฅ์ผ๋ก 90๋ ํ์ ํ ๋ฐฉํฅ) ์บ๋ฆญํฐ์ ๋ฐ๋ก ์ผ์ชฝ ๋ฐฉํฅ์ ์์ง ๊ฐ๋ณด์ง ์์ ์นธ์ด ์กด์ฌ์, ์ผ์ชฝ ๋ฐฉํฅ์ผ๋ก ํ์ ํ ๋ค์ ์ผ์ชฝ์ผ๋ก ํ ์นธ์ ์ ์ง, ์ผ์ชฝ ๋ฐฉํฅ์ ๊ฐ๋ณด์ง ์์ ์นธ์ด ์์ผ๋ฉด..
Python ์๊ณ ๋ฆฌ์ฆ - ๊ตฌํ 3ํ:์์ค ๋์ดํธ ์๊ณ ๋ฆฌ์ฆ
๊ตฌํ - ์์ค์ ๋์ดํธ ํ๋ณต ์๊ตญ ์ ์์ด ์๋ค. 8 x 8 ์ขํ ํ๋ฉด์ด๋ค. ๋์ดํธ๋ ๋งค์ผ ๋ฌด์ ์ ์ฐ๋งํ๋ค. ๋์ดํธ๋ ๋ง์ ํ๊ณ ์๊ธฐ์ ์ด๋์ L์ ํํ๋ก๋ง ์ด๋ํ ์ ์๋ค. ์ ์ ๋ฐ์ผ๋ก๋ ๋๊ฐ ์ ์๋ค. a b c d e f g h 1 2 3 4 5 6 7 8 ๋งจ ์์ ์นธ์ 1 ์ด๋ฉฐ, ์๋๋ 8์ด๋ค. ์ด๋์ด ๊ฐ๋ฅํ ๊ฒฝ์ฐ๋ 2๊ฐ์ง ๊ฒฝ์ฐ์ด๋ค. 1) ์ํ์ผ๋ก ๋ ์นธ ์ด๋ ํ ์์ง์ผ๋ก ํ ์นธ ์ด๋ 2) ์์ง์ผ๋ก ๋ ์นธ ์ด๋ ํ ์ํ์ผ๋ก ํ ์นธ ์ด๋ ์ด์ฒ๋ผ 8x8 ์ขํ ํ๋ฉด์์์ ๋์ดํธ์ ์์น๊ฐ ์ฃผ์ด์ก์ ๋ ๋์ดํธ๊ฐ ์ด๋ํ ์ ์๋ ๊ฒฝ์ฐ์ ์๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ ๋ง๋ค๊ธฐ ์กฐ๊ฑด์ ์์ค์ ํ ์์น๋ฅผ ํํ์์๋ 1๋ถํฐ 8๋ก ํํํ๊ณ , ์ด ์์น๋ฅผ ํํํ ์ a๋ถํฐ h๋ก ํํํ๋ค. ์๋ฅผ ๋ค์ด, ๋ง์ฝ ๋์ดํธ๊ฐ a1์ ์์ ๋..
Python ์๊ณ ๋ฆฌ์ฆ - ๊ตฌํ 2ํ:์๊ฐ ์๊ณ ๋ฆฌ์ฆ
๊ตฌํ - ์๊ฐ ์๊ณ ๋ฆฌ์ฆ ์ฐ์ ํ๋ฃจ๋ 24์๊ฐ, ์ด๋ก ๋๋๋ฉด 60 * 60 * 24๋ก์ 86,400 ๊ฐ์ ์์๋ก ์ชผ๊ฐค ์ ์๋ค. ์ ์ N์ ์ ๋ ฅ ๋ฐ๋๋ค. 00์ 00๋ถ 00์ด๋ถํฐ ~ ~์ 59๋ถ 59์ด๊น์ง ๋ชจ๋ ์์ ์์์ ํน์ ์์ธ N์ด ํฌํจ๋์ด ์๋ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ๊ตฌํํด๋ณด์. ์๋ฅผ ๋ค์ด, 7์ ์ ๋ ฅ๋ฐ๋๋ค. ์๊ฐ์ ์ฌ ์ ์์ง๋ง, ๋ถ์์๋ _ _ ์์ ์์๋ฆฌ์๋ 0๋ถํฐ 6๊น์ง๋ง ์ฌ ์ ์์ผ๋ฏ๋ก, ๋๋ฒ์งธ ์๋ฆฌ์๋ง ์ฌ ์ ์๋ค. ๊ทธ๋ฆฌ๊ณ ์ด์์๋ _ _ ์ด๋ฏ๋ก ๋ง์ฐฌ๊ฐ์ง์ด๋ค. .... 01 ์ 17 ๋ถ 47์ด ... 20 ์ 58 ๋ถ 07์ด ... ์ด๋ฐ์์ผ๋ก ์ ์ ์๋ ์๊ฐ์ด ์์ผ๋ฉฐ, ๊ทธ ์ธ์๋ ์ ์ ์๋ ์๊ฐ์ด๋ค. ์ ๋ ฅ ์กฐ๊ฑด : ์ฒซ์งธ ์ค์ ์ ์ n์ ์ ๋ ฅํ๋ค ( 0
Python ์๊ณ ๋ฆฌ์ฆ - ๊ตฌํ 1ํ:์ํ์ข์ฐ
๊ตฌํ ๋ฌธ์ ์ ํต์ฌ์ ๋ผ์ด๋ธ๋ฌ๋ฆฌ ์ฌ์ฉ ๊ฒฝํ์ด๋ค. ๋ถ์กฑํ๋ค๋ฉด, ๊ตฌํ ์ ํ์ ๋ฌธ์ ๋ฅผ ํ ๋ ๊ฐ์ด ์ค์ง ์์ ๊ฒ์ด๋ค. ์๋ฅผ ๋ค์ด, n๊ฐ์ ์์๊ฐ ๋ค์ด ์๋ ๋ฆฌ์คํธ์์ r๊ฐ์ ์์๋ฅผ ๋ฝ์ ํ ์ค๋ก ์ธ์ฐ๋ ๋ชจ๋ ๊ฒฝ์ฐ(์์ด)๋ฅผ ๊ตฌํด์ผ ํ๋ ๋ฌธ์ ๋ฅผ ๋ง๋๋ค๊ณ ๊ฐ์ ํด๋ณด์. ๋ค์ํ ๊ธฐ๋ฅ์ ์ฌ์ฉํ ์ ์๊ฒ ์ง๋ง, ๊ฐ๋จํ๊ฒ itertools (ํ์ค ๋ผ์ด๋ธ๋ฌ๋ฆฌ)๋ก ์ฝ๊ฒ ์งค ์๋ ์๋ค. ์ฆ, ์ธ์ด์ ๋ฌธ๋ฒ์ ์ ์ดํดํ๊ณ ๊ฒฝํ์ด ์์ด์ผ๋ง, ์๊ฐ์ ์ ํ๊ณผ ๋ฐ์์ด ๋ฐ๋ก ๋ ์ค๋ฅธ๋ค. ๊ตฌํ ์ ํ์ 2๊ฐ์ง๋ก ํ ์ ์๋ค. ์ฒซ์งธ, ์์ ํ์์ด๋ค. - ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ์ฃผ์ ์์ด ๋ค ๊ณ์ฐํ๋ ํด๊ฒฐ ๋ฐฉ๋ฒ ๋์งธ, ์๋ฎฌ๋ ์ด์ ์ด๋ค. - ๋ฌธ์ ์์ ์ ์ํ ์๊ณ ๋ฆฌ์ฆ์ ํ ๋จ๊ณ์ฉ ์ฐจ๋ก๋๋ก ์ง์ ์ํํด์ผ ํ๋ ๋ฌธ์ ์ด๋ค ๋ฉ๋ชจ๋ฆฌ ์ ์ฝ ์ฌํญ #1 ๊ธฐ๋ณธ์ ์ธ ์ ์ํ์ 4๋ฐ์ด..
Python - ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ ์ ๋ณต 2ํ
๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ - ์ซ์ ์นด๋ ๊ฒ์ ์ซ์ ์นด๋ ๊ฒ์์ ํ ์ข ๋ฅ๋ก์, ์ฌ๋ฌ ๊ฐ์ ์ซ์ ์นด๋ ์ค์์ ๊ฐ์ฅ ๋์ ์ซ์๊ฐ ์ฐ์ธ ์นด๋ ํ ์ฅ์ ๋ฝ๋ ๊ฒ์์ด๋ค. ๊ฒ์์ ๋ฃฐ์ ๋ค์๊ณผ ๊ฐ๋ค. 1. ์ซ์๊ฐ ์ฐ์ธ ์นด๋๋ค์ด n x m ํํ๋ก ๋์ฌ์ ธ ์์ผ๋ฉฐ, ์ด๋ n์ ํ์ ๊ฐ์๋ฅผ ์๋ฏธํ๋ฉฐ, m์ ์ด์ ๊ฐ์๋ฅผ ์๋ฏธํ๋ค 2. ๋จผ์ ๋ฝ๊ณ ์ ํ๋ ์นด๋๊ฐ ํฌํจ๋์ด ์๋ ํ์ ์ ํํ๋ค. 3. ๊ทธ๋ค์ ์ ํ๋ ํ์ ํฌํจ๋ ์นด๋๋ค ์ค ๊ฐ์ฅ ์ซ์๊ฐ ๋ฎ์ ์นด๋๋ฅผ ๋ฝ์์ผ ํ๋ค. 4. ๋ฐ๋ผ์ ์ฒ์์ ์นด๋๋ฅผ ๊ณจ๋ผ๋ผ ํ์ ์ ํํ ๋, ์ดํ์ ํด๋น ํ์์ ๊ฐ์ฅ ์ซ์๊ฐ ๋ฎ์ ์นด๋๋ฅผ ๋ฝ์ ๊ฒ์ ๊ณ ๋ คํ์ฌ ์ต์ข ์ ์ผ๋ก ๊ฐ์ฅ ๋์ ์ซ์์ ์นด๋๋ฅผ ๋ฝ์ ์ ์๋๋ก ์ ๋ต์ ์ธ์์ผํ๋ค. ์ฆ, ๊ฐ ํ์ ์ซ์์์ ๊ฐ์ฅ ์์ ๊ฐ๋ค ์ค์์, ๊ฐ์ฅ ํฐ ์๋ฅผ ์ฐพ์ผ๋ฉด ๋๋ ๊ฒ์์ด๋ค..
Python - ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ ์ ๋ณตํ๊ธฐ 1ํ
1. ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ greedy๋ ํ์์ ์ด๋ ๋ป์ด๋ฏ๋ก, ํ์๋ฒ์ด๋ผ๊ณ ๋ ํ๋ค. ์ฆ, ํ์์ ์ผ๋ก ๋ฌธ์ ๋ฅผ ํธ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ผ๋ ๋ป์ด๋ค. ์ฌ๊ธฐ์ ํ์์ ์ด๋๊ฒ ๋ฌธ์ ๋ฅผ ํ๋ ํ์ฌ ์ํฉ์์ ๊ฐ์ฅ ์ข์ ๊ฒ๋ง ๊ณ ๋ฅด๋ ๋ฐฉ๋ฒ์ ๋งํ๋ค. ํ์ฌ์ ์ํฉ๋ง ๊ณ ๋ คํ๊ณ , ํ์ฌ์ ์ ํ์ด ๋์ค์ ๋ฏธ์น ์ํฅ์ ๋ํด์๋ ๊ณ ๋ คํ์ง ์๋๊ฒ ํฐ ํน์ง์ด๋ค. ์ผ๋จ, ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ด ์ ํ์ ๋ค์ํ๊ณ , ๋ง์ ๋ฌธ์ ๋ฅผ ํ๋ฉด์ ์ฌ์ ์ง์์ด ํ์ํ ๋ฌธ์ ์ ์๋ ๋ฌธ์ ๋ฅผ ๊ตฌ๋ณํด์ ํ์ด์ผํ๋ค. ํนํ๋, ์ฐฝ์๋ ฅ๊ณผ ๋ฌธ์ ๋ฅผ ํ๊ธฐ ์ํ ์ต์ํ์ ์์ด๋์ด๋ฅผ ๋ ์ฌ๋ฆด ์ ์๋ ๋ฅ๋ ฅ์ ๊ฐ์ถฐ์ผ ํ๋ค. ๋น์ทํ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก๋ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ๋น ๋ฅด๊ฒ ์ฐพ์์ผ ํ๋ 'ํ๋ก์ด๋ ์์ Floyd-Warshall' ํน์ '๋ค์ต์คํธ๋ผDijkstra' ์๊ณ ๋ฆฌ์ฆ์ด ์๋ค. 1. ๊ทธ๋ฆฌ๋ - ๊ฑฐ์ค๋ฆ๋ 128..
[๋ฐฑ์ค] 10870๋ฒ. ํผ๋ ธ๋์น์ ์ฐพ๊ธฐ(์ฌ๊ท) & ๋ธ๋ฃจํธํฌ์ค - 2798๋ฒ. ๋ธ๋์ญ
๋ฌธ์ ํผ๋ณด๋์น ์๋ 0๊ณผ 1๋ก ์์ํ๋ค. 0๋ฒ์งธ ํผ๋ณด๋์น ์๋ 0์ด๊ณ , 1๋ฒ์งธ ํผ๋ณด๋์น ์๋ 1์ด๋ค. ๊ทธ ๋ค์ 2๋ฒ์งธ ๋ถํฐ๋ ๋ฐ๋ก ์ ๋ ํผ๋ณด๋์น ์์ ํฉ์ด ๋๋ค. ์ด๋ฅผ ์์ผ๋ก ์จ๋ณด๋ฉด Fn = Fn-1 + Fn-2 (n ≥ 2)๊ฐ ๋๋ค. n=17์ผ๋ ๊น์ง ํผ๋ณด๋์น ์๋ฅผ ์จ๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ๋ค. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n์ด ์ฃผ์ด์ก์ ๋, n๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ n์ด ์ฃผ์ด์ง๋ค. n์ 20๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์ ๋๋ 0์ด๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ n๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ์ถ๋ ฅํ๋ค. ์์ ์ ๋ ฅ ํด์ค ์ฝ๋ n = int(input()) def fib(n): if n == 0: r..
[๋ฐฑ์ค] 1978๋ฒ. ์์ ์ฐพ๊ธฐ
๋ฌธ์ ์ฃผ์ด์ง ์ N๊ฐ ์ค์์ ์์๊ฐ ๋ช ๊ฐ์ธ์ง ์ฐพ์์ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ฒซ ์ค์ ์์ ๊ฐ์ N์ด ์ฃผ์ด์ง๋ค. N์ 100์ดํ์ด๋ค. ๋ค์์ผ๋ก N๊ฐ์ ์๊ฐ ์ฃผ์ด์ง๋๋ฐ ์๋ 1,000 ์ดํ์ ์์ฐ์์ด๋ค. ์ถ๋ ฅ ์ฃผ์ด์ง ์๋ค ์ค ์์์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค. ์์ ์ ๋ ฅ ํด์ค ์ฝ๋ n = int(input()) num_list = list(map(int, input().split())) count = 0 def is_prime(num): if num == 1: # 1์ ์์๊ฐ ์๋๋ค return False i = 2 while i < num: if num % i == 0: return False i += 1 return True for num in num_list: if is_prime(num): # t..
[๋ฐฑ์ค] 1316๋ฒ. ๊ทธ๋ฃน ๋จ์ด ์ฒด์ปค
๋ฌธ์ ๊ทธ๋ฃน ๋จ์ด๋ ๋จ์ด์ ์กด์ฌํ๋ ๋ชจ๋ ๋ฌธ์์ ๋ํด์, ๊ฐ ๋ฌธ์๊ฐ ์ฐ์ํด์ ๋ํ๋๋ ๊ฒฝ์ฐ๋ง์ ๋งํ๋ค. ์๋ฅผ ๋ค๋ฉด, ccazzzzbb๋ c, a, z, b๊ฐ ๋ชจ๋ ์ฐ์ํด์ ๋ํ๋๊ณ , kin๋ k, i, n์ด ์ฐ์ํด์ ๋ํ๋๊ธฐ ๋๋ฌธ์ ๊ทธ๋ฃน ๋จ์ด์ด์ง๋ง, aabbbccb๋ b๊ฐ ๋จ์ด์ ธ์ ๋ํ๋๊ธฐ ๋๋ฌธ์ ๊ทธ๋ฃน ๋จ์ด๊ฐ ์๋๋ค. ๋จ์ด N๊ฐ๋ฅผ ์ ๋ ฅ์ผ๋ก ๋ฐ์ ๊ทธ๋ฃน ๋จ์ด์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ๋จ์ด์ ๊ฐ์ N์ด ๋ค์ด์จ๋ค. N์ 100๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ ๋จ์ด๊ฐ ๋ค์ด์จ๋ค. ๋จ์ด๋ ์ํ๋ฒณ ์๋ฌธ์๋ก๋ง ๋์ด์๊ณ ์ค๋ณต๋์ง ์์ผ๋ฉฐ, ๊ธธ์ด๋ ์ต๋ 100์ด๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ๊ทธ๋ฃน ๋จ์ด์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค. ์์ ์ ๋ ฅ ํด์ค ์ฝ๋ n = int(input()) words =..