๋ชฉ๋ก2022/01 (32)
KoreanFoodie's Study
๋จธ๋๋ ์ ํ ํฌ ์ถ์ฒ ๋์ (๋์ ์ ๋ชฉ์ ๊ต๋ณด๋ฌธ๊ณ ๋งํฌ๋ฅผ ๊ฑธ์ด๋์์) : 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..
๊ธฐ์ ๋ฉด์ ๊ณผ ์ฝ๋ฉํ ์คํธ ์ค๋น๋ฅผ ์ํด ๊ผญ ์์์ผ ํ ๊ธฐ์ด ์๊ณ ๋ฆฌ์ฆ ๊ด๋ จ ๊ฐ๋ ๋ค๊ณผ ์ฝ๋๋ฅผ ์ ๋ฆฌํ๊ณ ์์ต๋๋ค. ๊ฐ ์ฃผ์ ๋ค์ GeeksForGeeks ์ Top 10 algorithms in Interview Questions ๊ธ์์ ๋ฐ์ทํ์์ต๋๋ค. ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ (Kruskal - Minimum Spanning Tree) ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ ํ๋ฆผ ์๊ณ ๋ฆฌ์ฆ๊ณผ ๋น์ทํ๊ฒ ์ต์ ์ ์ฅ ํธ๋ฆฌ๋ฅผ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ๋ค๋ง ์๋ฆฌ๋ ์กฐ๊ธ ๋ค๋ฅด๋ค. ๋จผ์ , ๋ชจ๋ Vertex ๋ค์ ๋ณ๋์ ์งํฉ์ผ๋ก ๋ง๋ ๋ค. ๊ทธ ํ, ๋ชจ๋ ์ฃ์ง๋ค์ ์ฐ์ ์์ ํ์ ๋ฃ๊ณ , ์ต์ ๊ฐ์ค์น๋ฅผ ๊ฐ์ง ๋ ์๋ค๋ถํฐ ๊บผ๋ด ๋ Vertex ๋ฅผ ์ด์ด์ค๋ค. ์ด๋, ๊ฐ์ ์งํฉ์ธ ๊ฒฝ์ฐ๋ ์ฐ๊ฒฐํ์ง ์๋๋ค. ์งํฉ์ด ๊ฐ์์ง๋ฅผ ํ๋ณํ๋ ๊ฒ์ Union-Find ๋ฅผ ์ด์ฉํด ๊ฒ์ฌํ๋ค...