๋ชฉ๋ก์ ์ฒด ๊ธ (1096)
KoreanFoodie's Study
์ธ์ ๊ฐ๋ถํฐ, ํ๋กํฌ์ฆ๋ฅผ ํ ๋ ๋ค์ด์ ๋ฐ์ง๋ฅผ ๊ฑด๋ด๋ ๊ฒ์ ๋ญ ์ฌ์ฑ๋ค์ ๋ก๋ง์ผ๋ก ์๋ฆฌ์ก์๋ค. ๋ค์ด์๋ชฌ๋๋ ์ธ์ ๋ถํฐ ์์ํ ์ฌ๋์ ์์ง์ด ๋์๋. ๋๋ 1947๋ . ๋จ์๊ณต์์ ์์ํ ์ฃผ์ผ๋ฆฌ ํ์ฌ์ธ ๋๋น์ด์ค๋ "A diamond is forever"์ด๋ผ๋ ๊ด๊ณ ์นดํผ๋ฅผ ์ ์ธ๊ณ์ ์ผ๋ก ํํธ์ํค๋ ๊ฒ์ ์ฑ๊ณตํ๋ค. ๊ด๊ณ ๊ณ์์ ์ ์ค๋ก ๋จ์ ์ด ์นดํผ๋, ๋ค์ด์๋ชฌ๋๊ฐ ์์ํ ์ฌ๋์ ์์ง์ผ๋ก ์๋ฆฌ์ก๋ ์ผ์ ํํํ ๊ณตํ์ ํ๋ค. ๋ฌผ๋ก ๊ทธ ์ด์ ์๋ ๋ค์ด์๋ชฌ๋๋ ๊ณ ๊ธ์ง ์ฌ์นํ์ด๊ธด ํ์ง๋ง. ๋์ฒด ๋ค์ด์๋ชฌ๋๊ฐ ๋น์ผ ์ด์ ๊ฐ ๋ญ๊น. ์, ๋ฌผ๋ก ๊ฒฝ์ ํ์์ ๋ฐฐ์ฐ๋ ์์์ ๊ณต๊ธ์ ์ด์ผ๊ธฐํ๊ณ ์ถ์ ๊ฑด ์๋๋ค. ๊ทธ๊ฑด ๋๋ฌด๋ ๋น์ฐํ ์ด์ผ๊ธฐ์ด๋๊น. ๋ค๋ง ๊ทธ ์์๊ฐ ์ด๋์ ์ฐฝ์ถ๋๋์ง ๊ถ๊ธํ์ ๋ฟ์ด๋ค. ์ ๋ค์ด์๋ชฌ๋๋ ๋น์ธ์ ธ์ผ๋ง ํ์๊น. ๊ฒฝ์ ํ์ ์ธ ๊ด์ ..
๋จธ๋๋ ์ ํ ํฌ ์ถ์ฒ ๋์ (๋์ ์ ๋ชฉ์ ๊ต๋ณด๋ฌธ๊ณ ๋งํฌ๋ฅผ ๊ฑธ์ด๋์์) : For Genie 1. ๋ณด๋ ์ํผ์ '๋' '๋' ์ด๋ผ๋ ๊ฒ ๋ฌด์์ธ์ง, '๊ฒฝ์ ์ ์์ '๋ ๋ฌด์์ธ์ง ๊ตฌ์ฒด์ ์ด๊ณ ํ์ค์ ์ผ๋ก ๊ณ ๋ฏผํ๊ฒ ํด์ฃผ๋ ์ต๊ณ ์ ์ ๋ฌธ ์์ . 1998๋ ์ ๋์จ ์ฑ ์ด ์์ง๋ ๋ฒ ์คํธ์ ๋ฌ์ ๋จธ๋ฌด๋ฅด๊ณ ์๋ ๊ฒ์๋ ์ด์ ๊ฐ ์๋ค. ๋ง์ฝ ์ฌํ ํฌ ๋์๋ก ๋จ ํ๊ถ๋ง ๊ณ ๋ฅผ ์ ์๋ค๋ฉด ์ฃผ์ ์์ด ๊ณ ๋ฅผ ์ฑ . 2. ๋, ์ผํ๊ฒ ํ๋ผ ์ํผ๊ฐ๋ฏธ ํฌ์์๋ก์ ํฌ์ ์ ๋ฌธ์๊ฐ ์ฝ๊ฒ ํฌ์๋ฅผ ์์ํ ์ ์๋๋ก ๋์์ฃผ๋ ์ฑ . ๊ธฐ๋ณธ์ ๋ง์ธ๋์ ๊ณผ ํฌ์์ ๋น์์ฑ์ ๋ํด ์คํํ ๋์. 3. ์๊ณจ์์ฌ์ ๋ถ์๊ฒฝ์ ํ ์์ฌ์ด์, ํฌ์์๋ก์๋ ์ฑ๊ณตํ ๋ฐ๊ฒฝ์ฒ ์ ํฌ์ ์ฒ ํ์ ๊ดํ ์ฑ . ํฌ์์ ๋ํ ๋ง์ธ๋์ ์ด์ธ์๋ ํ๊ตญ ์ฌํ์์ ์ฌํ ํฌ๋ฅผ ์ด๋ป๊ฒ ํ ๊ฒ์ธ์ง ํ์ค์ ์ผ๋ก ์ง์ด์ฃผ๋ ์ ์ด..
๊ธฐ์ ๋ฉด์ ๊ณผ ์ฝ๋ฉํ ์คํธ ์ค๋น๋ฅผ ์ํด ๊ผญ ์์์ผ ํ ๊ธฐ์ด ์๊ณ ๋ฆฌ์ฆ ๊ด๋ จ ๊ฐ๋ ๋ค๊ณผ ์ฝ๋๋ฅผ ์ ๋ฆฌํ๊ณ ์์ต๋๋ค. ๊ฐ ์ฃผ์ ๋ค์ GeeksForGeeks ์ Top 10 algorithms in Interview Questions ๊ธ์์ ๋ฐ์ทํ์์ต๋๋ค. ๋งํฌ๋ ๋ฆฌ์คํธ ๋ง์ (Add two numbers represented by linked lists) ๋งํฌ๋ ๋ฆฌ์คํธ๋ก ์ซ์๊ฐ ์ฃผ์ด์ก์ ๋, ๋ ๋ฆฌ์คํธ๋ฅผ ๋ํด ๋ค์๊ณผ ๊ฐ์ ๋ฆฌ์คํธ๋ฅผ ๋ฆฌํดํ๋ ํจ์๋ฅผ ๊ตฌํํด ๋ณด์. ํด๋น ํจ์๋ ์ฌ๊ท์ ์ผ๋ก ๊ตฌํํ ์๋ ์๊ณ , stack ์ ์ด์ฉํด ๊ตฌํํ ์๋ ์๋ค. ํน์, ๋งํฌ๋ ๋ฆฌ์คํธ๋ฅผ reverse ์ํจ ํ, loop ์ ๋๋ ค ๋ง์ ์ ํด๋ ๊ฐ์ ๊ฒฐ๊ณผ๋ฅผ ๊ตฌํ ์ ์๋ค. ์๋ ์ฝ๋๋ ๋งํฌ๋ ๋ฆฌ์คํธ๋ฅผ ์ญ์ ์ํจ ๋ฐฉ์์ ๊ตฌํํ ์ฝ๋์ด๋ค. #inc..
๊ธฐ์ ๋ฉด์ ๊ณผ ์ฝ๋ฉํ ์คํธ ์ค๋น๋ฅผ ์ํด ๊ผญ ์์์ผ ํ ๊ธฐ์ด ์๊ณ ๋ฆฌ์ฆ ๊ด๋ จ ๊ฐ๋ ๋ค๊ณผ ์ฝ๋๋ฅผ ์ ๋ฆฌํ๊ณ ์์ต๋๋ค. ๊ฐ ์ฃผ์ ๋ค์ GeeksForGeeks ์ Top 10 algorithms in Interview Questions ๊ธ์์ ๋ฐ์ทํ์์ต๋๋ค. ๋งํฌ๋ ๋ฆฌ์คํธ ์คํธ๋ง ๋น๊ต string ์ ๋งํฌ๋ ๋ฆฌ์คํธ๋ก ํํํ๋ค๊ณ ํ์๋, ๋ค์๊ณผ ๊ฐ์ด ์คํธ๋ง์ ๋น๊ตํ๋ ํจ์๋ฅผ ๊ตฌํํด ๋ณด์. ๋จ, ํฌ ํฌ์ธํฐ๋ฅผ ์ด์ฉํ์ฌ ์ํํ๋ค. #include #include #include struct Node { char data; Node* next; Node(char data) : data{data}, next{nullptr} {} }; struct List { List() : head{nullptr} {} void insert(cha..
๊ธฐ์ ๋ฉด์ ๊ณผ ์ฝ๋ฉํ ์คํธ ์ค๋น๋ฅผ ์ํด ๊ผญ ์์์ผ ํ ๊ธฐ์ด ์๊ณ ๋ฆฌ์ฆ ๊ด๋ จ ๊ฐ๋ ๋ค๊ณผ ์ฝ๋๋ฅผ ์ ๋ฆฌํ๊ณ ์์ต๋๋ค. ๊ฐ ์ฃผ์ ๋ค์ GeeksForGeeks ์ Top 10 algorithms in Interview Questions ๊ธ์์ ๋ฐ์ทํ์์ต๋๋ค. ๋ ธ๋ ์ญ์ (Linked List Node deletion) Singly Linked List ์์ ๋ ธ๋๋ฅผ ์ญ์ ํ ๋๋, ๊ฐ๋จํ๊ฒ ์ด์ ๋ ธ๋์ ๋ค์ ๋ ธ๋๋ฅผ ํ์ฌ ๋ ธ๋์ ๋ค์ ๋ ธ๋์ ์ฐ๊ฒฐ์์ผ์ฃผ๊ธฐ๋ง ํ๋ฉด ๋๋ค(prev->next = cur->next). ํน์, prev ๋ ธ๋ ํ๋๋ฅผ ์ด์ฉํด๋ ๋๋ค(prev->next = prev->next->next). void delete_node(int x) { if (!head) { std::cout data == x) { head ..
๊ธฐ์ ๋ฉด์ ๊ณผ ์ฝ๋ฉํ ์คํธ ์ค๋น๋ฅผ ์ํด ๊ผญ ์์์ผ ํ ๊ธฐ์ด ์๊ณ ๋ฆฌ์ฆ ๊ด๋ จ ๊ฐ๋ ๋ค๊ณผ ์ฝ๋๋ฅผ ์ ๋ฆฌํ๊ณ ์์ต๋๋ค. ๊ฐ ์ฃผ์ ๋ค์ GeeksForGeeks ์ Top 10 algorithms in Interview Questions ๊ธ์์ ๋ฐ์ทํ์์ต๋๋ค. ๋งํฌ๋ ๋ฆฌ์คํธ ์ ๋ ฌ ์ฝ์ (Linked List insert in sorted way) ์ ๋ ฌ๋ ๋งํฌ๋ ๋ฆฌ์คํธ์์, ์ฝ์ ์ ์ํํ ๋ ์ ๋ ฌ๋ ์ํ๋ฅผ ์ ์งํ๋ ค๋ฉด ์ด๋ป๊ฒ ํด์ผ ํ ๊น? 1. ๋งํฌ๋ ๋ฆฌ์คํธ๊ฐ ๋น์ด ์์ ๊ฒฝ์ฐ ์ฝ์ ๋๋ ๋ ธ๋๋ฅผ ํค๋๋ก ๋ง๋ ๋ค. 2. ์์๊ฐ ํ๋์ผ ๊ฒฝ์ฐ, ์ฝ์ ๋๋ ๋ ธ๋๋ฅผ ํค๋๋ก ๋ง๋ค๊ณ ๊ธฐ์กด ํค๋์ ์ฐ๊ฒฐํ๋ค. 3. ์์๊ฐ ์ฌ๋ฌ ๊ฐ์ผ ๊ฒฝ์ฐ, ์ํ๋ฅผ ํ๋ฉฐ ์๋ง์ ์์น์ ๋ผ์ ๋ฃ๋๋ค. #include #include #include struct Node {..
๋คํธ์ํฌ์ ๊ตฌ์ฑ ๋คํธ์ํฌ๋ LAN ๊ณผ WAN ์ผ๋ก ๊ตฌ์ฑ๋๋ค. LAN ์ ๋ก์ปฌ ์์ญ ๋คํธ์ํฌ์ด๊ณ , LAN ๊ณผ LAN ์ ์๋ ๊ฒ์ WAN ์ด๋ผ๊ณ ํ๋ค. ๋ณดํต LAN ๊ณผ LAN ์ฌ์ด๋ ๋ผ์ฐํฐ๋ฅผ ์ด์ฉํด ์ฐ๊ฒฐํ๋ค. ์ค์์น์ ๋ผ์ฐํฐ ๋คํธ์ํฌ์ ๊ธฐ๋ณธ ๊ตฌ์ฑ์ ์ค์์น์ ๋ผ์ฐํฐ์์ ๋์จ๋ค. ์ค์์น์ ๋ผ์ฐํฐ๋ ๋ ๋ค ์ค์์นญ(ํต์ ์ ์ฐ๊ฒฐ๋ ํฌํธ๋ก ์ฐ๊ฒฐํด ์ฃผ๋ ์ญํ )์ ์ํํ์ง๋ง, ๊ฐ์ฅ ํฐ ์ฐจ์ด๋, ๋ธ๋ก๋์บ์คํ ์ ๋ง๋๋ ๋ง์ง ์๋๋์ ์ฐจ์ด์ด๋ค. ์ค์์น๋ ๋ธ๋ก๋์บ์คํ ์ ์ํํ๊ณ , ๋ผ์ฐํฐ๋ ์ด๋ฅผ ์ฐจ๋จํ๋ค. ์ฆ, ์ค์์น๋ ๊ฐ์ ๋คํธ์ํฌ๋ฅผ ๋ฌถ์ด์ฃผ๊ณ , ๋ผ์ฐํฐ๋ ๋คํธ์ํฌ ์งํฉ์ ๋ถ๋ฆฌ์์ผ์ค๋ค๊ณ ์ดํดํ ์ ์๋ค. ์ฆ, ์ ์ธ๊ณ์ ๋คํธ์ํฌ๋ฅผ ์ค์์น๋ก ๊ตฌ์ฑํ๋ ๊ฒ์ ๋ถ๊ฐ๋ฅํ๋ค. ์๋ํ๋ฉด ํจํท์ ๋ธ๋ก๋์บ์คํ ํ ๋ ์ ์ธ๊ณ์ ๋ชจ๋ ์ปดํจํฐ์ ๋ํด ..
๊ธฐ์ ๋ฉด์ ๊ณผ ์ฝ๋ฉํ ์คํธ ์ค๋น๋ฅผ ์ํด ๊ผญ ์์์ผ ํ ๊ธฐ์ด ์๊ณ ๋ฆฌ์ฆ ๊ด๋ จ ๊ฐ๋ ๋ค๊ณผ ์ฝ๋๋ฅผ ์ ๋ฆฌํ๊ณ ์์ต๋๋ค. ๊ฐ ์ฃผ์ ๋ค์ GeeksForGeeks ์ Top 10 algorithms in Interview Questions ๊ธ์์ ๋ฐ์ทํ์์ต๋๋ค. ๋จ์ ์ (Articulation Edge) ๋จ์ ์ ๊ณผ ๋จ์ ์ ์ ๋น์ทํ ์๋ฆฌ๋ก ๊ตฌํ ์ ์๋ค. DFS ๋ฅผ ํตํด ๋ฐฉ๋ฌธ ๋ ธ๋์ ์์์, ํด๋น ๋ ธ๋๋ฅผ ํฌํจํ ์์ ๋ ธ๋๋ค์์ ๊ฐ์ฅ ๋จผ์ ๋ฐฉ๋ฌธํ ๋ ธ๋์ ์์(์ต์ ๋ฐฉ๋ฌธ ์์)๋ฅผ ์ ์ฅํ๋ค. ๊ทธ ํ, ํด๋น ๋ ธ๋์ ์ต์ ๋ฐฉ๋ฌธ ๊ฐ๋ฅ ์์๊ฐ ์ธ์ ๋ ธ๋์ ๋ฐฉ๋ฌธ ์์๋ณด๋ค ํด ๊ฒฝ์ฐ(์ฆ, DFS ๋ฐฉ์์ผ๋ก ํด๋น ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๋ ๊ณผ์ ์์ ๋ค๋ฅธ ๋ ธ๋์์ ํด๋น ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ ์ ์๋ ๊ฒฝ์ฐ) ํด๋น ์ฃ์ง๋ ๋จ์ ์ ์ด๋ผ๊ณ ํ ์ ์๋ค. ์ฝ๋๋ GeeksForG..
๊ธฐ์ ๋ฉด์ ๊ณผ ์ฝ๋ฉํ ์คํธ ์ค๋น๋ฅผ ์ํด ๊ผญ ์์์ผ ํ ๊ธฐ์ด ์๊ณ ๋ฆฌ์ฆ ๊ด๋ จ ๊ฐ๋ ๋ค๊ณผ ์ฝ๋๋ฅผ ์ ๋ฆฌํ๊ณ ์์ต๋๋ค. ๊ฐ ์ฃผ์ ๋ค์ GeeksForGeeks ์ Top 10 algorithms in Interview Questions ๊ธ์์ ๋ฐ์ทํ์์ต๋๋ค. Boggle : Find all possible words in a board of characters ๋ค์๊ณผ ๊ฐ์ ๋ณด๋๊ฐ ์๋ค๊ณ ๊ฐ์ ํ์๋, Dictionary์์ ์ฐ๋ฆฌ๊ฐ ์ํ๋ ๋จ์ด๋ฅผ ๋ณด๋๋ฅผ ํตํด ๋ง๋ค ์ ์๋์ง ์๋์ง ํ์ธํ๋ ์ฝ๋๋ฅผ ์ง ๋ณด์. ์ธํ๊ณผ ์์ํ์ ๋ค์๊ณผ ๊ฐ๋ค. ์ ์ฝ ์กฐ๊ฑด์, ๋ณด๋์์ ์ํ์ข์ฐ + ๋๊ฐ์ ์ด 8๊ฐ์ง ๋ฐฉํฅ์ผ๋ก ์ด๋ํ ์ ์๋ค๋ ๊ฒ๊ณผ, ๋ณด๋ ์์ ๋ฌธ์๋ฅผ ์ค๋ณตํด์ ๋ฐฉ๋ฌธํ๋ ๊ฒ์ ์๋๋ค๋ ๊ฒ์ด๋ค. ํด๋น ํจ์๋ DFS ๋ฐฉ์์ผ๋ก ๊ตฌํํด์ผ ํ๋ค...
๊ธฐ์ ๋ฉด์ ๊ณผ ์ฝ๋ฉํ ์คํธ ์ค๋น๋ฅผ ์ํด ๊ผญ ์์์ผ ํ ๊ธฐ์ด ์๊ณ ๋ฆฌ์ฆ ๊ด๋ จ ๊ฐ๋ ๋ค๊ณผ ์ฝ๋๋ฅผ ์ ๋ฆฌํ๊ณ ์์ต๋๋ค. ๊ฐ ์ฃผ์ ๋ค์ GeeksForGeeks ์ Top 10 algorithms in Interview Questions ๊ธ์์ ๋ฐ์ทํ์์ต๋๋ค. ์์์ ๋ ฌ (Topological Sort) ์์์ ๋ ฌ์ ์ ํฅ ๊ทธ๋ํ (DAG, Directed Acyclic Graph) ์์ ์ ํ๊ด๊ณ๋ฅผ ๊ณ ๋ คํ ์ ๋ ฌ ๋ฐฉ์์ด๋ค. ์ฆ, A -> B ์ ๊ด๊ณ๊ฐ ์๋ค๊ณ ํ์๋, ์์์ ๋ ฌ์ ํ๋ฉด ๋ฐ๋์ A ๊ฐ B ๋ณด๋ค ๋จผ์ ์ถ๋ ฅ๋๋ค. ์์์ ๋ ฌ์ ํ๊ธฐ ์ํด์๋ Incoming Edge ์ ๊ฐ์ด 0 ์ธ ๋ ์๋ค๋ถํฐ ์์๋๋ก ์ถ์ถํ์ฌ ์ถ๋ ฅํ๋ฉด ๋๋ค. ํน์ Vertex ๋ฅผ ์ถ์ถํ๋ฉด ํด๋น Vertex ๊ฐ ๊ฐ๋ฆฌํค๋ Vertex ์ Incoming Edge..