- ์ด๋ถํ์
- ๋ฐฑ์๋ ํ๋ฆฌ์จ๋ณด๋ฉ
- ๊ฐ์ฅ๊ฐ๊น์ด๊ณตํต์กฐ์
- ์ํฐ๋
- ๋นํธ๋งต
- ์น๋ฆฐ์ด
- Union-Find
- ํธ๋ฆฌ
- ์นด์นด์ค ์ฝํ
- ์ฌ๊ท
- LCs
- ์ฌ๋ผ์ด๋ฉ ์๋์ฐ
- ์์ฝ๋
- ์๊ณ ๋ฆฌ์ฆ
- golang
- ๋์ ํ๋ก๊ทธ๋๋ฐ
- js
- ๋ค์ต์คํธ๋ผ
- ์นด์นด์ค2021
- DP
- DFS
- nestjs
- C++
- Python
- go
- ๋ฐฑ์ค
- ํ๋ก๊ทธ๋๋จธ์ค
- ๋นํธ๋ง์คํน
- BFS
- ํ๋ฆฌ์จ๋ณด๋ฉ
- Today
- Total
Hello Ocean! ๐ผ
[์ฑ ์ฝ๊ธฐ] ์ค๋ธ์ ํธ_01 ๊ฐ์ฒด, ์ค๊ณ ๋ณธ๋ฌธ
https://jojoldu.tistory.com/609
ํฅ๋ก๋์ ๊ธ์ ์ถ์ฒ๋์ด ์๋ ์ฑ ์ ํ ๊ถ ๋น๋ ธ๋ค.
๋ฐฑ์๋ ํ๋ฆฌ์จ๋ณด๋ฉ์ ํ๋ฉฐ, "๊ฐ์ฒด์งํฅ์ด๋ ๋ญ๊น"์ ๋ํ ๊ณ ๋ฏผ์ ๋ค์ ํ๊ฒ๋์๋ค.
๋ฐฐ์์ ์ ์ฐ๊ณ ์๋ค๊ณ ์๊ฐํ์ง๋ง, ์ค์ ๋ก ์ ๋ชฉํ๋ ค๊ณ ํ๋ ๋จธ๋ฆฌ๊ฐ ์ํ ๋ค.
๊ฐ์ฒด์งํฅ์ด๋ ๋ญ๊น? ๊ทธ ํด๋ต์ ์ป์ ์ ์์๊น ํ์ฌ ์ด ์ฑ ์ ์ฝ์ผ๋ ค๊ณ ํ๋ค.
์์ธ์ ์ ์๋์๊ด์์ ์ฑ
์ ๋น๋ ธ๋ค. ๋์๊ด ๋ง์ธ
๋ค์ด๊ฐ๋ฉฐ_ ํ๋ก๊ทธ๋๋ฐ ํจ๋ฌ๋ค์
ํ๋ก๊ทธ๋๋ฐ ํจ๋ฌ๋ค์์ ๊ฐ๋ฐ์ ๊ณต๋์ฒด๊ฐ ๋์ผํ ํ๋ก๊ทธ๋๋ฐ ์คํ์ผ๊ณผ ๋ชจ๋ธ์ ๊ณต์ ํ ์ ์๊ฒ ํ๋ค.
์ด๋ก์จ ๋ถํ์ํ ์๊ฒฌ ์ถฉ๋์ ๋ฐฉ์งํ๊ณ , ๋์ผํ ๊ท์น๊ณผ ๋ฐฉ๋ฒ์ ๊ณต์ ํ๋ ๊ฐ๋ฐ์๋ก ์ฑ์ฅํ ์ ์๋๋ก ํ๋ค.
์ด ์ฑ ์, ๊ฐ์ฒด์งํฅ ํจ๋ฌ๋ค์์ ๋ํ ์ฑ ์ด๋ค.
์ฐ๋ฆฌ๊ฐ ๊ฐ์ฒด์งํฅ ํจ๋ฌ๋ค์์ ๋ํด ์ด๋์ ๋ ์ ์ฌํ ๊ทธ๋ฆผ์ ๊ทธ๋ฆด ์ ์๋ ๊ธฐ๋ฐ์ ์ ๊ณตํ๊ณ ,
์ด๋์ ๋ ๋์ผํ ๊ท์น๊ณผ ํ์ค์ ๋ฐ๋ผ ํ๋ก๊ทธ๋๋ฐํ ์ ์๋๋ก ํ๋ค.
CHAPTER 01_ ๊ฐ์ฒด, ์ค๊ณ
์ฑ ์์๋ ํฐ์ผ ํ๋งค ์ ํ๋ฆฌ์ผ์ด์ ์ ์์ ๋ก ๋ค์ด ์ฝ๋์ ํจ๊ป ์ค๋ช ํ๊ณ ์๋ค.
ํต์ฌ : ์ด๋ป๊ฒ ๋ณ๊ฒฝํ๊ธฐ ์ฌ์ด ์ฝ๋๋ฅผ ์์ฑํ ์ ์์๊น?
์ธํฐํ์ด์ค(interface)์ ๊ตฌํ(implementation)
๊ฐ์ฒด๋ฅผ ์ธํฐํ์ด์ค์ ๊ตฌํ์ผ๋ก ๋๋๊ณ , ์ธํฐํ์ด์ค๋ง์ ๊ณต๊ฐ
→ ๊ฐ์ฒด ์ฌ์ด์ ๊ฒฐํฉ๋๋ฅผ ๋ฎ์ถ๊ณ ๋ณ๊ฒฝํ๊ธฐ ์ฌ์ด ์ฝ๋๋ฅผ ์ค๊ณํ๊ธฐ ์ํ ๊ธฐ๋ณธ ์์น์ด๋ค.
์ธํฐํ์ด์ค : ์ธ๋ถ์์ ์ ๊ทผ ๊ฐ๋ฅํ ์์ญ
๊ตฌํ : ์ธ๋ถ์์ ์ ๊ทผ์ด ๋ถ๊ฐ๋ฅํ ์์ญ (์์ธ ๋ด์ฉ)
A๊ฐ์ฒด๊ฐ B๊ฐ์ฒด๋ฅผ ์ด์ฉํ ๋, ๋ด๋ถ์ ์ด๋ค ํ๋๋ฅผ ํฌํจํ๊ณ ์๋์ง๋ ๋ชฐ๋ผ๋ ๋๊ณ ,
์ค์ง ์ธํฐํ์ด์ค์๋ง ์์กดํ๋ค.
์บก์ํ์ ๋ชฉ์
๊ฐ ๊ฐ์ฒด๋ค์ ์บก์ํ๋ฅผ ํตํด, ๋ด๋ถ ๊ตฌํ์ ์ธ๋ถ์ ๋ ธ์ถํ์ง ์๊ณ ์์จ์ฑ์ ๋ ์ ์๋ค.
→ ์์ ์ ๋ฌธ์ ๋ฅผ ์ค์ค๋ก ํด๊ฒฐํ ์ ์๋ค.
→ ๊ฐ์ฒด ์ค์ค๋ก ์์ ์ ๋ฐ์ดํฐ๋ฅผ ์ฑ ์์ง ์ ์๋ค.
์ ์ฐจ์งํฅ VS ๊ฐ์ฒด์งํฅ
์ ์ฐจ์งํฅ : ์ฑ ์(๊ธฐ๋ฅ)์ด ํ ๊ณณ์ ์ง์ค
- ํ๋ก์ธ์ค / ๋ฐ์ดํฐ๊ฐ ๋ณ๊ฐ๋ก ์กด์ฌ
- ๋ชจ๋ ์ฒ๋ฆฌ๊ฐ ํ๋์ ํด๋์ค(ํ๋ก์ธ์ค)์ ์์กดํ๊ณ , ๋๋จธ์ง๋ ๊ทธ์ ๋ฐ์ดํฐ ์ญํ ์ด๋ค.
- ๋ฐ์ดํฐ๋ ๋ชจ๋ ์๋์ ์ธ ์กด์ฌ์ด๋ค.
- ํด๋์ค ํ๋๋ฅผ ์์ ํ๊ธฐ ์ํด ์ฌ๋ฌ ํด๋์ค๋ฅผ ์์ ํด์ผํ๋ค.
- ํ๋ก์ธ์ค๊ฐ ํ์ํ ๋ชจ๋ ๋ฐ์ดํฐ์ ์์กดํ๊ธฐ ๋๋ฌธ์ด๋ค.
→ ๊ฐ ๊ฐ์ฒด๊ฐ ์์ ์ ๋ฐ์ดํฐ๋ฅผ ์ค์ค๋ก ์ฒ๋ฆฌํ๋๋ก ํ๋ก์ธ์ค์ ์ผ๋ถ๋ฅผ ์ด๋ํ ์ ์๋ค. (๊ฐ์ฒด์งํฅ์ผ๋ก ๊ฐ๋ ๊ธธ)
๊ฐ์ฒด์งํฅ : ์ฑ ์์ด(๊ธฐ๋ฅ) ์ฌ๋ฌ ๊ฐ์ฒด์ ๋ถ์ฐ
- ํ๋ก์ธ์ค / ๋ฐ์ดํฐ๊ฐ ํจ๊ป ์กด์ฌ
- A๊ฐ์ฒด์ ๊ด๋ จ๋ ํ๋ก์ธ์ค๋ A๊ฐ์ฒด ์์ ์กด์ฌ
- ์บก์ํ๋ฅผ ์ด์ฉํ๋ค.
- ๋ถํ์ํ ์์กด์ฑ์ด ์ ๊ฑฐ๋จ์ผ๋ก ์ธํด, ๊ฒฐํฉ๋๊ฐ ๋ฎ์์ง๋ค
๊ฐ์ฒด
ํ์ค์์ ์๋์ ์ธ ๊ฐ์ฒด์ผ์ง๋ผ๋, ๊ฐ์ฒด์งํฅ ์ธ๊ณ์์ ๋ฅ๋์ ์ด๊ณ ์์จ์ ์ธ ์กด์ฌ์ด๋ค.
๊ฐ์ฒด์งํฅ์์ ๊ฐ ๊ฐ์ฒด๋ค์ ํ์ค๊ณผ ๋น์ทํ๊ฒ ์ค๊ณํด์ผ ํ๋ค๊ณ ์๊ฐํ ์ ์๋ค.
ํ์ค์์ ๋๋ถ๋ถ์ ๊ฐ์ฒด๋ค์, ์ธ๊ฐ ์์ด๋ ์๋์ ์ธ ์กด์ฌ์ด๋ค. (์ธ๊ฐ์์ด๋ ์๋ฌด ์ผ๋ ์ผ์ด๋์ง ์๋๋ค.)
ํ์ง๋ง, ๊ฐ์ฒด์งํฅ์์์ ๊ฐ์ฒด๋ค์ ๋ฅ๋์ ์ด๊ณ ์์จ์ ์ด๋ค.
์์ธํ์ ๊ด์ ์์ ์ํํธ์จ์ด๋ฅผ ์๋ฌผ๋ก ์๊ฐํ์.
๊ฐ์ฒด์งํฅ ์ค๊ณ์ ํต์ฌ
ํด๋์ค๋ฅผ ์ค๊ณํ๋ ๊ฒ์ด ์๋, ๊ฐ์ฒด๋ฅผ ๋จผ์ ์๊ฐํด๋ณด๊ณ ์ดํ์ ๊ฐ์ฒด๋ค์ ํด๋นํ๋ ํด๋์ค๋ฅผ ๊ณ ๋ฏผํ๋ ๊ฒ.
์บก์ํ๋ฅผ ํตํด ์ ์ ํ ๊ฐ์ฒด์ ์ ์ ํ ์ฑ ์์ ํ ๋นํ๋ ๊ฒ
๋ถํ์ํ ์์กด์ฑ์ ์ ๊ฑฐํด ๊ฐ์ฒด ์ฌ์ด์ ๊ฒฐํฉ๋๋ฅผ ๋ฎ์ถฐ๋ผ. = ์ต์ํ์ ์์กด์ฑ๋ง ๋จ๊ฒจ๋ผ.
์ด๋ป๊ฒ?
์บก์ํํด๋ผ!
์ค๊ณ
์ค๊ณ๋ ์ฝ๋๋ฅผ ๋ฐฐ์นํ๋ ๊ฒ์ด๋ค.
์ข์ ์ค๊ณ?
์ค๋์ ์๊ตฌ ๊ธฐ๋ฅ์ ์จ์ ํ ์ํํ๋ฉด์, ๋ด์ผ์ ๋ณ๊ฒฝ์ ๋งค๋๋ฝ๊ฒ ์์ฉํ ์ ์๋ ์ค๊ณ์ด๋ค.
๋ณ๊ฒฝ์ ๋งค๋๋ฝ๊ฒ ์์ฉํ๋ค?
์ดํดํ๊ธฐ ์ฌ์ด ์ฝ๋ -> ์์กด์ฑ์ด ์ ์ ์ฝ๋๋ฅผ ๋งํ๋ค.
์ ํ๋ฆฌ์ผ์ด์ ์ ์ฌ๋ฌ ๊ฐ์ ๊ฐ์ฒด๋ก ๊ตฌ์ฑ๋๊ณ ,
์ ํ๋ฆฌ์ผ์ด์ ์ ๊ธฐ๋ฅ์ ๊ฐ์ฒด๊ฐ ์ํธ์์ฉ์ ํตํด ๊ตฌํ๋๋ค.
๊ฐ์ฒด๊ฐ ์ํธ์์ฉ์ ์ฃผ๊ณ ๋ฐ๋ ๋ฉ์ธ์ง๋ก ํํ๋๊ณ ,
๋ฉ์ธ์ง๋ฅผ ์ ์กํ๊ธฐ ์ํ ์ง์์ด ๋ ๊ฐ์ฒด๋ฅผ ๊ฒฐํฉ์ํค๋ฉฐ ์์กด์ฑ์ ๋ง๋ค์ด๋ธ๋ค.
์ข์ ๊ฐ์ฒด์งํฅ ์ค๊ณ?
ํ๋ ฅํ๋ ๊ฐ์ฒด ์ฌ์ด์ ์์กด์ฑ์ ์ ์ ํ ๊ด๋ฆฌํ๋ ์ค๊ณ์ด๋ค.
์ด๋ค ๊ธฐ๋ฅ์ ์ค๊ณํ๋ ๋ฐฉ๋ฒ์ ํ ๊ฐ์ง ์ด์์ผ ์ ์๋ค.
๋์ผํ ๊ธฐ๋ฅ์ ํ ๊ฐ์ง ์ด์์ผ๋ก ์ค๊ณํ ์ ์๊ธฐ ๋๋ฌธ์, ์ค๊ณ๋ ํธ๋ ์ด๋์คํ์ ์ฐ๋ฌผ์ด๋ค.
์ด๋ค ๊ฒฝ์ฐ์๋ ๋ชจ๋ ์ฌ๋์ ๋ง์กฑ์ํฌ ์ ์๋ ์ค๊ณ๋ ์๋ค.
์ค๊ณ๋ ๊ท ํ์ ์์ . ํ๋ฅญํ ์ค๊ณ๋ ์ ์ ํ ํธ๋ ์ด๋์คํ์ ๊ฒฐ๊ณผ
๊ฒฐ๋ก
์ฑ ์ ๋ด์ฉ์ ๋๋ฆ๋๋ก ์ ๋ฆฌํด๋ณด์๋๋ฐ, ์ค๋ณต๋๋ ๋ด์ฉ๋ ๋ง๊ณ ์ ๋ฆฌ๊ฐ ์๋ ๊ฒ ๊ฐ๊ธด ํ๋ค.
๋ด๊ฐ ์ดํดํ๋๋ก ์์ฝํด๋ณด์๋ฉด,
๊ตณ์ด ์ข์ ์ค๊ณ๋ฅผ ํ์ง ์๋๋ผ๋ ๋์๊ฐ๋ ํ๋ก๊ทธ๋จ์ ๋ง๋ค ์ ์๋ค.
ํ์ง๋ง ์์กด์ฑ์ด ๋์ ์ฝ๋๋ ๋ณ๊ฒฝ์ด ์ด๋ ต๋ค.
๊ทธ๋ฆฌ๊ณ , ์๊ตฌ์ฌํญ์ ๊ณ ์ ๋์ง ์๊ณ ์์ฃผ ๋ณ๊ฒฝ๋๋ค. ๋ฐ๋ผ์ ์ฐ๋ฆฌ๋ ๋ฏธ๋๋ฅผ ์ํด ๋ณ๊ฒฝ์ ์ฉ์ดํ ์ฝ๋๋ฅผ ์์ฑํ ํ์๊ฐ ์๋ค.
๋ณ๊ฒฝ์ ์ฉ์ดํ๊ธฐ ์ํด์๋, ๊ฐ ๊ฐ์ฒด๊ฐ ๊ฒฐํฉ๋๊ฐ ๋ฎ์์ผํ๊ณ ์ด๋ ๋ถํ์ํ ์์กด์ฑ์ ์ ๊ฑฐํด์ผํ๋ค๋ ๋ง์ด๋ค.
์์กด์ฑ์ ์ ๊ฑฐํ๊ธฐ ์ํด์๋, ์บก์ํ๋ฅผ ์ด์ฉํด์ ์ธํฐํ์ด์ค๋ง ์ ๊ณตํ๊ณ ์์ธํ ๊ตฌํ์ ์ธ๋ถ์์ ์ ์ ์์ด์ผ ํ๋ค.
๊ทธ๋ฐ๋ฐ, ์บก์ํ๋ฅผ ํ๋ค๋ณด๋ฉด ๊ฒฐํฉ๋๊ฐ ์คํ๋ ค ๋์์ง๋ ์ํฉ์ด ๋ฐ์ํ๊ธฐ๋ ํ๋ค. ๋ ๊ฐ์ง์ค์ ์ด๋ค ๊ฒ์ด ์ ๋ต์ด๋ผ๊ณ ํ ์ ์์ผ๋ฉฐ, ๋ฐ๋ผ์ ์ค๊ณ๋ ๋ต์ด ์ ํด์ ธ์์ง ์์ ๊ท ํ์ ์์ ์ด๋ผ๋ ํํ์ ์ฐ๊ธฐ๋ ํ๋ค.
๋ชจ๋ ์ฌ๋์ ๋ง์กฑ์ํค๋ ์ค๊ณ๋ ์๋ค. ๋ผ๋ ๋ง์ด ์ธ์์ ์ด์๋ค.
๊ทธ๋ผ์๋ ๋ ๋์ ์ค๊ณ๋ฅผ ์ํด ๊พธ์คํ ๊ณ ๋ฏผํด์ผํ ๊ฒ ๊ฐ๋ค.