10_Oct_2021 ๐ฐ์๋ฆฌ์ค AI ํธ๋ TIL: ์๋ฃ๊ตฌ์กฐ (๋ฐฐ์ด๊ณผ ์ฐ๊ฒฐ ๋ฆฌ์คํธ)
์๋ฃ๊ตฌ์กฐ์ ์๋ฏธ
์๋ฃ๋ฅผ ์ ์ฅํ๋ ๊ตฌ์กฐ. ์ฌ๋ฌ๊ฐ์ง ์ข ๋ฅ๊ฐ ์์ผ๋, ์ ์ฅ๋ ์๋ฃ์ ๋ํด ์ ๊ทผํ๋ ๋ฐฉ๋ฒ ๋ฑ์ ์ฐจ์ด๊ฐ ์กด์ฌํ๋ค.
์๋ฃ๊ตฌ์กฐ๋ฅผ ๋ฐฐ์ฐ๋ ์ด์ :
์๋ฃ๊ตฌ์กฐ์ ๋ฐ๋ผ ์ฅ๋จ์ ์ด ์กด์ฌํ๋ฉฐ ๊ตฌํํ๊ณ ์ ํ๋ ํ๋ก๊ทธ๋จ์ ์ฑ๋ฅ์ ๊ณ ๋ คํ์ฌ ์๋ง์ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ ํํด์ผ ํ๋ค. ํ๋ก๊ทธ๋จ์ ์๋ฃ๋ฅผ ํจ์จ์ ์ผ๋ก ๋ด๊ณ ํ์ฉํ๊ธฐ ์ํด ์ฌ์ฉํ๋ค.
ํน์ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํ๊ธฐ ์ํด, ์ ์ ํ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ฌ์ฉํด์ผ ์ข์ ์ฑ๋ฅ์ ๋ผ ์ ์๋ค.
์ถ์์ ์๋ฃํ
์ด๋ค ์๋ฃ์ ๊ทธ ์๋ฃ์ ๋ํ ์ฐ์ฐ(๋์)๋ค์ ์ํ์ ์ธ ์ ์๋ฅผ ์๋ฏธํ๋ค. ๊ทธ๋ฌ๋, ๊ทธ ์ ์๋ฅผ ๊ตฌํํ๋ ๋ฐฉ๋ฒ์ ์ ํํ๊ฒ ๋ช
์๋์ด ์์ง ์๋ค.
์ถ์์ ์๋ฃํ์ ์ถ์์ ์ด๋ผ๋ ๋จ์ด์ ์๋ฏธ์์ ์ ์ ์๋ฏ ๋ช
ํํ์ง ์์ ๊ฒ์ด๋ค.
์๋ฃํ
์๋ฃํ์ ์ด๋ค ์๋ฃ๊ฐ ์๋ณ๋ ์ ์๋ ๋ฐฉ๋ฒ๊ณผ, ๊ทธ ์๋ฃ์ ๋ํ ์ฌ๋ฌ ๊ฐ์ง ์ฐ์ฐ์ ์ ๊ณตํ๋ค.
65๋ผ๋ ์๋ฃ๋ ๊ทธ๋๋ก ์๋ฅผ ๋ํ๋ผ ์๋ ์๊ณ ์ ๋์ฝ๋๋ก ํด์ํ 'A'๋ฅผ ๋ํ๋ผ ์ ์๋ค.
๋ฐ๋ผ์ ์ด๋ฅผ ์ปดํจํฐ๊ฐ ํด์ํ๊ธฐ ์ํด์๋ ์๋ฃํ์ ๋ช ์ํด์ฃผ์ด์ผ ํ๋ ๊ฒ์ด๋ค.
๋ง์ผ ์๋ฅผ ๋ํ๋ด๋ ์๋ฃํ์ด๋ผ๋ฉด ์ฌ์น์ฐ์ฐ์ด ๊ฐ๋ฅํ๋, ๋ฌธ์์ ๊ฒฝ์ฐ ์ฌ์น์ฐ์ฐ์ ์ ์ฉํ ์ ์๋ค.
์๋ฃํ์ ์ด๋ค ์๋ฃ๊ฐ ์๋ณ๋๋ ๋ฐฉ๋ฒ์ ์ ์ํ๊ณ , ์๋ฃ์ ์ ์ฉํ ์ ์๋ ์ฐ์ฐ์ ๊ฒฐ์ ํ๋ค.
์๋ฃ๋ฅผ ํน์ ๋ถ๋ฅ์ ๋ฐ๋ผ ์ฌ๋ฐ๋ฅด๊ฒ ํํํ๊ธฐ ์ํ ์ ์์ ์ด์ ๊ตฌํ์ด ์๋ฃํ์ด๋ผ๊ณ ํ ์ ์๋ค.
์ถ์์ ์๋ฃํ
์ถ์์ ์๋ฃํ์ ๊ตฌํ ๋ฐฉ๋ฒ์ ๋ช ์ํ๊ณ ์์ง ์๋ค๋ ์ ์์ ๊ตฌ๋ณ๋๋ค.
๊ทธ๋ฆ์ ์ถ์์ ์๋ฃํ์ด๋ผ๊ณ ํ๋ค๋ฉด, ๊ทธ๋ฆ์ด ๋ด๊ณ ์๋ ์๋ฃ์ ๊ทธ ์๋ฃ์ ํด๋นํ๋ ์ฐ์์ ์ ์๋ฅผ ํฌํจํด์ผ ํ๋ค.
๊ทธ๋ฆ์ด ์์์ ๋ด๊ณ , ๊ทธ ๊ทธ๋ฆ์ ๋ด๊ธด ์์์ ๋จน์ ์ ์์ด์ผ ํ๋ฏ, ์ถ์์ ์๋ฃํ ๋ํ ์๋ฃ๋ฅผ ๋ด๊ณ ์ฐ์ฐ์ ํ ์ ์์ด์ผ ํ๋ค. ๊ทธ๋ฌ๋, ์ด๋ป๊ฒ ์๋ฃ์ ์ ๊ทผํ ์ ์๋ ์ง์ ๋ํ ๋ฐฉ๋ฒ์ ์ฃผ์ด์ง์ง ์๋๋ค.
์ฌ๊ธฐ์ ์ถ์์ ์๋ฃํ์ ์๋ฃ๋ฅผ ์ด๋ป๊ฒ ์ ์ฅํ๊ณ , ์ฐ์ฐ์ ํ ์ ์๋ ์ง์ ๋ํด ๋ช ํํ ๊ตฌํ๋ ๊ฒ์ ์๋ฃ๊ตฌ์กฐ๋ผ๊ณ ํ ์ ์๋ค.
์ ๋ฆฌ
- ์ถ์์ ์๋ฃํ: ์๋ฃ๋ค๊ณผ, ๊ทธ ์๋ฃ์ ๋ํ ์ฐ์ฐ๋ค์ ๊ฐ๋ ์ ์ผ๋ก ์ ์๋ง ํ ๊ฒ
- ์๋ฃ๊ตฌ์กฐ: ์๋ฃ๋ฅผ ์ ์ฅํ๋ ๋ฐฉ๋ฒ๊ณผ ์๋ฃ์ ์ ์ฉํ ์ ์๋ ์ฐ์ฐ์ ๊ตฌ์ฒด์ ์ผ๋ก ์ ๊ณตํ ๊ฒ
์ถ์์ ์๋ฃํ์ ๊ตฌ์ฒด์ ์ผ๋ก ๊ตฌํํ ๊ฒฐ๊ณผ๊ฐ ์๋ฃํ์ด๋ผ๊ณ ํ ์ ์๋ค.
๋ฐฐ์ด๊ณผ ์ฐ๊ฒฐ ๋ฆฌ์คํธ
์ฃผ์ ํ์ด์ฌ์ ๋ฆฌ์คํธ์ ์๋ฃ๊ตฌ์กฐ์์์ ๋ฆฌ์คํธ๋ ๋ค๋ฅธ ๊ฐ๋ ์ด๋ค.
๋ฆฌ์คํธ
๋ฆฌ์คํธ๋ ์์๊ฐ ์กด์ฌํ๊ณ ์ผ๋ ฌ๋ก ๋์ด๋ ๊ฐ์ ๊ฐ์ง ์ถ์์ ์๋ฃํ์ด๋ค.
๋ฆฌ์คํธ๊ฐ ์ ๊ณตํ๋ ๋ํ์ ์ฐ์ฐ:
- ์กฐํ: ์์์ ์์น์ ์๋ฃ๊ฐ ๋ฌด์์ธ์ง ํ์.
- ์ฝ์ : ์์์ ์์น์ ์๋ฃ๋ฅผ ์ถ๊ฐ.
- ์ญ์ : ์์์ ์์น์ ์๋ฃ๋ฅผ ์ ๊ฑฐ.
๋ฆฌ์คํธ๋ผ๋ ์ถ์์ ์๋ฃํ์ ๊ตฌํํ ๋ํ์ ์ธ ์์๊ฐ ๋ฐฐ์ด(array)์ด๋ค
๋ฒ ์ด์ ์ ์ฅ๋๋ ๊ฐ๋ค์ ์์๋ฅผ ๋ํ๋ด๋ ๋ฒํธ(index)๋ฅผ ๊ฐ์ง๋ค.
let array = [1,2,3,4,5,6]; //index: 0,1,2,3,4,5
๋ฐฐ์ด - ์กฐํ
๋ฐฐ์ด์ ๋ฐฐ์ด ๋ด์ ํน์ ์์์ ๊ฐ์ ์กฐํํ๊ณ ์ ํ ๋, ํจ์จ์ ์ด๊ณ ๋น ๋ฅธ ์ฐ์ฐ์ ํ ์ ์๋ค.
๋ฐฐ์ด - ์ฝ์
๋ฐ๋ฉด, ์๋ฃ๋ฅผ ์ถ๊ฐํ ๋์๋, ์๋ก์ด ์๋ฃ๊ฐ ์ถ๊ฐ๋๋ฉด์, ์๋ฃ๋ค์ ์์๋ฅผ ๋ณ๊ฒฝํด์ฃผ์ด์ผ ํ๊ธฐ ๋๋ฌธ์ ๋ฒ๊ฑฐ๋กญ๋ค.
์ฝ์
์ฐ์ฐ์์๋ ์ถ๊ฐ๋ ์๋ฃ๊ฐ ๋ค์ด๊ฐ ๊ณต๊ฐ์ ๋น์์ฃผ๊ธฐ ์ํด, ๊ธฐ์กด ์๋ฃ๋ ํ ์นธ์ฉ ๋ฐ๋ ค๋๊ฒ ๋๋ค.
๋ฐฐ์ด - ์ญ์
์ฝ์ ๊ณผ ๋ฐ๋๋ก, ์ ๊ฑฐํ ์ธ๋ฑ์ค์ ์๋ฃ๋ฅผ ๋น์ฐ๊ณ ์๋ฃ๊ฐ ์ค์ด๋ค์์ผ๋ฏ๋ก ๋น์๋ฆฌ๋ฅผ ๋ฉ๊พธ๊ธฐ ์ํด ์๋ฃ๋ค์ด ํ ์นธ์ฉ ๋น๊ฒจ์ง๋ค. -> ๋ฐฐ์ด์ด ๋ด๊ณ ์๋ ์๋ฃ๊ฐ ํ๋ ์ค์์ผ๋ฏ๋ก, ๋จ๋ ๊ณต๊ฐ๋ ์ ๊ฑฐํ๋ค.
์ฐ๊ฒฐ ๋ฆฌ์คํธ (Linked List)
๋ฆฌ์คํธ๋ฅผ ๊ตฌํํ ์๋ฃ๊ตฌ์กฐ ์ค, ๋ํ์ ์ธ ๋ค๋ฅธ ์๋ฃ๊ตฌ์กฐ๋ ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ด๋ค.
๋ฐฐ์ด์ ๊ฐ ์๋ฃ์ ์ธ๋ฑ์ค๋ฅผ ๋ถ์ฌ ์ ์ฅํ๋, ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ์ฌ๋ฌ ๊ฐ์ ๋
ธ๋๋ฅผ ์ ์ฅํ๋ ๋ฐฉ์์ผ๋ก ๊ตฌํํ๋ค.
๋ ธ๋๋ ์๋ฃ์ ํฌ์ธํฐ๋ฅผ ๊ฐ์ง๋ค. ์๋ฃ๋ ์ ์ฅํ๋ ๊ฐ ์์ฒด์ด๊ณ , ํฌ์ธํฐ๋ ์์ ์ ๋ค์ ์์์ ๋ ธ๋๋ฅผ ๊ฐ๋ฆฌํจ๋ค.
์ฐ๊ฒฐ ๋ฆฌ์คํธ - ํ์
์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ์ด๋ฌํ ํน์ฑ์ผ๋ก ํน์ ์์น์ ์๋ฃ๋ฅผ ์ฐพ๋ ๊ฒ์ด ๋ฒ๊ฑฐ๋กญ๋ค. ์ฐพ๊ณ ์ถ์ ์๋ฃ๋ฅผ ์ฐพ์ผ๋ ค๋ฉด, ์ฒซ ๋ฒ์งธ ๋ ธ๋๋ถํฐ ์ฐจ๋ก๋ก ํฌ์ธํฐ๋ฅผ ํตํด ์ด๋ํ๋ฉฐ ํ์ํด์ผ ํ๊ธฐ ๋๋ฌธ์ด๋ค.
๋ฐ๋ผ์, ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ์ฐพ๋ ์๋ฃ์ ์์น๊ฐ ์์์ ์ผ๋ก๋ถํฐ ๋ฉ์ด์ง ์๋ก ์ฐ์ฐ ํ์๊ฐ ๋ง์์ง๋ค.
์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ์ฅ์ ์, ์๋ฃ์ ์ถ๊ฐ์ ์ญ์ ์์ ๋๋ฌ๋๋๋ฐ,
์ฐ๊ฒฐ ๋ฆฌ์คํธ - ์ฝ์
์ฐ๊ฒฐ ๋ฆฌ์คํธ์์ ๋ ธ๋๋ฅผ ์ฝ์ ํ ๋์๋, ์ด์ ๋ ธ๋์ ์ ๋ค ๋ ธ๋์ ํฌ์ธํฐ ๊ด๊ณ๋ฅผ ๋์ ํ, ์ถ๊ฐํ ์์น์ ์ด์ ๋ ธ๋์ ํฌ์ธํฐ๋ฅผ ์๋ก์ด ๋ ธ๋๋ก, ์๋ก์ด ๋ ธ๋์ ํฌ์ธํฐ๋ฅผ ์ด์ ๋ ธ๋๊ฐ ๊ฐ๋ฆฌํค์ ๋ ธ๋๋ก ์ค์ ํ๋ฉด ์ถ๊ฐํ ์ ์๋ค.
์ฐ๊ฒฐ ๋ฆฌ์คํธ - ์ญ์
์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ์ญ์ ๋, ์ ๊ฑฐํ ๋
ธ๋์ ์ด์ ๋
ธ๋์ ํฌ์ธํฐ๊ฐ ์ ๊ฑฐํ ๋
ธ๋๊ฐ ๊ฐ๋ฆฌํค๋ ๋
ธ๋๋ฅผ ๊ฐ๋ฆฌํค๋๋ก ์ค์ ํ๋ฉด ์ญ์ ํ ์ ์๋ค.
์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ์์ ์ ๋ค์ ๋
ธ๋๋ฅผ ๊ฐ๋ฆฌํค๋ ์๋์ ์ธ ์์๋ฅผ ํํํ๊ธฐ ๋๋ฌธ์, ์ด์ ๊ฐ์ ์ฐ์ฐ์ด ๊ฐ๋ฅํ๋ค.
๋ฐฐ์ด
- ์ฅ์ : ํน์ ์์น์ ์๋ฃ ํ์์ด ์ ๋ฆฌ
- ๋จ์ : ์๋ฃ์ ์ฝ์ ๊ณผ ์ญ์ ์์ ํจ์จ์ด ๋ฎ์
์ฐ๊ฒฐ ๋ฆฌ์คํธ
- ์๋ฃ์ ์ฝ์ ๊ณผ ์ญ์ ๊ฐ ์ ๋ฆฌ
- ํน์ ์์น์ ์๋ฃ ํ์์ด ๋ฒ๊ฑฐ๋ก์
์๋ฃ๊ตฌ์กฐ์ ๊ตฌํ ๋ฐฉ๋ฒ
์๋ฃ๊ตฌ์กฐ๋ ์ถ์์ ์๋ฃํ์ ๋ช
์๋ ํํ ๋ฐ ์ฐ์ฐ ๋ฐฉ๋ฒ์ ๋ช
์ํ๋ค.
๊ฐ์ฒด์งํฅ ํ๋ก๊ทธ๋๋ฐ์ ์๋ก ๋ค๋ฉด, ์ถ์์ ์๋ฃํ์ ์ธํฐํ์ด์ค, ์๋ฃ๊ตฌ์กฐ๋ ํด๋์ค๋ก ์๊ฐํ ์ ์๋ค.
์ธํฐํ์ด์ค๋?
๊ฐ์ฒด์งํฅ ๊ตฌ์กฐ์์ ์ถ์ ๋ฉ์๋๋ง์ผ๋ก ์ด๋ฃจ์ด์ง ์ค๊ณ์ฉ ํด๋์ค
๊ตฌํ ๋ถ๋ถ์ด ๋น์ด์๋ ๋ฉ์๋๋ฅผ ์ถ์ ๋ฉ์๋๋ผ๊ณ ํ๋ฉฐ, ์์ ๋ฐ๋ ํด๋์ค์์ ์ด๋ฅผ ๊ตฌํํ์ฌ ์ฌ์ฉํ๋ค.
์ฆ, '๋ฆฌ์คํธ'๋ผ๋ ์ธํฐํ์ด์ค์๋ ์ฝ์
๊ณผ ์ญ์ ๋ฅผ ์ง์ํด์ผ ํ๋ค๋ผ๋ ๋ช
์ธ๋ง ์ฃผ์ด์ง๊ณ ,
์ค์ ๋์ ๋ถ๋ถ์ ๋ฆฌ์คํธ๋ฅผ ์์๋ฐ์ ๋ฐฐ์ด ํด๋์ค, ์ฐ๊ฒฐ๋ฆฌ์คํธ ํด๋์ค์์ ๊ตฌํํด์ผ ํ๋ค.
Python์ ์ธํฐํ์ด์ค ์
class MyInterface(metaclass=Xmeta): # ์ถ์ ํด๋์ค๋ก ๋ง๋ค๊ธฐ ์ํ ๋ฉํํด๋์ค ์ ์ @abstractmethod # ์ถ์ ๋ฉ์๋์์ ๋ํ๋ด๋ ๋ฐ์ฝ๋ ์ด์ def func() : pass
Java ๋ฑ ๋ค๋ฅธ ๊ฐ์ฒด์งํฅํ ์ธ์ด์๋ ๋ฌ๋ฆฌ Python์์๋ ์ธํฐํ์ด์ค์ ๊ธฐ๋ฅ์ ์ง์ ์ง์ํ์ง ์๋๋ค.
๋ฐ๋ผ์ ์์ ๊ฐ์ ๋ฐฉ์์ผ๋ก ํํํด์ผ ํ๋ค.
์๋ฃ๊ตฌ์กฐ๋ฅผ ๋ง๋๋ ๋ฐ์๋ ์ธํฐํ์ด์ค๊ฐ ์์๋ฐ๋ ํด๋์ค๊ฐ ํ์ํ๋ค.
ํด๋์ค๊ฐ ๊ฐ๊ณ ์๋ ํ๋๊ฐ ์๋ฃ์ ํด๋นํ๊ณ , ๋ฉ์๋๊ฐ ์๋ฃ์ ์ ์ฉํ ์ ์๋ ์ฐ์ฐ์ด๋ค.
์๋ฃ๊ตฌ์กฐ์ ๊ตฌํ ์์
import queue q = queue.Queue()
ํ์ด์ฌ์ ๊ธฐ๋ณธ ๋ผ์ด๋ธ๋ฌ๋ฆฌ ์ค, queue๋ผ๋ ์๋ฃ๊ตฌ์กฐ๋ฅผ ๊ตฌํํ Queueํด๋์ค๊ฐ ์๋ค.
ํ ์๋ฃ๊ตฌ์กฐ์ ์๋ฃ ์ ์ฅ ๋ฐ ์ฐ์ฐ ๋ฐฉ๋ฒ์ ๊ฐ์ถ๊ณ ์๋ ํด๋์ค์ด๋ค.
์ปจํ
์ด๋๋? : ๋ฆฌ์คํธ,ํํ, ๋์
๋๋ฆฌ ๋ฑ์ ํ๋ ์ด์์ ์์๋ฅผ ๋ด์ ์ ์๋ ์๋ฃํ์ด๋ค.
๋ด๋ถ์ ์ผ๋ก Container ํด๋์ค๋ฅผ ์์๋ฐ์ sub class์ ํด๋นํ๋ค.
์๋ฅผ ๋ค์ด, ์ต๋๊ฐ์ ๋ฐํํ๋ ์์ ์ ์ํ ์ปจํ ์ด๋๋ ๋ค์์ ์ฐ์ฐ์ ์ํํ๋ ๋ฉ์๋๋ฅผ ๊ฐ๋๋ค.
- ์ ์๋ฅผ ์ปจํ ์ด๋์ ์ถ๊ฐ
- ์ ์๋ฅผ ์ปจํ ์ด๋์์ ์ ๊ฑฐ
- ์ปจํ ์ด๋ ๋ด์ ์ ์ ์ค ์ต๋๊ฐ ๋ฐํ
์๋ฃ๊ตฌ์กฐ ๊ตฌํํด๋ณด๊ธฐ
์๋ฃ๊ตฌ์กฐ๋ฅผ ํ์ฉํ์ฌ ์ข์ ํด๋ฒ์ธ์ง ํ๋จํ๋ ๋ช๊ฐ์ง ๊ธฐ์ค์
- ์ฝ๋๊ฐ ๊ฐ๊ฒฐํ์ง (์ ์ง๋ณด์/ํด์ ์ฉ์ด)
- ์ผ๋ง๋ ๋น ๋ฅธ์ง (์๊ฐ ํจ์จ)
- ๋ฆฌ์์ค๋ฅผ ์ผ๋ง๋ ์ฐจ์งํ๋ ์ง (๊ณต๊ฐ/๋ฉ๋ชจ๋ฆฌ ํจ์จ)
- ๊ตฌํ ์๊ฐ์ด ์งง์๊ฐ (์๊ฐ์ ๊ฒฝ์ ์ฑ)
์ผ๋ง๋ ๋น ๋ฅธ๊ฐ
์ํํ๋ ๋ช ๋ น์ ์๊ฐ ์ ์์๋ก ์๊ฐ์ด ๋ ๊ฑธ๋ฆฐ๋ค.sum = 0 for i in range(30): sum = sum + 1
sum = 0 for i in range(300000): sum = sum + 1
์์ ์ฝ๋๊ฐ ์๋ ์ฝ๋ ๋ณด๋ค ์ ์ ์๋ก ๋ฐ๋ณตํ์ฌ, ์๊ฐ์ด ๋ ๊ฑธ๋ฆฐ๋ค.
์๊ฐ ๋ณต์ก๋
์๊ณ ๋ฆฌ์ฆ์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ์ ๋ํํ์ฌ ๋ํ๋ผ ์ ์๋ ๋ฐฉ๋ฒ
์ผ๋ฐ์ ์ผ๋ก ๋ฌธ์ ์์ ์ฃผ์ด์ง๋ ์ต์
์ ๊ฒฝ์ฐ(Big O notation)์ ๋ํ ์์์๊ฐ์ ๋ํ๋ด๋ ๋ฐ ์ฌ์ฉ๋๋ค.
๋ฐฐ์ด์ ์ฌ์ฉํ ๊ฒฝ์ฐ, ์์ n๊ฐ๋ฅผ ๋ชจ๋ ์ผ์ชฝ์ผ๋ก๋ง ์ฝ์ ํ๋ ๊ฒฝ์ฐ๊ฐ ์ต์ ์ ๊ฒฝ์ฐ์ด๋ค. ์์์ ์๊ฐ n๊ฐ๋ผ๋ฉด,
* (n(n+1))/2 ์ ์๊ฐ๋ณต์ก๋์ด๋ฉฐ, ์ต์ ์ ๊ฒฝ์ฐ์ด๋ค.
์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ฅผ ์ฌ์ฉํ ๊ฒฝ์ฐ, ์์ n๊ฐ๋ฅผ ๋ชจ๋ ์ผ์ชฝ์ผ๋ก ์์ ํ๋ฉด ์ด์ ๋ ธ๋ ์์ n๋ฒ ๋งํผ ์ฒซ ๋ฒ์งธ ๋ ธ๋๋ฅผ ๋ง๋ค์ด ์ฐ๊ฒฐ๋ง ํด์ฃผ๋ฉด ๋๋ฏ๋ก, O(n)์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค.
๋ง์ง๋ง์ผ๋ก, ์ด ๋๋ฌธ์ ์๋ฃ ๊ตฌ์กฐ๋ฅผ ๊ณต๋ถํด์ผ ํ๋ ์ด์ ๋ ์๋ฃ๊ตฌ์กฐ์ ๋ฐ๋ผ ํน์ฑ๊ณผ ๋์๋ฐฉ๋ฒ์ด ๋ค๋ฅด๊ธฐ ๋๋ฌธ์ ์์ฑํ๊ณ ์ ํ๋ ํ๋ก๊ทธ๋จ์ ๋ชฉ์ ์ ๊ฐ์ฅ ํจ์จ์ ์ผ๋ก ๋ฌ์ฑํ ์ ์๋ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ฌ์ฉํ๊ธฐ ์ํด์ ์ด๋ค.
๋ฌธ์ ํด๊ฒฐ์ ์ํ ์๋ฃ๊ตฌ์กฐ ํ์ฉ
- ๋ฌธ์ ๋ฅผ ํ์ ํ๋ค. (์ด๋ค ์๋ฃ๋ฅผ ๋ด์์ง, ์๋ฃ์ ์ด๋ค ์๋ฏธ๊ฐ ์๋ ์ง ํ์ )
- ์๋ฃ๊ตฌ์กฐ์ ํ์ํ ๊ธฐ๋ฅ์ ํ์ . (์๋ฃ๋ฅผ ์ด๋ป๊ฒ ์ฌ์ฉํ๋ ์ง ํ์ )
- ๋ฌธ์ ๋ฅผ ํจ์จ์ ์ผ๋ก ํด๊ฒฐํ๋ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ค๊ณํ๊ณ ์ฌ์ฉํ๋ค. (๋ชฉ์ ์ ๋ง๋ ์๋ฃ๊ตฌ์กฐ๋ก ๋ฌธ์ ํด๊ฒฐ)
์๋ฃ๋ฅผ ์ ์ ์ฅํ๋ ๋ค๋ ๊ฒ์?
๊ตฌํํ๊ณ ์ ํ๋ ํ๋ก๊ทธ๋จ์ ์๋์ ๋ง๋ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ฌ์ฉํด์, ํจ์จ์ ์ธ ์ฑ๋ฅ์ผ๋ก ๊ตฌํํ๋ ๊ฒ์ ์๋ฏธํ๋ค.
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ(10_Oct_2021 ๐ฐ์๋ฆฌ์ค AI ํธ๋ TIL: ์๋ฃ๊ตฌ์กฐ (๋ฐฐ์ด๊ณผ ์ฐ๊ฒฐ ๋ฆฌ์คํธ)), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@juanito_y247/10Oct2021-์๋ฆฌ์ค-AI-ํธ๋-TIL-์๋ฃ๊ตฌ์กฐ-๋ฐฐ์ด๊ณผ-์ฐ๊ฒฐ-๋ฆฌ์คํธ์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค