๐ป Algorithm
-
[Python] ๋ฐฑ์ค 2615 ์ค๋ชฉ (Brute Force)๐ป Algorithm/Python 2022. 7. 2. 15:44
๐ ๋ฌธ์ ์ค๋ชฉ์ ๋ฐ๋ํ์ ๊ฒ์ ๋ฐ๋์๊ณผ ํฐ ๋ฐ๋์์ ๊ต๋๋ก ๋์์ ๊ฒจ๋ฃจ๋ ๊ฒ์์ด๋ค. ๋ฐ๋ํ์๋ 19๊ฐ์ ๊ฐ๋ก์ค๊ณผ 19๊ฐ์ ์ธ๋ก์ค์ด ๊ทธ๋ ค์ ธ ์๋๋ฐ ๊ฐ๋ก์ค์ ์์์๋ถํฐ ์๋๋ก 1๋ฒ, 2๋ฒ, ... ,19๋ฒ์ ๋ฒํธ๊ฐ ๋ถ๊ณ ์ธ๋ก์ค์ ์ผ์ชฝ์์๋ถํฐ ์ค๋ฅธ์ชฝ์ผ๋ก 1๋ฒ, 2๋ฒ, ... 19๋ฒ์ ๋ฒํธ๊ฐ ๋ถ๋๋ค. ์์ ๊ทธ๋ฆผ์์์ ๊ฐ์ด ๊ฐ์ ์์ ๋ฐ๋์์ด ์ฐ์์ ์ผ๋ก ๋ค์ฏ ์์ ๋์ด๋ฉด ๊ทธ ์์ด ์ด๊ธฐ๊ฒ ๋๋ค. ์ฌ๊ธฐ์ ์ฐ์์ ์ด๋ ๊ฐ๋ก, ์ธ๋ก ๋๋ ๋๊ฐ์ ๋ฐฉํฅ ๋ชจ๋๋ฅผ ๋ปํ๋ค. ์ฆ, ์์ ๊ทธ๋ฆผ์ ๊ฒ์์์ด ์ด๊ธด ๊ฒฝ์ฐ์ด๋ค. ํ์ง๋ง ์ฌ์ฏ ์ ์ด์์ด ์ฐ์์ ์ผ๋ก ๋์ธ ๊ฒฝ์ฐ์๋ ์ด๊ธด ๊ฒ์ด ์๋๋ค. ์ ๋ ฅ์ผ๋ก ๋ฐ๋ํ์ ์ด๋ค ์ํ๊ฐ ์ฃผ์ด์ก์ ๋, ๊ฒ์์์ด ์ด๊ฒผ๋์ง, ํฐ์์ด ์ด๊ฒผ๋์ง ๋๋ ์์ง ์น๋ถ๊ฐ ๊ฒฐ์ ๋์ง ์์๋์ง๋ฅผ ํ๋จํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค...
-
[Python] ๋ฐฑ์ค 1913 ๋ฌํฝ์ด (๊ตฌํ)๐ป Algorithm/Python 2022. 7. 2. 15:39
๐ ๋ฌธ์ ํ์์ธ ์์ฐ์ N์ด ์ฃผ์ด์ง๋ฉด, ๋ค์๊ณผ ๊ฐ์ด 1๋ถํฐ N2๊น์ง์ ์์ฐ์๋ฅผ ๋ฌํฝ์ด ๋ชจ์์ผ๋ก N×N์ ํ์ ์ฑ์ธ ์ ์๋ค. N์ด ์ฃผ์ด์ก์ ๋, ์ด๋ฌํ ํ๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ๋ํ N2 ์ดํ์ ์์ฐ์๊ฐ ํ๋ ์ฃผ์ด์ก์ ๋, ๊ทธ ์ขํ๋ ํจ๊ป ์ถ๋ ฅํ์์ค. ์๋ฅผ ๋ค์ด N=5์ธ ๊ฒฝ์ฐ 6์ ์ขํ๋ (4,3)์ด๋ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ํ์์ธ ์์ฐ์ N(3 ≤ N ≤ 999)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค์๋ ์์น๋ฅผ ์ฐพ๊ณ ์ ํ๋ N2 ์ดํ์ ์์ฐ์๊ฐ ํ๋ ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ N๊ฐ์ ์ค์ ๊ฑธ์ณ ํ๋ฅผ ์ถ๋ ฅํ๋ค. ๊ฐ ์ค์ N๊ฐ์ ์์ฐ์๋ฅผ ํ ์นธ์ฉ ๋์ด์ ์ถ๋ ฅํ๋ฉด ๋๋ฉฐ, ์๋ฆฟ์๋ฅผ ๋ง์ถ ํ์๊ฐ ์๋ค. N+1๋ฒ์งธ ์ค์๋ ์ ๋ ฅ๋ฐ์ ์์ฐ์์ ์ขํ๋ฅผ ๋ํ๋ด๋ ๋ ์ ์๋ฅผ ํ ์นธ ๋์ด์ ์ถ๋ ฅํ๋ค. ์์ ์ ๋ ฅ 1 7 35 ์์ ์ถ๋ ฅ 1 49..
-
[Python] ๋ฐฑ์ค 2178 ๋ฏธ๋ก ํ์ (BFS)๐ป Algorithm/Python 2022. 7. 2. 15:36
๐ ๋ฌธ์ N×Mํฌ๊ธฐ์ ๋ฐฐ์ด๋ก ํํ๋๋ ๋ฏธ๋ก๊ฐ ์๋ค. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 ๋ฏธ๋ก์์ 1์ ์ด๋ํ ์ ์๋ ์นธ์ ๋ํ๋ด๊ณ , 0์ ์ด๋ํ ์ ์๋ ์นธ์ ๋ํ๋ธ๋ค. ์ด๋ฌํ ๋ฏธ๋ก๊ฐ ์ฃผ์ด์ก์ ๋, (1, 1)์์ ์ถ๋ฐํ์ฌ (N, M)์ ์์น๋ก ์ด๋ํ ๋ ์ง๋์ผ ํ๋ ์ต์์ ์นธ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ํ ์นธ์์ ๋ค๋ฅธ ์นธ์ผ๋ก ์ด๋ํ ๋, ์๋ก ์ธ์ ํ ์นธ์ผ๋ก๋ง ์ด๋ํ ์ ์๋ค. ์์ ์์์๋ 15์นธ์ ์ง๋์ผ (N, M)์ ์์น๋ก ์ด๋ํ ์ ์๋ค. ์นธ์ ์ ๋์๋ ์์ ์์น์ ๋์ฐฉ ์์น๋ ํฌํจํ๋ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ๋ ์ ์ N, M(2 ≤ N, M ≤ 100)์ด ์ฃผ์ด์ง๋ค. ๋ค์ N๊ฐ์ ์ค์๋ M๊ฐ์ ์ ์๋ก ๋ฏธ๋ก๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ๊ฐ์ ์๋ค์ ๋ถ์ด์ ..
-
[Python] ๋ฐฑ์ค 1325 ํจ์จ์ ์ธ ํดํน (BFS)๐ป Algorithm/Python 2022. 7. 2. 15:33
๐ ๋ฌธ์ ํด์ปค ๊น์ง๋ฏผ์ ์ ์๋ ค์ง ์ด๋ ํ์ฌ๋ฅผ ํดํนํ๋ ค๊ณ ํ๋ค. ์ด ํ์ฌ๋ N๊ฐ์ ์ปดํจํฐ๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ๊น์ง๋ฏผ์ ๊ท์ฐฎ๊ธฐ ๋๋ฌธ์, ํ ๋ฒ์ ํดํน์ผ๋ก ์ฌ๋ฌ ๊ฐ์ ์ปดํจํฐ๋ฅผ ํดํน ํ ์ ์๋ ์ปดํจํฐ๋ฅผ ํดํนํ๋ ค๊ณ ํ๋ค. ์ด ํ์ฌ์ ์ปดํจํฐ๋ ์ ๋ขฐํ๋ ๊ด๊ณ์, ์ ๋ขฐํ์ง ์๋ ๊ด๊ณ๋ก ์ด๋ฃจ์ด์ ธ ์๋๋ฐ, A๊ฐ B๋ฅผ ์ ๋ขฐํ๋ ๊ฒฝ์ฐ์๋ B๋ฅผ ํดํนํ๋ฉด, A๋ ํดํนํ ์ ์๋ค๋ ์๋ฆฌ๋ค. ์ด ํ์ฌ์ ์ปดํจํฐ์ ์ ๋ขฐํ๋ ๊ด๊ณ๊ฐ ์ฃผ์ด์ก์ ๋, ํ ๋ฒ์ ๊ฐ์ฅ ๋ง์ ์ปดํจํฐ๋ฅผ ํดํนํ ์ ์๋ ์ปดํจํฐ์ ๋ฒํธ๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์, N๊ณผ M์ด ๋ค์ด์จ๋ค. N์ 10,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์, M์ 100,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค. ๋์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์ ์ ๋ขฐํ๋ ๊ด๊ณ๊ฐ A B์ ๊ฐ์ ํ์์ผ๋ก ๋ค์ด์ค..
-
[Python] ๋ฐฑ์ค 11725 ํธ๋ฆฌ์ ๋ถ๋ชจ ์ฐพ๊ธฐ (DFS)๐ป Algorithm/Python 2022. 7. 2. 15:29
๐ ๋ฌธ์ ๋ฃจํธ ์๋ ํธ๋ฆฌ๊ฐ ์ฃผ์ด์ง๋ค. ์ด๋, ํธ๋ฆฌ์ ๋ฃจํธ๋ฅผ 1์ด๋ผ๊ณ ์ ํ์ ๋, ๊ฐ ๋ ธ๋์ ๋ถ๋ชจ๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ ๋ ฅ ์ฒซ์งธ ์ค์ ๋ ธ๋์ ๊ฐ์ N (2 ≤ N ≤ 100,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N-1๊ฐ์ ์ค์ ํธ๋ฆฌ ์์์ ์ฐ๊ฒฐ๋ ๋ ์ ์ ์ด ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค๋ถํฐ N-1๊ฐ์ ์ค์ ๊ฐ ๋ ธ๋์ ๋ถ๋ชจ ๋ ธ๋ ๋ฒํธ๋ฅผ 2๋ฒ ๋ ธ๋๋ถํฐ ์์๋๋ก ์ถ๋ ฅํ๋ค. ์์ ์ ๋ ฅ 1 7 1 6 6 3 3 5 4 1 2 4 4 7 ์์ ์ถ๋ ฅ 1 4 6 1 3 1 4 ์์ ์ ๋ ฅ 2 12 1 2 1 3 2 4 3 5 3 6 4 7 4 8 5 9 5 10 6 11 6 12 ์์ ์ถ๋ ฅ 2 1 1 2 3 3 4 4 5 5 6 6 ๐ ํ์ด import sys sys.setrecursionlimit(10**6) inp..
-
[Python] ๋ฐฑ์ค 19583 ์ธ์ด๋ฒ๊ฐ๊ฐ์ดํ (Set)๐ป Algorithm/Python 2022. 7. 2. 15:27
๐ ๋ฌธ์ ๋ณด์์ด๋ ์๊ณ ๋ฆฌ์ฆ ๋์๋ฆฌ HI-ARC๋ฅผ ์ด์ํ๊ณ ์๋ค. ๋ณด์์ด์ ์ด์์ง ์ผ๋์ 20๋ ๋์ ์ ํํ๋ ์ ์ ์๋ค์ ๋ง์ดํ๊ธฐ ์ํด ์ด์ฌํ ์ค๋น๋ฅผ ํด์์ผ๋, ์ ์ผ๋ณ์ ์ ํ์ด ์ ํ๋ ๋๋จธ์ง ์ ๋ถ์์๋ “์ฌํ์ ๊ฑฐ๋ฆฌ๋๊ธฐ”๋ฅผ ์ ์ธํ๊ณ ๊ทธ์ ๋ฐ๋ผ ํ๊ต์์๋ ๊ต๋ด ๋ชจ๋ ๋์๋ฆฌ์ ์คํ๋ผ์ธ ๋ชจ์์ ์์ ํ๋ผ๋ ๊ณต์ง๋ฅผ ํ๊ธฐ์ ์ด๋ฅด๋ ๋ค. ์คํ๋ผ์ธ์์ ๋ชจ์์ ์์ ํ๋ผ๋ ๊ถ๊ณ ๊ฐ ๋์จ ์ด๋ ค์ด ์ํฉ์๋ ๋ถ๊ตฌํ๊ณ , ๋ณด์์ด๋ ๊ธฐ์ง๋ฅผ ๋ฐํํ์ฌ ๊ฐ๊ฐ์ดํ๋ฅผ ๋ฏธํ๋ธ ์คํธ๋ฆฌ๋ฐ์ผ๋ก ๋์ฒดํ๋ ๊ฒฐ์ ์ ํ๊ฒ ๋๋ค. ํ์ง๋ง, ๋ฏธํ๋ธ ์คํธ๋ฆฌ๋ฐ์ผ๋ก ๊ฐ๊ฐ์ดํ๋ฅผ ํ๊ฒ ๋ ๊ฒฝ์ฐ, ์๋์ ๊ฐ์ ๋ฌธ์ ๊ฐ ์์๋ค. ๋๊ฐ ๊ฐ๊ฐ์ดํ์ ์๋์ง ์ ์ ์๋ค. ๋๊ฐ ๊ฐ๊ฐ์ดํ ์๋ฆฌ์ ๋๊น์ง ๋จ์์์๋์ง ์ ์ ์๋ค. ์ด๋ค ์ฌ๋์ด ๊ฐ๊ฐ์ดํ ์คํธ๋ฆฌ๋ฐ์ ๋จ์ํ ํ์ด๋๊ธฐ๋ง ํ๋์ง ์..
-
[Python] ๋ฐฑ์ค 2594 ๋์ด๊ณต์ (๊ตฌํ)๐ป Algorithm/Python 2022. 7. 2. 15:23
๐ ๋ฌธ์ ๋์ด๊ณต์์์ ์ฌ๋ฌ ๊ฐ์ ๋์ด๊ธฐ๊ตฌ๋ฅผ ๋งก์ ์ผํ๋ ์ธํ์ด์ ๊ทผ์์ด๋ ์๋ก ์ข์ํ๋ ์ฌ์ด์ด๋ค. ๊ทธ๋ค์ ์ฌ๋ ์๊ฐ์ ์ด์ฉํ์ฌ ๋๋ง์ ์๊ฐ์ ๊ฐ์ง๊ธฐ๋ฅผ ์ํ๋ค. ๊ทธ๋์ ๋งค์ผ ์ผ๊ณผ ์์ ์ ์ ๋์ด๊ธฐ๊ตฌ์ ์ด์ ์ผ์ ์ ๋ณด๊ณ , ๊ทธ๋ ๋์ด ํจ๊ปํ ์ ์๋ ๊ฐ์ฅ ๊ธด ํด์์๊ฐ์ด ์ธ์ ์ธ์ง๋ฅผ ์ฐพ์ผ๋ ค๊ณ ํ๋ค. ๋์ด๊ณต์์์ ์ผํ๋ ๋ชจ๋ ์ฌ๋๋ค์ ์ด๋ค ๋์ด๊ธฐ๊ตฌ๊ฐ ์๋์ ์์ํ๊ธฐ 10๋ถ ์ ๋ถํฐ, ๋ชจ๋ ๋์ด๊ธฐ๊ตฌ๊ฐ ์๋์ ๋ฉ์ถ ํ 10๋ถ ํ๊น์ง๋ ์ด ์ ์๊ณ , ๊ทธ ๋๋จธ์ง ์ผ๊ณผ ์๊ฐ์๋ง ์ด ์ ์๋ค. ํ๋ฃจ ์ผ๊ณผ๋ฅผ ์์ํ๋ ์๊ฐ์ ์ค์ 10์์ด๊ณ , ์ผ๊ณผ๋ฅผ ๋ง์น๋ ์๊ฐ์ ์คํ 10์์ด๋ค. ์๋ฅผ ๋ค์ด ์ธ ๊ฐ์ ๋์ด๊ธฐ๊ตฌ๊ฐ ์๋ํ๋ ์๊ฐ์ด ๋ค์๊ณผ ๊ฐ๋ค๊ณ ํ๋ฉด, ๋์ด๊ธฐ๊ตฌ 1: ์ค์ 10์ 30๋ถ - ์คํ 1์ ๋์ด๊ธฐ๊ตฌ 2: ์คํ 7์ 00๋ถ -..
-
[Python] ๋ฐฑ์ค 19638 ์ผํฐ์ ๋ง๋ฒ์ ๋ฟ ๋ง์น (Heapq)๐ป Algorithm/Python 2022. 7. 2. 15:16
๐ ๋ฌธ์ ์ผํฐ๋ ๋ง๋ฒ ๋๊ตฌ๋ค์ ์ง๋๊ณ ์ฌํ์ ๋ ๋๋ ๊ฒ์ด ์ทจ๋ฏธ์ธ ์ ๋น์ด๋ค. ๊ฑฐ์ธ์ ๋๋ผ์ ๋์ฐฉํ ์ผํฐ๋ ์์ ๋ณด๋ค ํค๊ฐ ํฌ๊ฑฐ๋ ๊ฐ์ ๊ฑฐ์ธ๋ค์ด ์๋ค๋ ์ฌ์ค์ด ๋ง์์ ๋ค์ง ์์๋ค. ์ผํฐ๊ฐ ๊บผ๋ด ๋ค์ ๋ง๋ฒ ๋๊ตฌ๋ ๋ฐ๋ก ๋ง๋ฒ์ ๋ฟ ๋ง์น๋ก, ์ด ๋ฟ ๋ง์น์ ๋ง์ ์ฌ๋์ ํค๊ฐ ⌊ ๋ฟ ๋ง์น์ ๋ง์ ์ฌ๋์ ํค / 2 ⌋๋ก ๋ณํ๋ ๋ง๋ฒ ๋๊ตฌ์ด๋ค. ๋จ, ํค๊ฐ 1์ธ ๊ฒฝ์ฐ ๋ ์ค์ด๋ค ์๊ฐ ์์ด ๋ฟ ๋ง์น์ ์ํฅ์ ๋ฐ์ง ์๋๋ค. ํ์ง๋ง ๋ง๋ฒ์ ๋ฟ ๋ง์น๋ ํ์ ์ ํ์ด ์๋ค. ๊ทธ๋์ ์ผํฐ๋ ๋ง๋ฒ์ ๋ฟ ๋ง์น๋ฅผ ํจ์จ์ ์ผ๋ก ์ฌ์ฉํ๊ธฐ ์ํ ์ ๋ต์ ์๋ฆฝํ๋ค. ๋ฐ๋ก ๋งค๋ฒ ๊ฐ์ฅ ํค๊ฐ ํฐ ๊ฑฐ์ธ ๊ฐ์ด๋ฐ ํ๋๋ฅผ ๋๋ฆฌ๋ ๊ฒ์ด๋ค. ๊ณผ์ฐ ์ผํฐ๊ฐ ์๋ฆฝํ ์ ๋ต์ ๋ง๊ฒ ๋ง๋ฒ์ ๋ฟ ๋ง์น๋ฅผ ์ด์ฉํ๋ค๋ฉด ๊ฑฐ์ธ์ ๋๋ผ์ ๋ชจ๋ ๊ฑฐ์ธ์ด ์ผํฐ๋ณด๋ค ํค๊ฐ ์๋๋ก ํ ์ ์์๊น? ์ ๋ ฅ ์ฒซ ๋ฒ์งธ ..