ํ๋ก์ด๋ ์์ ์๊ณ ๋ฆฌ์ฆ์ด๋? ๋ชจ๋ ์ง์ ์์ ๋ค๋ฅธ ๋ชจ๋ ์ง์ ๊น์ง์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ๋ชจ๋ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. 2์ฐจ์ ํ ์ด๋ธ์ ์ต๋จ ๊ฑฐ๋ฆฌ ์ ๋ณด๋ฅผ ์ ์ฅํ๋ค. ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ๊ณผ์ ์ฐจ์ด - ์์ค์ฝ๋๊ฐ ๋ค์ต์คํธ๋ผ์ ๋นํด ์งง์ ๊ตฌํ์ด ๊ฐ๋จํ๋ค. - ๋ค์ต์คํธ๋ผ์ ๊ฒฝ์ฐ ๋จ๊ณ๋ง๋ค ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ์ง๋ ๋ ธ๋๋ฅผ ํ๋์ฉ ๋ฐ๋ณต์ ์ผ๋ก ์ ํํ๋ค. ํ๋ก์ด๋ ์์ ๋ํ ๋จ๊ณ๋ง๋ค '๊ฑฐ์ณ ๊ฐ๋ ๋ ธ๋'๋ฅผ ๊ธฐ์ค์ผ๋ก ์๊ณ ๋ฆฌ์ฆ์ ์ํํ๋ค. ํ์ง๋ง, ๋งค ๋จ๊ณ๋ง๋ค ๋ฐฉ๋ฌธํ์ง ์๋ ๋ ธ๋ ์ค์์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ๋ ๋ ธ๋๋ฅผ ์ฐพ์ ํ์๊ฐ ์๋ค! ํ๋ก์ด๋ ์์ ์๊ณ ๋ฆฌ์ฆ์ ์ ํ์ ํ๋ก์ด๋ ์์ ์๊ณ ๋ฆฌ์ฆ ์ง์ ์๋ํ๊ธฐ [step 0] ๊ทธ๋ํ์ ๋ ธ๋์ ๊ฐ์ ์ ๋ฐ๋ผ ์ต๋จ ๊ฑฐ๋ฆฌ ํ ์ด๋ธ์ ๊ฐฑ์ ํ๋ค. [step 1] 1๋ฒ ๋ ธ๋๋ฅผ ๊ฑฐ์ณ ๊ฐ๋ ๊ฒฝ์ฐ๋ฅผ ๊ณ ๋ คํ์ฌ ํ ์ด๋ธ์ ๊ฐฑ์ ํ๋ค. ..
2-3-4 ํธ๋ฆฌ๋? ํ์ํธ๋ฆฌ ์ค ํ๋๋ก, ์ด์ง ํธ๋ฆฌ๊ฐ ์๋๋ค. ์ฆ, ์์ ๋ ธ๋๊ฐ 2๊ฐ๋ณด๋ค ๋ง์ ์ ์๋ค. ํน์ง์ผ๋ก 1. ์ด๋ฆ์ฒ๋ผ ์์ ๋ ธ๋์ ๊ฐ์๋ 2๊ฐ ๋๋ 3๊ฐ ๋๋ 4๊ฐ๋ฅผ ๊ฐ์ง ์ ์๋ค. (์ฆ, ์ต์ 2๊ฐ ~ ์ต๋ 4๊ฐ) 2. ๋ชจ๋ leaf ๋ ธ๋๊ฐ ๊ฐ์ level์ ์กด์ฌํ๋ค. 3. ์ฝ์ ์, leaf ๋ ธ๋์ ์ฝ์ ํ๋ค. ์ฝ์ ์ถ๊ฐํ key๊ฐ root๋ถํฐ leaf ๋ ธ๋๊น์ง ๋ด๋ ค๊ฐ๋ฉด์, 4-๋ ธ๋์ด๋ฉด splitํ๋ฉด์ ๋ด๋ ค๊ฐ๋ค. splitํ ๋ ์ค๊ฐ ๊ฐ์ ๋ถ๋ชจ ๋ ธ๋๋ก ๋ฌด์กฐ๊ฑด ์ฌ๋ผ๊ฐ ์ ์๋๋ฐ, ๊ทธ ์ด์ ๋ key๊ฐ ๋ด๋ ค์ค๋ฉด์ 4-๋ ธ๋์ธ ๊ฒฝ์ฐ split์ ์ด๋ฏธ ํด๋จ๊ธฐ ๋๋ฌธ์ด๋ค. splitํ๋๋ฐ O(1)์ด ๊ฑธ๋ฆฌ๊ณ , ์ต์ ์ ๊ฒฝ์ฐ leaf๋ ธ๋๊น์ง ๋ด๋ ค๊ฐ๋ฉด์ ๋งค๋ฒ split ํด์ผํ๋ฏ๋ก(log n๋ฒ), ์ฝ์ ์์ ์๊ฐ๋ณต..
KMP ์๊ณ ๋ฆฌ์ฆ์ด๋? ๋ํ์ ์ธ ๋ฌธ์์ด ๊ฒ์ ์๊ณ ๋ฆฌ์ฆ KMP ์๊ณ ๋ฆฌ์ฆ์ ํต์ฌ ์๋ฆฌ ๋ฌธ์์ด ๋งค์นญ์ ํ๋ฉด์ ํ ์คํธ(์ ์ฒด ๋ฌธ์์ด)์ ํจํด(์ฐพ๋ ๋ฌธ์์ด)์์ ์๋ก ๋ค๋ฅธ ๊ธ์๊ฐ ๋์๋ค๋ฉด, '์๋ก ๋ค๋ฅธ ๊ธ์์ ๋ฐ๋ก ์ ๊น์ง๋ ์ผ์นํ๋ค'๋ผ๋ ์ฌ์ค๊ณผ '์ ๋์ฌ์ ์ ๋ฏธ์ฌ๊ฐ ๊ฐ์ ๋งํผ ๋น๊ต๋ฅผ ๋ํด๋ ๋๋ค'๋ ์ฌ์ค ์ด์ฉํ๊ธฐ ์ฆ, ๋ฐ๋ก ์ ๊ธ์๊น์ง ์ผ์นํ์์ผ๋ฏ๋ก, ์ ๋ฏธ์ฌ์ ์ ๋์ฌ๊ฐ ๊ฐ์๋งํผ ๋น๊ต๋ฅผ ๋ํ๋๋ก ์ด๋์์ผ์ฃผ๋ฉด ๋๋ค. ์ง์ ํ๋ํ๋ ์ดํดํด๋ณด๊ธฐ ์๋ ๊ทธ๋ฆผ์ ๋ณด๋ฉด์ ์ดํดํด๋ณด์. @ @ @ @ a b c d a b c d @ @ @ @ ์ธ ํ ์คํธ์์, (@๋ ์๋ฌด ๊ธ์๋ผ๊ณ ์๊ฐํ์, ์ ๊ฒฝ์์จ๋ ๋๋ค.) a b c d a b c w z ์ธ ํจํด์ ์ฐพ๋๋ค๊ณ ํด๋ณด์. ์ฒซ ๋ฌธ์๋ถํฐ ํ๋ ํ๋ ๋น๊ต๋ฅผ ์์ํ๋ค. @ @ @ @ a b c..
๋ฒจ๋ง-ํฌ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋? ํ ๋ ธ๋์์ ๋ค๋ฅธ ๋ ธ๋๊น์ง์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ์์ ๊ฐ์ค์น๋ฅผ ๊ฐ๋ edge(๊ฐ์ )์ด ์์ ๋ ์ฌ์ฉํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ๊ณผ ์ฐจ์ด๋ ๋ฌด์์ธ๊ฐ? ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ - ๋งค๋ฒ ๋ฐฉ๋ฌธํ์ง ์๋ ๋ ธ๋ ์ค์์ ์ต๋จ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์งง์ ๋ ธ๋๋ฅผ ์ ํํด ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํด๋๊ฐ๋ค. - ์์ ๊ฐ์ค์น๋ฅผ ๊ฐ๋ edge(๊ฐ์ )์ด ์๋ค๋ฉด ์ต์ ์ ํด๋ฅผ ์ฐพ์ ์ ์๋ค. - ์๊ฐ ๋ณต์ก๋๊ฐ ๋น ๋ฅด๋ค. ๋ฒจ๋ง-ํฌ๋ ์๊ณ ๋ฆฌ์ฆ - ๋งค ๋จ๊ณ๋ง๋ค ๋ชจ๋ edge(๊ฐ์ )์ ์ ๋ถ ํ์ธํ๋ฉด์ ๋ชจ๋ ๋ ธ๋๊ฐ์ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํด๋๊ฐ๋ค. - ์์ ๊ฐ์ค์น๋ฅผ ๊ฐ๋ edge๊ฐ ์์ด๋ ์ต์ ์ ํด๋ฅผ ์ฐพ์ ์ ์๋ค. - ์๊ฐ ๋ณต์ก๋๊ฐ ๋๋ฆฌ๋ค. ์ฆ, ๋ชจ๋ edge์ ๊ฐ์ค์น๊ฐ ์์์ผ ๋๋ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์, ์์ ๊ฐ์ค์น๋ฅผ ๊ฐ๋..
๋ค์ด๊ฐ๊ธฐ ์ ์ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ดํดํ๊ธฐ ์ํด ์ฌ๋ฌ ์ ํ๋ธ์ ๋ธ๋ก๊ทธ๋ฅผ ๋ฐฉ๋ฌธํ์๋๋ฐ ๋์ฒด๋ก ์ค๋ช ์ด ์ด๋ ต๊ฑฐ๋ ์๋ต์ด ๋ง๋ค.. ์ฝ๋ ์ค๋ช ๋ ์์ธํ์ง ์์ ์์ฌ์์ด ์์๋ค. (ํนํ, ๋ธ๋ก๊ทธ์ ์๋ ํ๋ ๊ทธ๋ฆผ์ ์์ด๋ ๊ฒ ๋ฑ๋ฑํ๊ฑธ๊น.. ์ ๋ชจ๋ฅด๋ ์ฌ๋์๊ฒ ๊ฑฐ๋ถ๊ฐ์ด ๋ ๋ค) ์ง์ ํ๋ํ๋ ๊ทธ๋ ค๊ฐ๋ณด๋ฉฐ ์ดํดํ ๋์ ๊นจ๋ฌ์์ ๋ค๋ฅธ ๋ถ๋ค๊ป ์์ธํ๊ณ ์ฝ๊ฒ, ๋ง์น ์๋ฌด๊ฒ๋ ๋ชจ๋ฅด๋ ์ด๋ฆฐ ์์ด์๊ฒ ์ค๋ช ํ๋ฏ์ด ์ค๋ช ํด๋ณด๋ ค๊ณ ํ๋ค. ๊ทธ๋ฆฌ๊ณ ์๊ฐ์ด ์ง๋๋ฉด ์์ด๋ฒ๋ฆฌ๋ ๋ฏธ๋์ ๋๋ฅผ ์ํ์ฌ ์์ธํ ๊ธฐ์ ํด๋ณด์๋ค. ์์ธํ ์์๋ถํฐ ์ ์ ๊ณผ์ ์ ์ถ์ํํด๋๊ฐ๋ฏ๋ก ์ดํดํ๊ธฐ ์ฌ์ธ ๊ฒ์ด๋ผ๊ณ ์๊ฐํ๋ค. ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ด๋? ๊ทธ๋ํ์ ํ ์ ์ (Vertex ๋๋ Node)์์ ๋ชจ๋ ์ ์ ๊น์ง์ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ๊ฐ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก, ์ต๋จ ๊ฒฝ๋ก ๋ฌธ์ ์ ์ฌ์ฉ๋๋ค..
- Total
- Today
- Yesterday
- ์๋ฐ์คํฌ๋ฆฝํธ
- ๋ธ๋ผ์ฐ์
- ์๋ฃ๊ตฌ์กฐ
- ํ์ด์ฌ
- DOM
- DB
- error
- zustand
- ์ ๋ ฌ
- Component
- ์๋ฌ
- JavaScript
- ๋ฐ์ดํฐ๋ฒ ์ด์ค
- mdn
- ์๊ณ ๋ฆฌ์ฆ
- leetcode
- React Query
- CSS
- ๋ฆฌ์กํธ
- BOJ
- Context API
- Python
- github
- ๊ทธ๋ํ
- useState
- Browser
- git
- state
- ํจ์
- react
์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |