DFS
-
DFS/BFS๋ฅผ ์ด์ฉํ ์๊ณ ๋ฆฌ์ฆAlgorithm 2021. 6. 17. 11:48
์๋ ๋ฌธ์ ๋ ํ๋ก๊ทธ๋๋จธ์ค์์ ์ ๊ณตํ๋ ์ฌํ๊ฒฝ๋ก์ ๋ฌธ์ ์ ๋๋ค๐ง๐ป๐ป ๋ฌธ์ ์ ์ ์ฃผ์ด์ง ํญ๊ณต๊ถ์ ๋ชจ๋ ์ด์ฉํ์ฌ ์ฌํ๊ฒฝ๋ก๋ฅผ ์ง๋ ค๊ณ ํฉ๋๋ค. ํญ์ "ICN" ๊ณตํญ์์ ์ถ๋ฐํฉ๋๋ค. ํญ๊ณต๊ถ ์ ๋ณด๊ฐ ๋ด๊ธด 2์ฐจ์ ๋ฐฐ์ด tickets๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋ฐฉ๋ฌธํ๋ ๊ณตํญ ๊ฒฝ๋ก๋ฅผ ๋ฐฐ์ด์ ๋ด์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. ์ ํ์ฌํญ ๋ชจ๋ ๊ณตํญ์ ์ํ๋ฒณ ๋๋ฌธ์ 3๊ธ์๋ก ์ด๋ฃจ์ด์ง๋๋ค. ์ฃผ์ด์ง ๊ณตํญ ์๋ 3๊ฐ ์ด์ 10,000๊ฐ ์ดํ์ ๋๋ค. tickets์ ๊ฐ ํ [a, b]๋ a ๊ณตํญ์์ b ๊ณตํญ์ผ๋ก ๊ฐ๋ ํญ๊ณต๊ถ์ด ์๋ค๋ ์๋ฏธ์ ๋๋ค. ์ฃผ์ด์ง ํญ๊ณต๊ถ์ ๋ชจ๋ ์ฌ์ฉํด์ผ ํฉ๋๋ค. ๋ง์ผ ๊ฐ๋ฅํ ๊ฒฝ๋ก๊ฐ 2๊ฐ ์ด์์ผ ๊ฒฝ์ฐ ์ํ๋ฒณ ์์๊ฐ ์์๋ ๊ฒฝ๋ก๋ฅผ return ํฉ๋๋ค. ๋ชจ๋ ๋์๋ฅผ ๋ฐฉ๋ฌธํ ์ ์๋ ๊ฒฝ์ฐ๋ ์ฃผ์ด..
-
๊น์ด/๋๋น ์ฐ์ ํ์(DFS/BFS) - ํ๊ฒ ๋๋ฒAlgorithm 2021. 5. 6. 12:20
์๋ ๋ฌธ์ ๋ ํ๋ก๊ทธ๋๋จธ์ค์์ ์ ๊ณตํ๋ ์ฝ๋ฉํ ์คํธ > ๊น์ด/๋๋น ์ฐ์ ํ์(DFS/BFS) > ํ๊ฒ ๋๋ฒ (๊ณ ๋์ Kit)์ ๋ฌธ์ ์ ๋๋ค๐ง๐ป๐ป ๋ฌธ์ ์ ์ n๊ฐ์ ์์ด ์๋ ์ ์๊ฐ ์์ต๋๋ค. ์ด ์๋ฅผ ์ ์ ํ ๋ํ๊ฑฐ๋ ๋นผ์ ํ๊ฒ ๋๋ฒ๋ฅผ ๋ง๋ค๋ ค๊ณ ํฉ๋๋ค. ์๋ฅผ ๋ค์ด [1, 1, 1, 1, 1]๋ก ์ซ์ 3์ ๋ง๋ค๋ ค๋ฉด ๋ค์ ๋ค์ฏ ๋ฐฉ๋ฒ์ ์ธ ์ ์์ต๋๋ค. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 ์ฌ์ฉํ ์ ์๋ ์ซ์๊ฐ ๋ด๊ธด ๋ฐฐ์ด numbers, ํ๊ฒ ๋๋ฒ target์ด ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋ ์ซ์๋ฅผ ์ ์ ํ ๋ํ๊ณ ๋นผ์ ํ๊ฒ ๋๋ฒ๋ฅผ ๋ง๋๋ ๋ฐฉ๋ฒ์ ์๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. ์ ํ์ฌํญ ์ฃผ์ด์ง๋ ์ซ..