์๋ฃ๊ตฌ์กฐ๋ ์ฌ๋ฌ ๋ฐ์ดํฐ๋ค์ ๋ฌถ์์ ์ ์ฅํ๊ณ ์ฌ์ฉํ๋ ๋ฐฉ๋ฒ์ ์ ์ํ ๊ฒ์ด๋ค.
๋๋ถ๋ถ์ ์๋ฃ๊ตฌ์กฐ๋ ํน์ ์ํฉ์ ๋์ธ ๋ฌธ์ ํด๊ฒฐ์ ํนํ๋์ด ์์ด ์ฌ๋ฌ ๊ตฌ์กฐ๋ฅผ ์๊ณ ์์ผ๋ฉด ๋น ๋ฅธ ํด๊ฒฐ์ ๋์์ด ๋๋ค.
๋ํ์ ์ธ ์๋ฃ๊ตฌ์กฐ๋ก๋ Stack, Queue, Tree, Graph๋ฑ์ด ์๋ค.
์คํ์ ์๋ค ํฌ๊ฐ๋ค ๋ฑ์ ๋ป์์ ์ง์ํ ์ ์๋ฏ ๋ฐ์ดํฐ๋ฅผ ์์๋๋ก ์๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค.
์คํํ ์๋ฃ๊ตฌ์กฐ๋ ์
๋ ฅ๊ณผ ์ถ๋ ฅ์ด ํ ๋ฐฉํฅ์ผ๋ก ์ด๋ฃจ์ด์ง๋ ์ ํ์ ์ ๊ทผ ๋ฐฉ์์ ๊ฐ์ง๊ณ ์์ผ๋ฉฐ ์ด๋ฅผ LIFO(Last In First Out) ๋๋ FILO(First In Last Out) ๋ผ๊ณ ๋ถ๋ฅด๊ธฐ๋ ํ๋ค.
์คํํ ์๋ฃ๊ตฌ์กฐ ๊ฐ์ ๊ฒฝ์ฐ์๋ ๋ธ๋ผ์ฐ์ ์ ๋ค๋ก๊ฐ๊ธฐ ์์ผ๋ก ๊ฐ๊ธฐ ๊ธฐ๋ฅ์ ๊ตฌํํ ๋ ์ฌ์ฉ๋๊ณ ์๋ค.
ํ๋ ์ค์์ ๊ธฐ๋ค๋ฆฌ๋ค, ๋๊ธฐ ํ๋ ฌ ์ด๋ผ๋ ๋ป์์๋ ์ง์ํ ์ ์๋ฏ ๋ฐ์ดํฐ๊ฐ ๋ค์ด๊ฐ ์์๋๋ก ์ฒ๋ฆฌํ๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค.
ํํ ์๋ฃ๊ตฌ์กฐ๋ ์คํํ๊ณผ ๋ฐ๋๋๋ ๊ฐ๋
์ ๊ฐ์ง๊ณ ์๋๋ฐ, ๋จผ์ ๋ค์ด๊ฐ ๋ฐ์ดํฐ๊ฐ ๋จผ์ ๋์ค๋ ์ด ์๋ฃ๊ตฌ์กฐ๋ฅผ LILO(Last In Last Out) ๋๋ FIFO(First In First Out)๋ผ๊ณ ๋ถ๋ฅด๊ธฐ๋ ํ๋ค.
ํ๋ ์์
์ดํ์์ ์์๋๋ก ๋
ธ๋๋ฅผ ๋ค์๋ ์ฌ์ฉํ๊ธฐ๋ ํ๊ณ ์ปดํจํฐ์์ ๊ด๋ฒ์ํ๊ฒ ์ฌ์ฉ๋๋๋ฐ,
์ปดํจํฐ์์ ์์
ํ ๋ฌธ์๋ฅผ ์ถ๋ ฅํ๋ฉด ์ฐจ๋ก๋๋ก ํ์ ๋ณด๋ด๊ณ ํ๋ฆฐํฐ์์ ์ฐจ๋ก๋๋ก ํ์ ๋ฌธ์๋ฅผ ์ถ๋ ฅํ๋ค.
์ด์ฒ๋ผ ์์๋ก ์์ ํ๋ฅผ ์ ์ฅํ๋ ๊ณณ์ Buffer(๋ฒํผ)๋ผ๊ณ ํ๋ฉฐ, ์ด๋ CPU์ ์ด๋ฒคํธ๋ ๋ถ๊ท์น์ ์ผ๋ก ์ฒ๋ฆฌ๋๋ ๋ฐ๋ฉด, ๋ณดํต ์ด๋ฒคํธ๋ฅผ ์ฒ๋ฆฌํ๋ ์ฅ์น(ํ๋ฆฐํธ ๋ฑ)์ ์ผ์ ํ ์๋๋ก ์ด๋ฒคํธ๋ฅผ ์ฒ๋ฆฌํ๊ธฐ์ ์ด ๊ฐ๊ฒฉ์ ๋ง์ถ๊ธฐ ์ํด์ ๋ฒํผ๋ฅผ ์ฌ์ฉํ๋ค.
๊ทธ๋ํํ ์๋ฃ๊ตฌ์กฐ์์๋ ๊ฐ ์๋ฃ๋ฅผ ์ ์ (Vertex)์ด๋ผ ํ๊ณ , ๊ฐ ์ ์ ๊ฐ ์ฐ๊ฒฐ์ด ๋์ด ์์ผ๋ฉด ์ง์ ์ ๊ด๊ณ๋ผ๊ณ ํ๊ณ ์ด ์ฐ๊ฒฐ์ ๊ฐ์ (Edge)์ด๋ผ ํ๋ค. ์ง์ ์ฐ๊ฒฐ์ด ์๋๋ผ๋ ๋ค๋ฅธ ์ ์ ์ ๊ฑฐ์ณ์ ์ฐ๊ฒฐ ๋๊ธฐ๋ง ํ๋ฉด ๊ฐ์ ์ ๊ด๊ณ๋ผ๊ณ ํ๋ค.
์ฌ๊ธฐ์ ๊ฐ์ ์ ์ฐ๊ฒฐ๋์ด ์์๋ง ํ์ธํ ์ ์๊ณ ์ ์ ๊ฐ ์ฐ๊ฒฐ์ ๋๊ฐ ์ด๋ป๊ฒ ๋๋์ง์ ๋ํ ์ ๋ณด๋ ํฌํจํ๊ณ ์์ง ์๋ค.
์ด๋ ๊ฒ ์ถ๊ฐ ์ ๋ณด๊ฐ ์๋ ๊ทธ๋ํํ ์๋ฃ๊ตฌ์กฐ๋ฅผ ๋น๊ฐ์ค์น ๊ทธ๋ํ๋ผ๊ณ ํ๋ค.
์ด์ ๋ฐ๋๋ก ์ฐ๊ฒฐ ์ ๋ณด๊ฐ ์๋ ๊ทธ๋ํ๋ฅผ ๊ฐ์ค์น ๊ทธ๋ํ๋ผ ํ๋ค.
๋ฌด๋ฐฉํฅ ๊ทธ๋ํ(Undirected Graph) - ์๋ก ์ค๊ณ ๊ฐ ์ ์๋ ๊ทธ๋ํ๋ฅผ ๋ฌด๋ฐฉํฅ ๊ทธ๋ํ๋ผ ํ๊ณ , ์ด์ ๋ฐ๋๋๋ ๊ฐ๋ ์ด ์ผ๋ฐฉํตํ์ผ๋ก ์ค๋ช ํ ์ ์๋ ๋จ๋ฐฉํฅ ๊ทธ๋ํ(Directed Graph)์ด๋ค.
์ง์ ์ฐจ์(In-degree), ์ง์ถ ์ฐจ์(Out-degree) - ํ ์ ์ ์ ์ง์ ํ๋ ๊ฐ์ ๊ณผ ์ง์ถํ๋ ๊ฐ์ ์ด ๋ช๊ฐ์ธ์ง ํ๊ธฐํ๋ค.
์ธ์ (Adjacency) - ๋ ์ ์ ์ด ์ง์ ์ ์ผ๋ก ์ฐ๊ฒฐ๋์ด ์์ผ๋ฉด ์ธ์ ํ๋ค๊ณ ํ๋ค.
์๊ธฐ ๋ฃจํ(Self-loop) - ํ ์ ์ ์์ ์ง์ถํ ๊ฐ์ ์ด ์์ ์๊ฒ ๋์์ ์ง์ ํ๋ ๊ฒฝ์ฐ ๊ทธ ์ ์ ์ ์๊ธฐ ๋ฃจํ๋ฅผ ๊ฐ์ก๋ค๊ณ ํ๋ค.
์ธ์ดํด (Cycle) - ํ ์ ์ ์์ ์ถ๋ฐํด ๋ค๋ฅธ ์ ์ ์ ๊ฑฐ์ณ ๋ค์ ์ถ๋ฐํ ์ ์ ์ผ๋ก ๋์์ฌ ์ ์๋ค๋ฉด, ์ฌ์ดํด์ด ์กด์ฌํ๋ ๊ทธ๋ํ๋ผ ํ๋ค.
์ธ์ ํ๋ ฌ์ ์ ์ ๊ฐ ์ธ์ ํ๋ค๋ฉด 1, ์๋๋ผ๋ฉด 0์ผ๋ก ํ๊ธฐํ๋ ์ผ์ข
์ ํ์ด๋ค.
๋ง์ฝ ๊ฐ์ค์น ๊ทธ๋ํ๋ผ๋ฉด 1 ๋์ ์ ์๋ฏธํ ์ ๋ณด๊ฐ ๋ค์ด๊ฐ ์ ์๋ค.
์ธ์ ํ๋ ฌ์ ๋ ์ ์ ๊ฐ ๊ด๊ณ๋ฅผ ํ์ธํ ๋ ์ฉ์ดํ๋ฉฐ ๊ฐ์ฅ ๋น ๋ฅธ ๊ฒฝ๋ก๋ฅผ ์ฐพ์๋ ์ฃผ๋ก ์ฌ์ฉ๋๋ค.
์ธ์ ๋ฆฌ์คํธ๋ ์ ์ ์ด ์ด๋ค ์ ์ ๊ณผ ์ธ์ ํ์ง ๋ฆฌ์คํธ ํํ๋ก ํ๊ธฐํ๋ฉฐ ์ธ์ ํ ์ ์ ๋ง ํ๊ธฐ ๋๊ธฐ์ ๋ชจ๋ ์ ์ ๊ณผ์ ๊ด๊ณ๋ฅผ ํํํ๋ ์ธ์ ํ๋ ฌ์ ๋นํด ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํจ์จ์ ์ผ๋ก ์ฌ์ฉํ ์ ์๋ค.
ํธ๋ฆฌ ๊ตฌ์กฐ๋ ๋ฌด๋ฐฉํฅ ๊ทธ๋ํ์ ํ ๊ตฌ์กฐ๋ก ๋ฟ๋ฆฌ๋ถํฐ ๊ฐ์ง ๋ป์ด๋๊ฐ๋ ๋ชจ์ต์ด ๋ฎ์๋ค๊ณ ํด์ ํธ๋ฆฌ ๊ตฌ์กฐ๋ผ๊ณ ํ๋ค.
ํธ๋ฆฌ ๊ตฌ์กฐ๋ ๋ฐ์ดํฐ๊ฐ ๋ฐ๋ก ์๋ ์๋ ํ๋ ์ด์์ ๋ฐ์ดํฐ์ ๋ฌด๋ฐฉํฅ์ผ๋ก ์ฐ๊ฒฐ๋ ๊ณ์ธต์ ์๋ฃ๊ตฌ์กฐ์ด๋ฉฐ, ํ ๋ฐ์ดํฐ ๋ค์ ์ฌ๋ฌ ๋ฐ์ดํฐ๊ฐ ์กด์ฌํ ์ ์๋ ๋น์ ํ ๊ตฌ์กฐ์ด๋ค.
ํธ๋ฆฌ๊ตฌ์กฐ๋ ์๋๋ก๋ง ๋ป์ด ๋๊ฐ๊ธฐ์ ์ธ์ดํด์ ์๋ค.
ํธ๋ฆฌ ๊ตฌ์กฐ์์ ๋ฐ์ดํฐ๋ฅผ ๋
ธ๋(Node)๋ผ๊ณ ์นญํ๋ฉฐ ๋ฃจํธ(Root)๋ผ๋ ์ต์์ ๋
ธ๋๋ก๋ถํฐ ์ฌ๋ฌ ๋ฐ์ดํฐ๋ฅผ ๊ฐ์ ์ผ๋ก ์ฐ๊ฒฐํ๋ค.
๊ทธ๋ฆฌ๊ณ ๋๊ฐ์ ๋
ธ๋๊ฐ ์ํ๋ก ์ฐ๊ฒฐ๋๋ฉด ๋ถ๋ชจ์์ ๊ด๊ณ๋ฅผ ๊ฐ์ง๋ฉฐ ์์์ด ์๋ ๋
ธ๋๋ ๋ฆฌํ(Leaf)๋
ธ๋๋ผ๊ณ ํ๋ค.
๊น์ด(Depth) - ํธ๋ฆฌ ๊ตฌ์กฐ์์๋ ๋ฃจํธ๋ก ๋ถํฐ ํ์ ๊ณ์ธต์ ํน์ ๋
ธ๋๊น์ง์ ๊น์ด๋ฅผ ํํํ ์ ์๋ค.
๋ฃจํธ๋ฅผ ๊ธฐ์ค์ผ๋ก 0์ด๊ณ , ์์์ผ๋ก ๋ด๋ ค๊ฐ๋๋ง๋ค 1์ฉ ๋ํด์ง๋ค.
๋ ๋ฒจ(Level) - ํธ๋ฆฌ๊ตฌ์กฐ์์ ๊ฐ์ ๊น์ด๋ฅผ ๊ฐ์ง๊ณ ์๋ ๋
ธ๋๋ฅผ ๋ฌถ์ด ๋ ๋ฒจ๋ก ํํ ํ ์ ์๋ค.
๊น์ด๊ฐ 0์ธ ๋ฃจํธ๋ Level 1์ด๋ฉฐ ๊น์ด๊ฐ ๊น์ด ์ง์๋ก ํ๋จ๊ณ ์ฉ ๋ ๋ฒจ์ด ์ฌ๋ผ๊ฐ๋ฉฐ, ๊ฐ์ ๋ ๋ฒจ์ ๋
ธ๋๋ฅผ ํ์ (Siblings)๋
ธ๋๋ผ๊ณ ํ๋ค.
DOM์์๋ ๊ฐ์ ๋ถ๋ชจ๋ฅผ ๊ฐ์ง๊ณ ์์ด์ผ ํ์ ๋ ธ๋๋ก ๋ณธ๋ค.
๊ณ ๋ก DOM์์ ํ์ ๋ ธ๋๋ DOM์ ์ ์์์๋ ํ์ ๋ ธ๋์ด๊ณ ํธ๋ฆฌํ ์๋ฃ๊ตฌ์กฐ์ ์ ์์์๋ ํ์ ๋ ธ๋๊ฐ ๋๋ ๊ฒ์ด๋ค.
๋ค๋ง ๊ฐ์ ๋ ๋ฒจ์ด๋ ๋ค๋ฅธ ๋ถ๋ชจ๋ฅผ ๊ฐ์ง ๋ ธ๋ ๊ฐ์ ๊ฒฝ์ฐ๋ DOM์ ์ ์์์๋ ํ์ ๋ ธ๋๊ฐ ์๋๊ณ ํธ๋ฆฌํ ์๋ฃ๊ตฌ์กฐ์ ์ ์์์๋ ํ์ ๋ ธ๋์ด๋ค.
๋์ด(Height) - ํธ๋ฆฌ ๊ตฌ์กฐ์์ ๋ฆฌํ ๋
ธ๋๋ฅผ ๊ธฐ์ค์ผ๋ก ๋ฃจํธ๊น์ง์ ๋์ด๋ฅผ ๊ตฌํ ์ ์๋ค.
๋ฆฌํ๊ฐ ์ ๊ฐ๊ฐ ๊ธฐ์ค์ด ๋๋๋ฐ ์์์ด ์๋ ๋ถ๋ชจ ๋
ธ๋๋ ๊ฐ์ฅ ๋์ด ์๋ ์์์ ๋์ด์ +1 ํ ๋์ด๋ฅผ ๊ฐ์ง๋ค.
์๋ธ ํธ๋ฆฌ(Sub-tree) - ๋ฃจํธ๋ก๋ถํฐ ๋์ค๋ ํฐ ํธ๋ฆฌ ๋ด๋ถ์ ํธ๋ฆฌ ๊ตฌ์กฐ๋ฅผ ๊ฐ์ถ ์์ ํธ๋ฆฌ๋ฅผ ์๋ธ ํธ๋ฆฌ๋ผ ํ๋ค.
์ด์ง ํธ๋ฆฌ๋ ํจ์จ์ ์ธ ๊ฒ์์ ์ํด ์ ์๋ ํธ๋ฆฌ ๊ตฌ์กฐ์ด๋ค.
์ด์ง ํธ๋ฆฌ๋ ์์ ๋
ธ๋๊ฐ ์ต๋ 2๊ฐ์ธ ๋
ธ๋๋ค๋ก ๊ตฌ์ฑ๋ ํธ๋ฆฌ์ด๊ณ ์ด ๋๊ฐ์ ์์ ๋
ธ๋๋ ์ผ์ชฝ, ์ค๋ฅธ์ชฝ ์์ ๋
ธ๋๋ก ๋๋ ์ ์๋ค.
์ด์ง ํธ๋ฆฌ๋ ์๋ฃ์ ์ฝ์
, ์ญ์ ๋ฐฉ๋ฒ์ ๋ฐ๋ผ ์ ์ด์ง ํธ๋ฆฌ, ์์ ์ด์ง ํธ๋ฆฌ, ํฌํ ์ด์ง ํธ๋ฆฌ๋ก ๋๋ ์ ์๋ค.
์ด๋ฌํ ํน์ง ๋์ ์ด์ง ํ์ ํธ๋ฆฌ๋ ํ์ชฝ์ผ๋ก ๋ชฐ๋ฆด ์ ์๋ค.
ํ์ชฝ์ผ๋ก ๋ชฐ๋ฆด ๊ฒฝ์ฐ ํ์ ์๊ฐ์ด ๋ ์ค๋ ๊ฑธ๋ฆด ์ ์์ผ๋ ์ฌ์กฐ์ ๊ณผ์ ์๊ณ ๋ฆฌ์ฆ์ ์ถ๊ฐ ํ ์ ์๋ค.
๊ทธ๋ํํ๊ณผ ํธ๋ฆฌํ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ตํ๋ค.
๋๊ด์ ๋ถ๋ซํ ๋๊ธฐ์ ๋ฌธ์ ๋ฅผ ํ๋๋ง ๋์ ธ์ฃผ๋ ๋ฐฉ์์ผ๋ก ๋์์คฌ๋ค.
ํ ์ด 1๋ฒ ํ์๋ค!
๋ด์ผ ๊ธ์์ผ
์ตํ๋๋ฐ ์๊ฐ์ด ํ์ํ ๊ฒ ๊ฐ๋ค.
์ฌ๊ทํจ์ ๋ค์์ ํ์ด๋์ค๋ ์ด ๋ฌด์๋ฌด์ํ ๋
์๋ค.
๋ด์ผ ๊ธ์์ผ์ด๊ณ ๊ทธ ๋ค์ ๋ ์ ํ ์์ผ์ด๋ ์กฐ๊ธ ์ฌ์ ๋ฅผ ๊ฐ์ง๊ณ ์ ๋ฆฌํด๋ณด๋ ์๊ฐ์ ๊ฐ์ ธ์ผํ ๊ฒ ๊ฐ๋ค.
์ด ์์ค์ ์ฌ์ ์ฐพ๋ ๋๊นจ์ง ๋จธ๋ฆฌ์ ์์ ์
์ด์ ์ ๋ฐฐ์ด ๋ฉ์๋ push, pop ๊ฐ์ ๊ฒ๋ค ์ ๋ฆฌํ๋ฉด์ ์คํํ์ด๋ ํํ์ ์กฐ๊ธ ์ ๋ฆฌํด๋์ ์ค๋ ๋ค์ ๋ง๋ฌ์๋ ๋ถ๋ด์ด ๋ํ๋ค.
์์ฃผ ์นญ์ฐฌํด ๊ณผ๊ฑฐ์ ๋!